Kombinatorikk

Trenger du å vite hvor mange ulike hender på fem kort du kan velge fra en kortstokk på 32 kort? Det er nøyaktig den typen oppgave kombinatorikk løser. Det finnes to grunnleggende regler i kombinatorikk — addisjonsprinsippet og multiplikasjonsprinsippet. Alle andre fremgangsmåter er bare utvidelser av disse to prinsippene.

Addisjonsprinsippet

Addisjonsprinsippet er veldig enkelt — det sier at hvis vi har mengdene A, B uten felles elementer, er antall mulige måter å velge ett element fra unionen A ∪ B lik |A| + |B|, altså summen av antall elementer i mengdene.

Vi begynner med et lett eksempel. Vi har 6 røde og 8 blå kuler. Vi heller alle kulene i én urne. Hvor mange muligheter har vi til sammen når vi trekker én kule? Mengden av røde kuler kaller vi A, og mengden av blå kuler kaller vi B. Disse mengdene er disjunkte, det vil si at de ikke har noen felles kule. Vi vil trekke én kule, så vi har til sammen |A| + |B| = 6 + 8 = 14 muligheter. Det var alt.

Multiplikasjonsprinsippet

Nå har vi igjen to mengder, K og M. Mengden K inneholder tre kvinner, og mengden M inneholder fire menn. Vi spør: Hvor mange ulike par av typen mann—kvinne kan vi lage fra disse mengdene? Det vi gjør, er å ta én kvinne og la henne få en mann som partner. Antall par finner vi slik: Vi tar én kvinne, Nora, og setter henne sammen med alle mennene etter tur. Da får vi 4 ulike par, fordi vi kan sette henne sammen med 4 ulike menn. Det samme gjør vi for de to andre kvinnene, og de lager også 4 nye par hver. Det er alt, vi har til sammen 4 + 4 + 4 = 12 par.

Hva har vi egentlig gjort? Vi har multiplisert antall elementer i de to mengdene. Vi hadde 3 kvinner og 4 menn, så det totale antallet par er 3 · 4 = 12. Derfor heter det multiplikasjonsprinsippet. Hvis vi har to mengder og lager par av dem, multipliserer vi altså bare antall elementer i den ene mengden med antall elementer i den andre.

Du kan se at dette virkelig stemmer. Under står alle parene vi kan lage av 3 kvinner og 4 menn. Hver rad viser mulighetene for én av kvinnene, og hver kolonne viser mulighetene for én av mennene. Vi har altså tre rader og fire kolonner, til sammen rader · kolonner muligheter.

$$\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øste eksempler

1. Hvor mange ulike tosifrede tall finnes det? Hvordan ser et tosifret tall ut? På første plass står ett av sifrene 1, …, 9, mens null i tillegg kan stå på andre plass: 0, …, 9. I den første mengden har vi 9 sifre, i den andre 10. Vi bruker multiplikasjonsprinsippet og får det endelige resultatet: 9 · 10 = 90.

• Hvor mange ulike tresifrede tall finnes det der ingen siffer får forekomme to ganger? På første plass kan det igjen stå ni sifre, for tallet kan ikke begynne med null. På andre plass kan alle sifrene stå, også null, men der kan ikke stå sifferet som står på første plass, så fra de ti mulige sifrene trekker vi fra ett (hvis det tresifrede tallet vårt for eksempel begynner med fire, er det klart at fire ikke kan stå på andre plass, for da ville det forekomme to ganger i tallet). På tredje plass kan alle sifrene igjen stå, men ikke sifferet som står på første eller andre plass. Grunnen er den samme. Hvis sifferet 4 står på første plass og sifferet 7 på andre, kan vi sette ett siffer fra {0, …, 9} ∖ {4, 7} på tredje plass. Fra de ti sifrene må vi altså trekke fra to. Nå må vi bare multiplisere 9 · 9 · 8 = 648. Det finnes altså 648 slike tall.
• Vi kaster en vanlig terning to ganger etter hverandre. Hvor mange ulike utfall kan vi få? I det første kastet kan terningen vise 6 ulike resultater. I det andre kastet også, så det totale antallet muligheter er 6 · 6 = 36.
• Vi kaster en terning to ganger etter hverandre. Hvor mange ulike utfall kan vi få hvis vi fikk et partall i det første kastet? I det første kastet kom det et partall, altså ett av tallene 2, 4, 6, som er 3 muligheter. I det andre kastet kan det komme hvilket som helst tall, så vi har til sammen 3 · 6 = 18 muligheter.