Kombinatorikk: Inndelinger i grupper

Regneregel

På hvor mange måter kan vi dele \(n\) elementer inn i \(r\) grupper med et spesifisert antall elementer i hver gruppe? Vi kan finne et generelt svar på dette spørsmålet ved å anvende den generelle multiplikasjonssetningen.

Inndeling i grupper

Vi starter med å formulere et teorem som gir svaret på spørsmålet stilt over.

Inndeling i grupper

For å bevise dette resultatet kan vi først se på situasjonen hvor vi både har en inndeling i grupper og en nummeringer av elementene der elementene i gruppe 1 skal nummereres fra \( 1\) til \( n_1\), elementene i gruppe to skal nummereres fra \( n_1+1\) til \(n_1+n_2\), elementene i gruppe tre skal nummereres fra \( n_1+n_2+1\) til \( n_1+n_2+n_3\), og så videre. Dette er åpenbart ekvivalent med å nummerere de \( n\) elementene fra \( 1\) til \( n\) og definere at element nummer \( 1 \) til \( n_1\) er i gruppe 1, element nummer \( n_1+1\) til \( n_1+n_2\) er i gruppe 2 og så videre. Antall mulige måter å nummerere de \( n\) elementene fra \(1\) til \(n\) er \[_nP_n = n!.\]

Ved å benytte multiplikasjonssetningen kan vi utlede en alternativ formel for \(_nP_n\). Vi vil se på antall kombinasjoner av \( r + 1\) operasjoner, der den første operasjonen er å gruppere de \( n\) elementene inn i \( r\) grupper uten noen nummerering, mens for \( k=1,2,\ldots,r\) er operasjon \( k+1\) å nummerere elementene i gruppe \( k\). Vi lar \( v\) betegne antall mulige inndelinger i \( r\) grupper. Det er altså verdien til \(v\) vi er ute etter. For hver av disse \( v\) gruppeinndelingene kan elementene i gruppe 1 nummereres på \( _{n_1}P_{n_1}=n_1!\) måter, og for hver kombinasjon av gruppeinndelingen og nummerering i gruppe \( 1\) kan elementene i gruppe \( 2\) nummereres på \( _{n_2}P_{n_2}=n_2!\) måter, og så videre opp til gruppe \( r\). Multiplikasjonssetningen gir dermed at \[_nP_n = v \cdot n_1!\cdot n_2!\cdot\ldots\cdot n_r!.\] Ved å sette de to uttrykkene for \(_nP_n\) lik hverandre og løse med hensyn på \( v\) får vi \[v = \frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_r} = \binom{n}{n_1, n_2, \ldots, n_r}.\]

Kommentar

Man bør merke seg at man i dette teoremet antar at gruppene er identifiserbare, for eksempel ved at de er nummerert fra \(1\) til \(r\). Dette innbærer for eksempel at dersom man ønsker å dele de \(n=4\) elementene \(a\), \(b\), \(c\) og \(d\) inn i \(r=2\) grupper med \(n_1=n_2=2\) elementer i hver gruppe, så vil en gruppering med gruppe 1 lik \(\{a,b\}\) og gruppe 2 lik \(\{c,d\}\) regnes som en annen gruppeinndeling enn grupperingen med gruppe 1 lik \(\{c,d\}\) og gruppe 2 lik \(\{a,b\}.\)

Spesialtilfelle: Inndeling i to grupper

Et viktig spesialtilfelle av denne telleregelen får vi ved å sette \( r=2\). Vi får da at antall mulige grupperinger av \( n\) elementer i to grupper med \( n_1\) elementer i gruppe 1 og \( n_2=n-n_1\) elementer i gruppe 2 er \[\binom{n}{n_1, n-n_1} = \frac{n}{n_1!\cdot (n-n_1)!} = \binom{n}{n_1}.\]