Kombinatorik

Har du brug for at vide, hvor mange forskellige hænder med fem kort du kan vælge fra et spil med 32 kort? Det er præcis den slags opgaver, kombinatorikken løser. Der findes to grundlæggende kombinatoriske regler — additionsprincippet og multiplikationsprincippet. Alle andre fremgangsmåder er blot en udvidelse af de to grundlæggende principper.

Additionsprincippet

Additionsprincippet er helt enkelt — det fortæller os, at hvis vi har mængder A, B, som ikke har noget fælles element, så er antallet af måder, hvorpå vi kan vælge ét element fra foreningsmængden A ∪ B, lig med |A| + |B|, altså summen af mængdernes størrelser.

Vi begynder med et let eksempel. Vi har 6 røde kugler og 8 blå kugler. Kuglerne hælder vi ned i én urne. Hvor mange muligheder har vi i alt, når vi trækker én kugle? I begyndelsen havde vi mængden af røde kugler, den kalder vi A, og mængden af blå kugler, den kalder vi B. Mængderne er disjunkte, dvs. de har ingen kugle til fælles. Vi vil trække én kugle, så vi har i alt |A| + |B| = 6 + 8 = 14 muligheder. Det var det hele.

Multiplikationsprincippet

Vi har igen to mængder, K og M. Mængden K indeholder tre kvinder, og mængden M fire mænd. Nu spørger vi, hvor mange forskellige par mand—kvinde vi kan danne af disse mængder? Hvad forsøger vi at gøre — vi tager altid én kvinde og giver hende en mand. Antallet af alle par finder vi sådan: vi tager én kvinde, Emma, og parrer hende efter tur med alle mændene. Det giver 4 forskellige par, fordi vi kan parre hende med i alt 4 forskellige mænd. Det samme gør vi for de to andre kvinder, og de danner også hver 4 par mere. Og det er alt, vi har i alt 4 + 4 + 4 = 12 par.

Hvad har vi egentlig gjort? Vi har ganget størrelserne af de to mængder. Vi havde 3 kvinder og 4 mænd, så det samlede antal par er 3 · 4 = 12. Heraf navnet multiplikationsprincippet. Hvis vi altså har to mængder, som vi danner par af, så ganger vi bare antallet af elementer i den ene mængde med antallet af elementer i den anden.

Du kan desuden selv se, at det virkelig passer. Nedenfor står alle de par, vi kan danne af 3 kvinder og 4 mænd. Hver række viser mulighederne for én af kvinderne, og hver kolonne mulighederne for én af mændene. Vi har således tre rækker og fire kolonner, i alt rækker · kolonner muligheder.

$$\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 forskellige tocifrede tal findes der? Hvordan ser et tocifret tal ud? På første plads står et af cifrene 1, …, 9, mens der på anden plads desuden kan stå nul: 0, …, 9. I den første mængde har vi altså 9 cifre, i den anden 10. Vi bruger multiplikationsprincippet og får det endelige resultat: 9 · 10 = 90.

• Hvor mange forskellige trecifrede tal findes der, hvor intet ciffer må forekomme to gange? På første plads kan der igen stå ni cifre, tallet kan ikke begynde med nul. På anden plads kan der stå alle cifre inklusive nul, men der må ikke stå det ciffer, som står på første plads, så vi trækker én fra de ti mulige cifre (hvis vores trecifrede tal fx begynder med fire, er det klart, at der ikke også kan stå fire på anden plads, for så ville cifferet forekomme to gange i tallet). På tredje plads kan der igen stå alle cifre, men der må ikke stå et ciffer, som står på første eller anden plads. Begrundelsen er den samme. Hvis der står cifferet 4 på første plads og cifferet 7 på anden plads, kan vi på tredje plads sætte ét ciffer fra {0, …, 9} ∖ {4, 7}. Fra det samlede antal på ti cifre skal vi altså trække to. Nu skal vi bare gange 9 · 9 · 8 = 648. I alt findes der altså 648 sådanne tal.
• Vi slår to gange i træk med en almindelig terning. Hvor mange forskellige udfald kan vi få? I første kast kan der komme 6 forskellige udfald på terningen. I andet kast også, så det samlede antal muligheder er 6 · 6 = 36.
• Vi slår to gange i træk med en terning. Hvor mange forskellige udfald kan vi få, hvis vi i første kast slog et lige tal? I første kast kom der et lige tal, altså et af tallene 2, 4, 6, hvilket er i alt 3 muligheder. I andet kast kan der nu komme et hvilket som helst tal, så vi har i alt 3 · 6 = 18 muligheder.