Permutationer och kombinationer: varför ordningen ändrar antalet

Fem personer anmäler sig frivilligt till ett projekt. Du behöver en kapten och en vicekapten. Kaptenen kan väljas på fem sätt och vicekaptenen därefter på fyra. Det finns tjugo fördelningar.

Ändra nu en mening: du behöver en kommitté med två personer utan skilda roller. Samma fem personer ger tio kommittéer. Personerna ändrades inte. Det som ändrades var definitionen av ett resultat.

Permutationer och kombinationer räknar resultat utan att lista alla möjligheter. Formlerna blir begripliga när du bestämmer vilken information resultatet behåller. Här bygger vi först det beslutet och härleder sedan notationerna.

Börja med positioner, inte en formel

Föreställ dig två tomma rutor märkta kapten och vicekapten. Den första har fem möjliga personer. När den fyllts återstår fyra för den andra. Varje första val har fyra fortsättningar:

$$5 \times 4 = 20$$

Detta är multiplikationsprincipen. Om varje alternativ i ett steg har lika många möjliga fortsättningar multiplicerar du stegens antal. Se det som ett träd med fem grenar som var och en delar sig i fyra.

Etiketterna spelar roll. Alex som kapten och Bea som vicekapten skiljer sig från Bea som kapten och Alex som vicekapten. Samma personer står på olika positioner. Det är ett ordnat val, en permutation.

En kommitté har inga märkta positioner. Alex, Bea och Bea, Alex beskriver samma grupp. Om tjugo fördelningar används för kommittéer räknas varje grupp två gånger.

Bytestestet visar om ordningen spelar roll

Fråga: blir resultatet annorlunda om jag byter plats på två valda objekt?

För en prispall, ja. Guld och silver är olika resultat. För pizzapålägg, vanligen nej. Svamp plus oliver är samma val som oliver plus svamp.

Frågan gäller modellen, inte substantivet. En uppgift kan välja tre böcker att köpa, där ordningen ignoreras, eller ordna tre böcker på en hylla, där den registreras. Ordet ”böcker” avgör inte formeln.

Skriv ett exempel på ett resultat före beräkningen. ”Kapten Alex, vicekapten Bea” innehåller roller. ”Gruppen med Alex och Bea” gör det inte. Detta steg förhindrar fler fel än en längre formelsamling.

Situation	Vad resultatet registrerar	Modell
Dela ut guld, silver och brons	Person på varje plats	Ordnat, utan upprepning
Välja tre kommittémedlemmar	Endast medlemskap	Oordnat, utan upprepning
Skapa en fyrsiffrig kod	Siffra på varje position	Ordnat, upprepning kan tillåtas
Välja flera glasskulor	Antal av varje smak	Oordnat, upprepning kan tillåtas

De två sista raderna kräver också frågan om upprepning. Avgör inte modellen enbart från ordningen.

Fakulteter räknar fullständiga ordningar

Ställ fyra olika böcker i rad. För första platsen finns fyra val, sedan tre, två och ett:

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

Utropstecknet betyder fakultet och förkortar den fallande produkten. För ett icke-negativt heltal $n$ räknar fakulteten ordningar av alla $n$ olika objekt.

Varför är $0! = 1$? Det finns en tom ordning. Du gör ingenting och den är färdig. Värdet håller också $1! = 1 \times 0!$ konsekvent.

Läs inte fakultet som upprepad addition eller potens. Fyra fakultet är tjugofyra; fyra upphöjt till fyra är tvåhundrafemtiosex. I en fakultet minskar valen eftersom objekt inte återanvänds. I en potens förblir de lika många.

Permutationer stoppar produkten tidigt

Av sju löpare vill du bara veta de tre första, utan delade placeringar. Det finns sju val för första, sex för andra och fem för tredje:

$$P(7,3) = 7 \times 6 \times 5 = 210$$

Hur de återstående fyra slutar spelar ingen roll. Att multiplicera till ett besvarar en annan fråga.

För $r$ ordnade positioner fyllda med $n$ olika objekt utan upprepning:

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

Nämnaren förkortar fakultetens oanvända svans. Sju fakultet delat med fyra fakultet lämnar sju gånger sex gånger fem.

Formeln förutsätter $0 \le r \le n$ och olika tillgängliga objekt. Ändras antagandena, återgå till rutorna i stället för att tvinga in talen i uttrycket.

Kombinationer tar bort dubbla ordningar

Välj tre av sju personer till en kommitté. Det ordnade antalet är 210, men behandlar olika ordningar av samma trio som olika svar.

Trion Alex, Bea och Chen kan listas i sex ordningar: ABC, ACB, BAC, BCA, CAB och CBA. Varje trio förekommer sex gånger eftersom $3! = 6$.

Dividera med antalet dubbla ordningar:

$$\binom{7}{3} = \frac{210}{6} = 35$$

Generellt:

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

Det läses ”n över r”. Den första divisionen tar bort oanvända objekt, den andra ordningar som inte längre skiljs åt.

Symmetrin $\binom{7}{3} = \binom{7}{4}$ är användbar. Att välja de tre som deltar avgör också de fyra som inte gör det. Beskrivningarna motsvarar samma beslut.

Upprepning ändrar frågan igen

En fyrsiffrig kod får använda noll till nio på varje position, även först, och siffror får upprepas. Varje ruta har tio val:

$$10^4 = 10000$$

Om siffror inte får upprepas blir antalet:

$$10 \times 9 \times 8 \times 7 = 5040$$

Om uppgiften säger ”fyrsiffrigt tal” i stället för ”kod” utesluts vanligen en inledande nolla. Med upprepning blir det:

$$9 \times 10 \times 10 \times 10 = 9000$$

Tre liknande meningar, tre olika antal. Formeln blev inte opålitlig. Begränsningarna ändrades.

Oordnade val med upprepning, som glasskulor med samma smak, kräver en annan metod. Vanliga kombinationer antar att varje objekt väljs högst en gång. Att se att en välbekant formel inte gäller är ett korrekt första steg.

Arbeta genom beslutet i denna ordning

Skriv först hur ett fullständigt resultat ser ut. Fråga sedan om ordning eller roller skiljer resultat, om objekt kan upprepas och om en position har en särskild begränsning.

Försök lösa tre problem innan du ser svaren:

1. Välj en ordförande och sekreterare bland sex personer, utan dubbla roller.
2. Välj två likställda representanter bland samma sex.
3. Skapa en kod med tre tecken ur fyra symboler, med upprepning.

Det första har $6 \times 5 = 30$ fördelningar. Det andra delar med $2!$ och ger femton par. Det tredje har $4^3 = 64$ koder eftersom alla fyra symboler finns kvar på varje position.

Förklaringen är viktigare än talet. Kan du säga varför ett svar delas med två och ett annat inte, förstår du skillnaden.

Räkning är grunden för sannolikhet

När likformigt sannolika utfall räknas rätt kan sannolikheter bildas genom att jämföra gynnsamma utfall med alla möjliga. Vår intuitiva sannolikhetsguide tar nästa steg. Födelsedagsparadoxen visar hur rätt räkning gör ett överraskande resultat hanterbart.

Håll färdigheten liten: definiera ett utfall, rita positionerna om de finns och förklara varje faktor. Använd Math Zens sannolikhetsövningar för nästa tillämpning och återgå till ett litet exempel när notationerna döljer resonemanget.

En permutation behåller ordningen. En kombination behåller medlemskapet. Division med en fakultet glömmer ordningen utan att räkna samma grupp igen.