Kombinatorik

Kombinationer af fire elementer

Kombinatorik er en matematisk disciplin, hvor man studerer, på hvor mange måder et sæt af elementer fra forskellige grupper kan sættes sammen. Har man fx 3 forretter, 8 hovedretter og 5 desserter, hvor mange forskellige menuer kan man så sætte sammen? Det er spørgsmål som dette, kombinatorikken kan besvare.

I dette eksempel er svaret let at finde. Der er 3 muligheder for forret, og for hver af disse forretter kan man vælge 8 hovedretter, altså 3*8 kombinationer. Og så kan man vælge en ud af 5 desserter for hver af disse 24 kombinationer. Svaret er derfor 24*5 = 120 menuer. Denne beregning er et specialtilfælde af en generel regel indenfor kombinatorikken:

Produktregel:
Hvis en hændelse kan indtræffe på m måder og en anden hændelse kan indtræffe på n måder, så er der m*n måder disse to hændelser kan indtræffe sammen på.

Sumregel:
Hvis en hændelse kan indtræffe på m måder og en anden hændelse kan indtræffe på n måder, så er der der m + n måder én af disse to hændelser kan indtræffe på.

Kombinationer og permutationer

I mange kombinatoriske opgaver er det vigtigt at skelne imellem om man tillægger rækkefølgen af objekter en betydning eller ej. Hvis man fx siger at der er 10 måder at udvælge 2 folketingskandidater ud af 5, så tillægger man ikke rækkefølgen betydning, men hvis man siger at de 5 kandidater kan opstilles på en liste på 120 måder, så har rækkefølgen eller ordningen betydning. I kombinatorik har ordet kombination samme betydning som ordet udvælgelse, og ordet permutation betyder ordning.

Mere formelt betyder K(n,r) det antal måder hvorpå man kan udvælge r objekter ud af en mængde på n forskellige objekter, mens P(n,r) betyder antallet af måder hvorpå man kan udvælge en ordnet mængde på r objekter ud af n forskellige objekter.

Produktreglen medfører at der gælder følgende sammenhæng mellem K- og P-funktionerne:

${\displaystyle P(n,r)=K(n,r)P(r,r)}$

fordi man kan lave en ordnet udvælgelse af r ud af n forskellige objekter ved først at udvælge de r objekter og derefter ordne dem.

K-funktionen må tilfredsstille følgende rekursion:

${\displaystyle K(n,r)=K(n-1,r-1)+K(n-1,r)}$

Dette kan indses på følgende måde: Lad ét af objekterne være mærket på en speciel måde, så det kan kendes fra alle de andre. Man kan da udvælge r objekter sådan at dette objekt enten er med, dvs. vælges på forhånd (det kan gøres på K(n-1,r-1) måder) eller netop ikke er med, dvs. lægges til side (det kan gøres på K(n-1,r) måder). Sumreglen giver herefter formlen.

Disse to beregninger er ganske typiske for tankegangen i kombinatorikken.

At permutere r ud af n objekter er det samme som at anbringe r af de n objekter i afmærkede positioner. Den første position kan fyldes på n måder (man vælger ét ud af n objekter). Den næste position kan herefter fyldes på n – 1 måder (man vælger ét ud af de resterende n – 1 objekter) ..., og den r'te position kan fyldes på n – r + 1 måder (man vælger ét ud af de resterende n – r + 1 objekter). Produktreglen giver da:

${\displaystyle P(n,r)=n(n-1)(n-2)...(n-r+1)}$

Eksempel 1: På hvor mange måder kan man arrangere 2 klodser med forskellige farver ud af en bunke klodser med farverne gul, rød, blå og grøn?

Svar: Der er 4 forskellige farver, og vi skal udtage 2 af dem; svaret er derfor P(4,2) = 4*3 = 12. Man får altså ikke at vide hvilke rækkefølger der er tale om, kun hvor mange der er. Nu er dette eksempel så lille at man kan prøve om svaret passer ved at opregne alle permutationerne, fx sådan her:

{gul,rød},{gul,blå},{gul,grøn},

{rød,gul},{rød,blå},{rød grøn},

{blå,gul},{blå,rød},{blå,grøn},

{grøn,gul},{grøn,rød},{grøn,blå}

hvilket stemmer. Det ændrer intet at der fx er 5 røde og 7 grønne klodser i bunken – det er udelukkende farven der spiller en rolle, for to klodser med samme farve kan ikke skelnes fra hinanden. Slut på eksempel 1.

Da P(r,r) må være lig med

${\displaystyle P(r,r)=r(r-1)(r-2)...(r-r+1)=r!}$ se Fakultet (matematik)

findes endelig, da P(n,r)= K(n,r)P(r,r) som vist ovenfor:

${\displaystyle K(n,r)={P(n,r) \over r!}={n(n-1)(n-2)...(n-r+1) \over r(r-1)(r-2)...2\cdot 1}}$

Eksempel 2: Hvor mange diagonaler er der i en konveks polygon med n kanter?

Svar: En diagonal forbinder to hjørner i polygonen, så det handler om at udtage 2 punkter ud af de n punkter, der er sidernes endepunkter. Det kan gøres på K(n,2) måder. Men n af disse punktpar danner polygonens sider, så svaret er K(n,2) – n. Hvis vi prøver med n = 4, altså en firkant, finder vi K(4,2) – 4 = 4*3/2! – 4 = 6 – 4 = 2, hvilket stemmer med at der er 2 diagonaler i en firkant. For en trekant, der jo ikke har nogle diagonaler, finder vi K(3,2) – 3 = 3*2/2! – 3 = 0. Slut på eksempel 2.

Eksempel 3: Hvad er sandsynligheden for at få 7 rigtige i Lotto?
Svar: De 7 rigtige findes som 1 kombination ud af alle kombinationer. Der er K(36,7) = 8347680 kombinationer med 7 tal ud af 36. Chancen for en 7ér er altså 1 ud af ca. 8 millioner. Slut på eksempel 3.

Ens objekter

Hvis ikke alle objekterne kan skelnes fra hinanden, slår formlerne i det forrige ikke til. Det kan fx være man ønsker at finde alle permutationer af klodserne fra eksempel 1, med 1 gul, 5 røde, 1 blå og 7 grønne klodser. Dette antal permutationer bliver lig med:

${\displaystyle {{14!} \over {1!\cdot 5!\cdot 1!\cdot 7!}}=144144}$ permutationer.

Denne beregning er nemlig et konkret tilfælde af den generelle formel:

${\displaystyle {n!} \over {q_{1}!\cdot q_{2}!\cdot q_{3}!\cdot ...\cdot q_{t}!}}$

som giver antallet af permutationer af n objekter, hvoraf der er q₁ objekter af 1. slags, q₂ objekter af 2. slags, osv. op til q_t objekter af t´te slags. Hvis man kun vil finde antal permutationer af 5 klodser, men forlanger at alle farver skal være repræsenteret, så bliver der

${\displaystyle {{5!} \over {1!\cdot 2!\cdot 1!\cdot 1!}}+{{5!} \over {1!\cdot 1!\cdot 1!\cdot 2!}}=120}$

permutationer.

Hvis antallet af ens objekter af hver slags er uendelig stort taler man om "udtrækning med tilbagelægning" idet denne situation svarer til at man lægger objektet tilbage blandt de mulige udtrækningskandidater hver gang det bliver udtrukket. Antallet af måder at arrangere r objekter ud af n forskellige objekter med tilbagelægning er

${\displaystyle n^{r}}$.

Dette resultat følger direkte af produktreglen fordi der er n muligheder i alle r positioner.

Eksempel 4: Hvad er sandsynligheden for at få 7 rigtige i Joker?
Svar: For hver af de 7 positioner er der 10 muligheder, så der er 10⁷ permutationer. Chancen for at gætte den rigtige permutation er altså 1 ud af 10 millioner. Slut på eksempel 4.

Antallet af kombinationer ved udvælgelse af r objekter ud af n med tilbagelægning er

${\displaystyle K(n+r-1,r)}$

Eksempel 5: Hvor mange udfald er der, hvis man kaster 3 ens terninger?
Svar: Det drejer sig her om at udvælge 3 tal blandt de 6 mulige visninger "med tilbagelægning" dvs. hvis hver visning kan vælges mere end én gang. Det kan gøres på K(6 + 3 – 1,3) = 56 måder. Hvis terningerne har forskellige farver er der 6³ = 216 mulige udfald. Slut på eksempel 5.

Hvis der er q₁ objekter af første slags, q₂ objekter af anden slags, ... ,q_t objekter af t´te slags bliver antallet af kombinationer

${\displaystyle (q_{1}+1)(q_{2}+1)(q_{3}+1)...(q_{t}+1)}$

fordi det q_k´te objekt kan vælges på q_k måder eller ikke vælges. Formlen medfører at man kan vælge ingen objekter på 1 måde, hvilket måske er meget naturligt.

Eksempel 6: Hvor mange divisorer har tallet 6776?
Svar: Primtalsopløsningen af 6776 er 2³ * 7 * 11² og der er derfor (3+1)(1+1)(2+1) = 24 måder at udvælge primfaktorerne på. Men det vil sige at 6776 har 24 divisorer. Slut på eksempel 6.

Ekstern reference

http://mathforum.org/library/topics/combinatorics/

• Wikimedia Commons har flere filer relateret til Kombinatorik