Kombinatorikk: Ikke-ordnet utvalg, trekning uten tilbakelegging

Regneregel

Anta en urnemodell og at vi har \(n\) kuler i urna. På hvor mange måter kan vi da trekke \(r\) kuler når vi trekker kuler uten tilbakelegging og ikke tar hensyn til i hvilken rekkefølge kulene trekkes ut, kun hvilke kuler som blir trukket ut. Vi kan finne et generelt svar på dette spørsmålet ved å anvende den generelle multiplikasjonssetningen.

Ikke-ordnet utvalg, trekning uten tilbakelegging

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

Ikke-ordnet utvalg, trekning uten tilbakelegging

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 \[v = \frac{n!}{r! \cdot (n-r)!} = \binom{n}{r}.\]

Kommentarer

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