Ordnet udvælgelse

Ordnet udvælgelse bruger vi, når vi vælger et bestemt antal objekter fra en mængde, og rækkefølgen, som vi vælger objekterne i, har betydning.

Udledning af formlen

Vi begynder med en typisk opgave om ordnet udvælgelse: i en lille landsby holdes der hvert år en konkurrence i at spise æbleskiver. Til finalen har i alt syv fedtede konkurrenter kvalificeret sig. Beregn, hvor mange muligheder der i alt er for, hvordan de syv deltagere kan besætte de tre første pladser.

Det er vigtigt at være opmærksom på, at rækkefølgen i dette eksempel har betydning. Hvis vi fx ved, at Noah, William og Oscar kommer på de tre første pladser, giver netop disse tre i alt seks forskellige placeringer:

• Noah, William, Oscar;
• Noah, Oscar, William;
• William, Noah, Oscar;
• William, Oscar, Noah;
• Oscar, Noah, William;
• Oscar, William, Noah.

Det er alle forskellige placeringer, og vi vil beregne, hvor mange forskellige placeringer vi i alt kan sammensætte, når der er 7 deltagere.

Til det bruger vi multiplikationsprincippet. Vi siger, at vi vælger tripler af formen (x₁, x₂, x₃), hvor x₁ er deltageren, der blev nummer et, osv. Hvilke deltagere kan vi sætte ind for x₁? Dem alle, altså kan vi sætte 7 deltagere ind for x₁. Hvilke kan vi sætte ind for x₂? Alle undtagen den, vi allerede har sat ind på førstepladsen, så for x₂ kan vi sætte 7 − 1 = 6 deltagere ind. For x₃ kan vi så sætte de deltagere ind, som ikke står på første eller anden plads, så vi har 7 − 2 = 5 muligheder. Vi anvender multiplikationsprincippet og får det samlede antal muligheder: 7 · 6 · 5 = 210.

Vi kan bemærke, at hvis vi vil kende antallet af alle muligheder for de første 4 pladser, kan vi for x₄ sætte 7 − 3 = 4 deltagere ind, så det samlede antal muligheder bliver 7 · 6 · 5 · 4 = 840. Hvad kan vi udlede af det?

Hvis vi har en mængde med n elementer (her i eksemplet 7 spisere), og vi vælger 3 elementer, hvor rækkefølgen har betydning, så er resultatet lig med n · (n − 1) · (n − 2). På førstepladsen kan alle komme, på den næste én færre osv. Heraf kan vi udlede en generel formel for, når vi vælger r elementer fra en mængde med n elementer: antallet af muligheder bliver lig med n · (n − 1) · (n − 2) · … · (n − r + 1).

Denne formel omskriver vi yderligere ved hjælp af fakultet. Når vi ser på, hvordan syv fakultet ser ud: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, og hvordan vi beregnede antallet af alle medaljeplaceringer 7 · 6 · 5, ser vi en vis lighed. Vi skal bare af med den sidste del, dvs. vi skal dividere 7! med 4 · 3 · 2 · 1, så der kun er 7 · 6 · 5 tilbage. Og hvad er udtrykket 4 · 3 · 2 · 1 lig med? Det er lig med 4!.

Vi kan således skrive, at hvis vi har en mængde med n elementer og vælger i alt r elementer, hvor rækkefølgen har betydning, så har vi i alt

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

muligheder. Når vi sætter tallene fra æbleskivekonkurrencen ind i formlen:

$$P(7,3)=\frac{7!}{(7-3)!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{4\cdot 3\cdot 2\cdot 1}=7\cdot 6\cdot 5=210.$$

Beregner

Følgende beregner finder antallet af ordnede udvælgelser for givne n og r.

Løste eksempler

1. Vi bliver ved æbleskivekonkurrencen. Hvordan ville antallet af mulige medaljeplaceringer ændre sig, hvis vi vidste, at Lucas Holm er kommet til konkurrencen, og han er en mester, som altid vinder? Dvs. hvor mange forskellige medaljeplaceringer findes der, hvis vi har 7 deltagere, og Lucas helt sikkert vinder?

Det er igen en enkel ordnet udvælgelse, førstepladsen er sikker, og af de resterende 6 deltagere skal vi bestemme, hvordan de kan besætte anden- og tredjepladsen. Vi vælger således 2 elementer fra en mængde med 6 elementer, hvilket fører til

$$P(6,2)=\frac{6!}{(6-2)!}=30$$

2. Engang for længe siden, da Lucas Holm endnu ikke var sådan en mester, kom han regelmæssigt blandt de tre første. Hvor mange forskellige medaljeplaceringer findes der, hvis vi har 7 deltagere, og Lucas helt sikkert får en medalje?

   Dette eksempel adskiller sig fra det forrige ved, at vi ikke ved, hvilken plads Lucas fik; han kunne være blevet nummer to eller endda nummer tre, hvilket han stadig skammer sig over. Derfor skal vi i alt beregne tre forskellige ordnede udvælgelser: i tilfældet, hvor Lucas vandt, dernæst hvis Lucas fik sølvmedaljen, og til sidst bronzemedaljen. Men hver gang er der kun to pladser tilbage, hvor en anden kan komme. Hvis Lucas fx var nummer to, kunne de andre deltagere blive placeret enten på førstepladsen eller på tredjepladsen. Vi beregner altså igen en ordnet udvælgelse af to elementer ud af seks, vi skal blot beregne den tre gange, for Lucas' tre forskellige placeringer. Antallet af alle placeringer er således lig med:

   $$3\cdot P(6,2)=3\cdot \frac{6!}{(6-2)!}=3\cdot 30=90$$

   Læg mærke til, at den tre foran den ordnede udvælgelse kan skrives som P(3, 1), for i virkeligheden vælger vi ét element (én bestemt placering) fra en mængde med tre elementer (tre medaljepladser).

3. På en skole er der i alt 20 lærere. Snart skal der holdes studentereksamen, og der skal sammensættes et udvalg med denne sammensætning: én formand, én rar bisidder og én streng bisidder. Hvor mange muligheder er der i alt?

   Det første spørgsmål, vi skal besvare, er, om rækkefølgen har betydning — ja, det har den, tre lærere kan igen fordeles på seks forskellige måder. Nu er det enkelt — vi vælger en ordnet udvælgelse af 3 elementer ud af 20:

   $$P(20,3)=\frac{20!}{17!}=6840.$$

4. Hvor mange trecifrede tal kan vi sammensætte af cifrene {0, 1, 2, 3, 4, 5}, hvis intet ciffer må gentages?

   Har rækkefølgen betydning? Ja, 123 er et andet tal end 321. Hvor mange forskellige tripler findes der? Det er en enkel ordnet udvælgelse af 3 elementer ud af 6:

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

   Men vi skal stadig trække de udvælgelser fra, der har nul på første plads, for 012 er ikke et trecifret tal. Spørgsmålet lyder nu — hvor mange forskellige tripler findes der, som begynder med nul? I så fald skifter cifrene kun på de to resterende pladser (triplerne har formen (0, x₂, x₃)), så vi søger, hvor mange forskellige par vi kan danne ved hjælp af tallene {1, 2, 3, 4, 5}. Det er igen enkelt: P(5, 2) = 5!/3! = 20. Der findes altså 20 tripler, som begynder med nul.

   Det samlede antal trecifrede tal, som er sammensat af cifrene {0, 1, 2, 3, 4, 5}, er således 120 − 20 = 100.

5. Hvor mange forskellige trecifrede tal kan vi sammensætte af cifrene {1, 2, 3, 4, 5}, hvis intet ciffer må gentages, og det resulterende tal skal være ulige?

   Rækkefølgen har betydning, for 123 er et andet tal end 321. Vi sammensætter et trecifret tal, som er ulige, hvilket betyder, at der på de to første pladser kan stå et vilkårligt ciffer, men på den sidste skal der stå et af cifrene {1, 3, 5}. Først beregner vi antallet af alle tripler, som vi kan sammensætte af fem cifre: P(5, 3) = 5! / 2! = 60.

   Hvert ciffer vil forekomme lige ofte på den sidste plads, så hvis vi har 5 cifre, vil hvert ciffer forekomme på den sidste plads 60 / 5 = 12 gange. Vi har tre cifre {1, 3, 5}, som kan optræde på den sidste plads, så vi har 12 forskellige tal, der ender på 1, 12 tal, der ender på 3, og 12 tal, der ender på 5. Vi bruger additionsprincippet og får i alt 12 + 12 + 12 = 36 muligheder.

6. Bestem x, hvis du ved, at P(x, 2) = 72. Med andre ord: fra en mængde af størrelse x vælger vi par, og vi ved, at vi kan vælge i alt 72 forskellige par. Hvor stor var mængden, som vi valgte parrene fra? Vi skriver det ud:

   $$P(x,2)=\frac{x!}{(x-2)!}=72$$

   Dernæst omskriver vi:

   $$\begin{array}{rcl}\frac{x!}{(x-2)!}& =& 72\\ \frac{x\cdot (x-1)\cdot (x-2)!}{(x-2)!}& =& 72\\ x\cdot (x-1)& =& 72\\ x^2-x& =& 72\\ x^2-x-72& =& 0\end{array}$$

   Det er nu en klassisk andengradsligning, så vi løser den ved hjælp af diskriminanten, eller vi kan omskrive ligningen til formen

   $$(x+8)\cdot (x-9)=0$$

   hvorfra vi allerede kan aflæse løsningerne: x₁ = −8 og x₂ = 9. Den negative løsning interesserer os ikke, for en mængde kan ikke have en negativ størrelse, så den oprindelige ligning har løsningen x = 9, mængden havde ni elementer.