Kombinatorik

Behöver du veta hur många olika uppsättningar om fem kort du kan välja ur en kortlek med 32 kort? Det är precis den sortens uppgift som kombinatoriken löser. Det finns två grundläggande kombinatoriska regler – additionsprincipen och multiplikationsprincipen. Alla andra metoder är bara utvidgningar av de här grundprinciperna.

Additionsprincipen

Additionsprincipen är mycket enkel – den säger att om vi har mängderna A, B som inte har något gemensamt element, så är antalet sätt att välja ett element ur unionen A ∪ B lika med |A| + |B|, dvs. summan av mängdernas storlekar.

Vi börjar med ett lätt exempel. Vi har 6 röda kulor och 8 blå kulor. Vi lägger alla kulor i en urna. Hur många möjligheter har vi totalt när vi drar en kula? Från början hade vi mängden röda kulor, som vi kallar A, och mängden blå kulor, som vi kallar B. Mängderna är disjunkta, dvs. de har ingen gemensam kula. Vi vill dra en kula, så vi har totalt |A| + |B| = 6 + 8 = 14 möjligheter. Det var allt.

Multiplikationsprincipen

Vi har återigen två mängder, K och M. Mängden K innehåller tre kvinnor och mängden M fyra män. Nu undrar vi hur många olika par man–kvinna vi kan bilda av de här mängderna. Det vi försöker göra är att alltid ta en kvinna och para ihop henne med någon man. Antalet par räknar vi ut så här: vi tar en kvinna, Emma, och parar ihop henne i tur och ordning med alla männen. Då får vi 4 olika par, eftersom vi kan para ihop henne med totalt 4 olika män. Samma sak gör vi för de två återstående kvinnorna, och också de bildar 4 nya par var. Det var allt, vi har totalt 4 + 4 + 4 = 12 par.

Vad har vi egentligen gjort? Vi har multiplicerat storleken på de båda mängderna. Vi hade 3 kvinnor och 4 män, så det totala antalet par är 3 · 4 = 12. Därför heter det multiplikationsprincipen. Om vi alltså har två mängder som vi bildar par av, multiplicerar vi helt enkelt antalet element i den ena mängden med antalet element i den andra.

Nedan kan du se att det verkligen stämmer. Här följer alla par som vi kan bilda av 3 kvinnor och 4 män. Varje rad visar möjligheterna för en av kvinnorna och varje kolumn möjligheterna för en av männen. Vi har alltså tre rader och fyra kolumner, totalt rader · kolumner möjligheter.

$$\begin{array}{rcl}& & (K_1,M_1),(K_1,M_2),(K_1,M_3),(K_1,M_4),\\ & & (K_2,M_1),(K_2,M_2),(K_2,M_3),(K_2,M_4),\\ & & (K_3,M_1),(K_3,M_2),(K_3,M_3),(K_3,M_4)\end{array}$$

Lösta exempel

1. Hur många olika tvåsiffriga tal finns det? Hur ser ett tvåsiffrigt tal ut? På första platsen står en av siffrorna 1, …, 9, medan det på andra platsen dessutom kan stå en nolla: 0, …, 9. I den första mängden har vi alltså 9 siffror och i den andra 10. Vi använder multiplikationsprincipen och får slutresultatet: 9 · 10 = 90.

• Hur många olika tresiffriga tal finns det där ingen siffra får förekomma två gånger? På första platsen kan det återigen stå nio siffror, eftersom ett tal inte kan börja med noll. På andra platsen kan alla siffror stå, även noll, men där får inte siffran från första platsen stå, så från de tio möjliga siffrorna drar vi bort ett (om vårt tresiffriga tal till exempel börjar med en fyra är det klart att fyran inte kan stå på andra platsen, eftersom den då skulle förekomma två gånger i talet). På tredje platsen kan återigen alla siffror stå, men där får inte siffran från första eller andra platsen stå. Skälet är återigen detsamma. Om siffran 4 står på första platsen och siffran 7 på andra, kan vi på tredje platsen sätta en siffra ur {0, …, 9} ∖ {4, 7}. Från det totala antalet på tio siffror måste vi dra bort två. Nu multiplicerar vi bara: 9 · 9 · 8 = 648. Det finns alltså totalt 648 sådana tal.
• Vi kastar en vanlig tärning två gånger i rad. Hur många olika utfall kan vi få? I första kastet kan tärningen visa 6 olika utfall. I andra kastet också, så det totala antalet möjligheter är 6 · 6 = 36.
• Vi kastar tärningen två gånger i rad. Hur många olika utfall kan vi få om det första kastet gav ett jämnt tal? I första kastet kom det upp ett jämnt tal, dvs. ett av talen 2, 4, 6, vilket är totalt 3 möjligheter. I andra kastet kan vilket tal som helst komma upp, så totalt har vi 3 · 6 = 18 möjligheter.