Permutation (ordnet stikprøve) er en metode i kombinatorik, hvor rækkefølgen betyder noget.

Det modsatte er kombinationer, hvor rækkefølgen er ligegyldig.

 

Når vi udtrækker elementer, kan det ske uden tilbagelægning eller med tilbagelægning:

 

Uden tilbagelægning:

Et element kan kun bruges én gang. Hvis du fjerner en kugle fra en pose og ikke lægger den tilbage, kan den ikke trækkes igen.

 

Med tilbagelægning:

Et element kan bruges flere gange. Hvis du fjerner en kugle fra en pose men lægger den tilbage, kan den trækkes igen.

 

Når vi taler om permutationer (ordnede stikprøver), skelner vi derfor mellem om vi vælger uden tilbagelægning eller med tilbagelægning.

 

 

Ordnet stikprøve uden tilbagelægning

Ved et fodboldstævne med 6 hold skal der findes en 1., 2. og 3. plads.

 

Hvor mange måder kan medaljerne fordeles?

 

Her er stikprøven ordnet, fordi det betyder noget hvilket hold der bliver nr. 1, 2 og 3.

Den er også uden tilbagelægning, fordi et hold ikke kan vinde mere end en placering.

 

$$ \large P(n,r) = \frac{n!}{(n-r)!} $$

$$ \large P(6,3) = \frac{6!}{(6-3)!} $$

$$ \large P(6,3) = \frac{6!}{3!} $$

$$ \large P(6,3) = \frac{720}{6} $$

$$ \large Permutationer\ = 120 $$

 

Der er altså 120 mulige fordelinger af medaljer.

 

 

Fuld permutation

I medalje-eksemplet valgte vi kun en delmængde af holdene, hvor \( \large r < n \).

Man kan også have en fuld permutation, hvor alle elementer indgår. I det tilfælde er:

 

$$ \large P(n,n) = n! $$

 

Eksempel: Alle 6 hold skal stilles på række:

 

$$ \large 6! = 720 $$

 

Der er altså 720 mulige rækker.

 

 

Ordnet stikprøve med tilbagelægning

Hvis du skal vælge en kode til din cykellås med 4 cifre, er der 10 mulige tal (0-9) ved hvert valg.

Du kan godt vælge \( \large 5555 \), fordi det er med tilbagelægning. Det samme tal må bruges flere gange.

Rækkefølgen betyder også noget: \( \large 1234 \) er ikke det samme som \( \large 4321 \).

 

Du skal vælge 4 tal, og der er 10 muligheder (0-9) hver gang.

 

$$ \large Permutationer\ = n^r $$

$$ \large Permutationer\ = 10^4 $$

$$ \large Permutationer\ = 10.000 $$

 

Der er altså 10.000 mulige koder.

 

 

Opsummering

En permutation er en ordnet stikprøve, hvor rækkefølgen har betydning.

 

• Uden tilbagelægning: Et element kan kun bruges én gang. Eksempel: medaljefordeling i sport.
• Med tilbagelægning: Et element kan bruges flere gange. Eksempel: pinkoder.
• Fuld permutation: Alle elementer indgår, og antallet er \( \large n! \).

 

Permutationer bruges til at tælle mulige rækkefølger, og de vokser meget hurtigt i antal selv for små værdier af \( \large n \).