Kombinatorikk/telleregler

I en uniform sannsynlighetsmodell har vi at sannsynligheten for en hendelse A er \[ P(A) = \frac{\text{antall gunstige utfall}}{\text{antall mulige utfall}}, \] der «antall gunstige utfall» er antall enkeltutfall i hendelsen A og «antall mulige utfall» er totalt antall enkeltutfall i utfallsrommet. Unntatt i svært enkle situasjoner vil både antall gunstige og antall mulige utfall være svært store, og det er dermed ikke hensiktsmessig å finne disse ved å telle antall enkeltutfall. Til bruk i slike situasjoner finnes det en del telleregler som relativt enkelt gir antall enkeltutfall. De viktigste av disse reglene beskrives på denne siden.

Sentrale begreper

Trykk på det grå feltet for mer informasjon om temaet.

Multiplikasjonssetningen

Teorem: Hvis en operasjon kan gjøres på \( n_1\) måter, og for hver av disse kan en annen operasjon gjøres på \( n_2\) måter, og for hver kombinasjon av disse operasjonene kan en tredje operasjon gjøres på \( n_3\) måter, \(\ldots\), og for hver kombinasjon av disse \( p-1\) operasjonene kan en \(p\)'te operasjon gjøres på \(n_p\) måter, kan de \( p\) operasjonene kombineres på \[ n_1\cdot n_2\cdot n_3 \cdot\ldots\cdot n_p \] måter.

Kommentar: Vi kan med fordel merke oss at vi i denne setningen kun gjør antagelser for hvor mange måter de forskjellige operasjonene kan utføres på. For eksempel antar vi ikke at de \( n_3\) måtene den tredje operasjonene kan utføres på er de samme uansett hva de to første operasjonene var. Det viktige er kun at antall mulige måter den tredje operasjonen kan gjøres på, er den samme for alle kombinasjoner av de to første operasjonene.

Relevante kapitler: 2.3
Relevante videoer:
\(\ \ \ \)Eksamen desember 2012, oppgave 2a (10:00, Mette Langaas).
Relevante oppgaver:
\(\ \ \ \)Eksamen mai 2014, oppgave 1a (b,n,e).
\(\ \ \ \)Eksamen desember 2013, oppgave 1a (b,n,e).
\(\ \ \ \)Eksamen august 2013, oppgave 4 (b,n,e).
\(\ \ \ \)Eksamen desember 2012, oppgave 1a (b,n,e).

Urnemodell

Vi vil ofte kunne bestemme antall gunstige og antall mulige utfall i en uniform sannsynlighetsmodell ved å observere at situasjonen vi er interessert i er ekvivalent med hva vi har i en urnemodell.

I en urnemodell antar vi at vi har en urne med \( n\) kuler. Alle ballene er identifiserbare, for eksempel ved at de er nummererte fra \( 1\) til \( n\). Vi antar så at vi trekker \( r\) kuler fra urna og registrerer hvilke kuler vi har trukket ut. Ballene kan trekkes «med tilbakelegging» eller «uten tilbakelegging». Hvis de trekkes med tilbakelegging betyr dette at en ball som er trukket ut legges tilbake i urna før neste ball trekkes. Dermed kan samme ball trekkes ut flere ganger. Dersom vi trekker uten tilbakelegging vil en ball som er trukket ut ikke legges tilbake i urna, slik at denne ballen ikke kan trekkes ut flere ganger. Det er også vanlig å se på to måter å registrere hvilke kuler som er trukket ut. Hvis vi registrerer både hvilke kuler som blir trukket ut og i hvilken rekkefølge de trekkes ut får vi det som kalles et «ordnet utvalg». Alternativet er at vi ikke bryr oss om rekkefølgen ballene blir trukket ut, og dermed kun registrere hvilke kuler som er blitt trukket ut. Dette kalles et «ikke-ordnet utvalg». Ved å kombinere hver av de to måtene for å trekke kuler med hver av de to måtene å registrere hva vi har trukket ut kan vi dermed definere fire situasjoner,

ordnet utvalg, trekning med tilbakelegging,
ordnet utvalg, trekning uten tilbakelegging,
ikke-ordnet utvalg, trekning med tilbakelegging,
ikke-ordnet utvalg, trekning uten tilbakelegging,

og for hver av disse fire situasjonene kan vi spørre oss hvor mange resultater, eller utfall, som er mulig. Tre av disse fire situasjonene diskuteres på denne siden.

Relevante kapitler: 2.3
Relevante videoer:
\(\ \ \ \)Kombinatorikk (28:23, Håkon Tjelmeland)
\(\ \ \ \)Eksamen desember 2012, oppgave 2a (10:00, Mette Langaas).
Relevante oppgaver:
\(\ \ \ \)Eksamen mai 2014, oppgave 1a (b,n,e).
\(\ \ \ \)Eksamen desember 2013, oppgave 1a (b,n,e).
\(\ \ \ \)Eksamen august 2013, oppgave 4 (b,n,e).
\(\ \ \ \)Eksamen desember 2012, oppgave 1a (b,n,e).

Ordnet utvalg, trekning med tilbakelegging, \( n^r\)

Teorem: Betrakt en urnemodell der vi trekker kulene med tilbakelegging og registrerer både hvilke kuler vi trekker ut og rekkefølgen på disse (ordnet utvalg). Hvis det er \( n\) kuler i urna og vi trekker ut \( r\) kuler finnes det \[ n^r \] mulige trekninger eller utfall.

Bevis

For å bevise resultatet kan vi benytte muliplikasjonssetningen. Det finnes \( n\) mulige resultater i den første trekningen, et mulige resultat for hver kule i urna. I og med at vi trekker med tilbakelegging finnes for hvert mulig resultat i den første trekningen også \( n\) mulige resultater i den andre trekningen, igjen et mulig resultat for hver av de \( n\) kulene i urna. For den tredje trekningen blir det tilsvarende, for hvert mulig resultat av de to første trekningene finnes det \( n\) mulige resultat i den tredje trekningen. For de resterende trekningene blir situasjonen også den samme, i hver trekning er det \( n\) mulige resultat for hver kombinasjon av resultater i de tidligere trekningene. Fra muliplikasjonssetningen vet vi at vi får totalt antall resultater ved å gange sammen antall resultater for hver operasjon eller trekning, som her gir \( n^r\).

Ordnet utvalg, trekning uten tilbakelegging, \( \frac{n!}{(n-r)!}\)

Teorem: Betrakt en urnemodell der vi trekker kulene uten tilbakelegging og registrerer både hvilke kuler vi trekker ut og rekkefølgen på disse (ordnet utvalg). Hvis det er \( n\) kuler i urna og vi trekker ut \( r\) kuler finnes det \[ _nP_r = \frac{n!}{(n-r)!} \] mulige trekninger eller utfall.

Bevis

For å bevise resultatet kan vi benytte muliplikasjonssetningen. Det finnes \( n\) mulige resultater i den første trekningen, et mulige resultat for hver kule. I og med at vi trekker uten tilbakelegging finnes for hvert mulig resultat i den første trekningen \( n-1\) mulige resultater for den andre trekning, et mulig resultat for hver av de \( n-1\) gjenværende kulene i urna. For hvert mulig resultat av de to første trekningene finnes det \( n-2\) mulige resultat i den tredje trekningen, et mulig resultat for hver av de \( n-2\) resterende kulene i urna etter at to kuler er trukket ut og fjernet. For de resterende trekningene blir situasjonen tilsvarende, ved trekning nummer \( k\) vil \( k-1\) kuler allerede være trukket ut slik at vi har \( n-(k-1)\) mulige resultat for denne trekningen for hver kombinasjon av de \( k-1\) første trekningene. Fra muliplikasjonssetningen vet vi da at vi får totalt antall resultater ved å gange sammen antall resultater for hver operasjon eller trekning, som her blir \[ n\cdot (n-1)\cdot (n-2)\cdot \ldots\cdot (n-(r-1)) = \frac{n\cdot (n-1)\cdot \ldots\cdot (n-r+1)\cdot (n-r)\cdot (n-r-1)\cdot \ldots\cdot 2\cdot 1} {(n-r)\cdot (n-r-1)\cdot \ldots\cdot 2\cdot 1} = \frac{n!}{(n-r)!}. \]

Notasjon: Merk at \( P\)'en i \(_nP_r\) står for antall permutasjoner og ikke for sannsynlighet.

Spesialtilfelle: Et viktig spesialtilfelle av denne telleregelen får vi ved å velge \( r=n\). Vi får da at antall mulige rekkefølger, eller permutasjoner, av \( n\) elementer er \[ _nP_n = n!. \]

Relevante kapitler: 2.3
Relevante videoer:
\(\ \ \ \)Kombinatorikk (28:23, Håkon Tjelmeland)
Relevante oppgaver:

Ikke-ordnet utvalg, trekning uten tilbakelegging, \(\binom{n}{r}\)

Teorem: Betrakt en urnemodell der vi trekker kulene uten tilbakelegging og registrerer kun hvilke kuler vi trekker (ikke-ordnet utvalg), altså ikke rekkefølgen på kulene. Hvis det er \( n\) kuler i urna og vi trekker ut \( r\) kuler finnes det \[ _nC_r = \binom{n}{r} \] mulige trekninger eller utfall.

Bevis

For å bevise dette resultatet starter vi med å se på situasjonen hvor vi har et ordnet utvalg og trekker uten tilbakelegging. For denne situasjonen med et ordnet utvalg vet vi at antall mulige trekninger er \[ _nP_r = \frac{n!}{(n-r)!}. \]

Ved å benytte multiplikasjonssetningen kan vi også utlede en alternativ formel for \(_nP_r\). Vi vil se på antall kombinasjoner av to operasjoner, der den første operasjonen er å trekke uten å registrere rekkefølgen, mens den andre operasjonen er å velge en rekkefølge for de \( r\) kulene som er trukket ut. Vi lar \( v\) betegne antall trekninger når vi ikke registrerer rekkefølgen. Det er altså verdien til \(v\) vi er ute etter. For hver av de \( v\) trekningene uten å registrere rekkefølgen har vi \( ~rP_r=r!\) mulige rekkefølger av de \( r\) kulene som er trukket ut. Multiplikasjonssetningen gir dermed at \[ _nP_r = v \cdot r!. \] Ved å sette de to uttrykkene for \(_nP_r\) lik hverandre og løse med hensyn på \( v\) får vi da \[ \frac{n!}{(n-r)!} = v\cdot r! ~~~~\Rightarrow~~~~ v = \frac{n!}{r! \cdot (n-r)!} = \binom{n}{r}. \]

Kommentar: På norsk er det vanlig å lese \( \binom{n}{r}\) som 'n over r', mens på engelsk er det vanlig å lese den som 'n choose r'.

Relevante kapitler: 2.3
Relevante videoer:
\(\ \ \ \)Kombinatorikk (28:23, Håkon Tjelmeland)
\(\ \ \ \)Eksamen desember 2012, oppgave 2a (10:00, Mette Langaas).
Langaas).
Relevante oppgaver:
\(\ \ \ \)Eksamen mai 2014, oppgave 1a (b,n,e).
\(\ \ \ \)Eksamen desember 2012, oppgave 1a (b,n,e).

Inndeling i grupper, \(\binom{n}{n_1 n_2 \cdots n_r}\)

Teorem: Anta at vi har \( n\) elementer som skal deles inn i \( r\) grupper slik at det blir nøyaktig \( n_1\) elementer i gruppe nummer 1, nøyaktig \( n_2\) elementer i gruppe nummer 2, og så videre opp til nøyaktig \( n_r\) elementer i gruppe nummer \( r\). Det forutsettes at alle elementene skal være i nøyaktig en gruppe slik at \( n_1+n_2+\ldots+n_r = n\). Det finnes da \[ \binom{n}{n_1, n_2, \ldots, n_r} = \frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_r!} \] mulige grupperinger.

Bevis

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, og antall mulige måter å nummerere \( n\) elementer 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 \[ n! = v\cdot n_1!\cdot n_2!\cdot \ldots\cdot n_r! ~~~~\Rightarrow~~~~ v = \frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_r} = \binom{n}{n_1, n_2, \ldots, n_r}. \]

Spesialtilfelle: 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}. \]

Relevante kapitler: 2.3
Relevante videoer:
\(\ \ \ \)Kombinatorikk (28:23, Håkon Tjelmeland)
Relevante oppgaver: