Kombinatorikk: 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 tar hensyn til rekkefølgen kulene trekkes ut? Vi kan finne et generelt svar på dette spørsmålet ved å anvende den generelle multiplikasjonssetningen.

Ordnet utvalg, trekning uten tilbakelegging

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

Ordnet utvalg, trekning uten tilbakelegging

For å bevise resultatet kan vi benytte multiplikasjonssetningen. 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 multiplikasjonssetningen vet vi da at vi får totalt antall resultater ved å gange sammen antall resultater for hver operasjon eller trekning, som her blir

\[ \begin{align} &n\cdot (n-1)\cdot (n-2)\cdot \ldots\cdot (n-(r-1))\\ &= \frac{n\cdot \ldots\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)!}. \end{align} \]

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!.\]