Kombinationer – räkna ut nCr

Vad är en kombination?

En kombination är ett urval där ordningen inte spelar roll. Väljer du två glassmaker, choklad och vanilj, är det samma urval som vanilj och choklad. Antalet sätt att välja $k$ saker bland $n$ kallas binomialkoefficienten och skrivs $C(n,k)$. Den läses "n över k" och kallas på räknaren nCr.

Motsatsen är en permutation, där ordningen spelar roll. Guld, silver och brons till tre löpare är en permutation, eftersom det är skillnad på vem som vinner. Att plocka ut tre löpare till ett stafettlag utan bestämd ordning är en kombination.

Formeln och varför den stämmer

$C(n,k)=\frac{n!}{k!·(n-k)!}$

Tänk först som om ordningen spelade roll. Första valet kan göras på $n$ sätt, nästa på $n-1$ och så vidare, totalt $n·(n-1)·...·(n-k+1)$ sätt. Men varje urval av $k$ saker har då räknats en gång för varje ordning det kan stå i, och de är $k!$ stycken. Därför delar man med $k!$. Utropstecknet betyder fakultet, produkten av alla heltal från 1 upp till talet. Det räknar fakultetskalkylatorn ut.

Några egenskaper är bra att känna till:

• Symmetri: $C(n,k)=C(n,n-k)$. Att välja 3 av 10 som får följa med är samma sak som att välja de 7 som stannar hemma.
• $C(n,0)=C(n,n)=1$. Det finns ett sätt att välja ingenting och ett sätt att välja allt.
• Talen $C(n,k)$ bildar Pascals triangel, där varje tal är summan av de två närmast ovanför.

Räknade exempel

Två av fem: $C(5,2)=\frac{5·4}{2}=10$. Om ordningen hade spelat roll hade det blivit 20, alltså dubbelt så många, eftersom varje par kan stå i två ordningar.

Lotto, 7 nummer av 35: $C(35,7)=\frac{35·34·33·32·31·30·29}{7!}$ = 6 724 520. Chansen att pricka rätt rad med en enda rad är alltså 1 på 6 724 520. Skulle ordningen på dragningen räknas blir det 33 891 580 800 möjligheter, men i Lotto spelar ordningen ingen roll. Jämförelser mellan olika spel finns i lotterikalkylatorn.

En pokerhand är 5 kort av 52. Antalet möjliga händer är $C(52,5)$ = 2 598 960. Det är utgångspunkten för alla sannolikheter i poker, som kortlekskalkylatorn visar för varje hand.

Kombinationer med upprepning

Ibland får samma sak väljas flera gånger, som när du tar tre kulor glass och gärna får ta två av samma smak. Då gäller $C(n+k-1,k)$. Med 10 smaker och 3 kulor blir det $C(12,3)$ = 220 olika bägare. Formeln kommer från ett knep där man ställer kulorna på rad och sätter in $n-1$ skiljeväggar mellan smakerna. Varje bägare motsvarar ett sätt att placera väggarna bland kulorna.

Vanliga fel

• Att använda kombinationer när ordningen spelar roll. Fråga dig om "A sedan B" är något annat än "B sedan A". Är svaret ja behöver du permutationer.
• Att glömma dela med $k!$ och få ett svar som är många gånger för stort.
• Att läsa "n över k" som bråket n/k. Det är inte ett bråk utan ett antal.
• Att räkna med upprepning när varje sak bara finns en gång, som lottnummer.

Typiska uppgifter

Hur många matcher spelas om 16 lag möter varandra en gång? Varje match är ett par lag där ordningen inte spelar roll, så svaret är $C(16,2)$ = 120. Samma räkning ger antalet handskakningar när alla i ett rum hälsar på alla.

Hur många olika pizzor kan du göra med 3 av 8 pålägg? $C(8,3)$ = 56. Hur många pizzor man sedan har råd med räknar pizzakalkylatorn ut.

En vanlig provuppgift kombinerar två urval: en kommitté med 2 kvinnor av 6 och 3 män av 5. Varje del räknas för sig och sedan multipliceras de, eftersom varje val av kvinnor kan kombineras med varje val av män: $C(6,2)·C(5,3)=15·10=150$.

Uppgifter med "minst" löses ofta via motsatsen. Ska en grupp på 4 väljas ur en klass med 15 flickor och 10 pojkar, och minst en pojke ska vara med, räknar man alla grupper och drar bort de grupper som bara består av flickor: $C(25,4)-C(15,4)=\mathrm{12 650}-\mathrm{1 365}=\mathrm{11 285}$. Att i stället räkna fallen en, två, tre och fyra pojkar var för sig ger samma svar men tar betydligt längre tid och ger fler chanser att räkna fel.

Kombinationer används också för att räkna sannolikheter. Chansen att få exakt 2 ess på en hand med 5 kort är antalet gynnsamma händer delat med alla händer: $\frac{C(4,2)·C(48,3)}{C(52,5)}$. Samma tanke ligger bakom binomialfördelningen, där $C(n,k)$ räknar på hur många sätt $k$ lyckade försök kan fördela sig bland $n$. Räknat ut blir det $\frac{6·\mathrm{17 296}}{\mathrm{2 598 960}}\approx \mathrm{0,0399}$, alltså knappt 4 %. Grunderna i sannolikhetslära finns i sannolikhetskalkylatorn, och för tärningsfrågor finns tärningskalkylatorn.

Kombination eller inte? Tre frågor att ställa

Det svåraste i kombinatorik är ofta att avgöra vilken formel som gäller. Tre frågor räcker i de flesta uppgifter:

1. Spelar ordningen roll? Ja ger permutationer, nej ger kombinationer.
2. Får samma sak väljas flera gånger? Ja ger formlerna med upprepning.
3. Består uppgiften av flera oberoende val? Då multipliceras antalet sätt för varje val, enligt multiplikationsprincipen.

En kod till ett hänglås med tre siffror är egentligen en permutation med upprepning, ${10}^3=1000$ möjligheter, eftersom 1-2-3 och 3-2-1 är olika koder. En hand i ett kortspel är en kombination utan upprepning, eftersom samma kort inte kan dras två gånger och korten sorteras på handen ändå. En glassbägare är en kombination med upprepning.

Pascals triangel

Skriver man upp $C(n,k)$ rad för rad, med $n=0$ överst, får man Pascals triangel. Rad 5 är 1, 5, 10, 10, 5, 1. Varje tal är summan av de två ovanför, eftersom ett urval av $k$ bland $n$ antingen innehåller ett visst element eller inte: $C(n,k)=C(n-1,k-1)+C(n-1,k)$. Summan av en hel rad är $2^n$, vilket är antalet sätt att välja vilken delmängd som helst. För rad 5 blir det 32. Stapeldiagrammet i kalkylatorn visar just en sådan rad, och formen liknar en klocka när $n$ växer.

Stora tal

Antalet kombinationer växer mycket snabbt. Att välja 50 av 100 kan göras på ungefär ${10}^{29}$ sätt. Kalkylatorn räknar exakt med heltal så långt det går och visar svaret i grundpotensform när det blir för långt att läsa.

Så gör du på räknaren

• Använd funktionen nCr, som på många räknare ligger under SHIFT eller i en meny för sannolikhet. Skriv 35 nCr 7 = och svaret blir 6 724 520.
• Saknas nCr: räkna n! ÷ (k! × (n − k)!), men det fungerar bara så länge n! inte blir för stort för räknaren.
• Bättre för stora n: multiplicera de k största faktorerna och dela med k!.

Fler kalkylatorer om urval och slump finns bland kalkylatorerna för sannolikhet och kombinatorik och på matematiksidan.