Kombinatorik: permutationer, kombinationer og formler forklaret

Din telefon har en firecifret pinkode, og du har glemt den. Hvor mange gæt skal du bruge for at prøve alle muligheder? Svaret finder du med kombinatorik, og det er mindre mystisk, end ordet lyder. Der findes præcis 10 000 koder, fra 0000 til 9999, og du behøver ikke skrive dem alle ned for at vide det. Du skal bare gange: ti muligheder for første ciffer, ti for andet, ti for tredje og ti for fjerde.

Sammenlign med at vælge 7 tal ud af 36 i et lotteri. Her er rækkefølgen ligegyldig, og pludselig bliver tallet et helt andet: 8 347 680 mulige rækker. Forskellen på de to situationer er hele pointen med emnet. Når du kan se, om rækkefølgen betyder noget, og om noget må bruges flere gange, ved du, hvilken formel du skal tage frem. Du bygger værktøjerne op ét ad gangen herunder, med tal du kan regne efter selv.

Hvad er kombinatorik?

Du møder kombinatorik hver gang et spørgsmål begynder med 'på hvor mange måder'. Hvor mange adgangskoder kan en app have, hvis den kræver tre bogstaver og to cifre? Hvor mange hold på fem kan du stille op fra en klasse på femogtyve? Hvor mange forskellige pizzaer kan du bestille, hvis du vælger tre af ti fyld? Alle spørgsmålene handler om at tælle uden at lave listen. Det kan lade sig gøre, fordi de fleste valg følger et mønster, og mønstret kan du lære at genkende. Når du først kan se det, tager regnestykket få sekunder, selv når svaret er i millionklassen.

Emnet er også døren ind til sandsynlighedsregning. Skal du finde chancen for en bestemt hændelse, har du brug for antallet af gunstige og antallet af mulige udfald, og de to tal kommer næsten altid fra kombinatorik. Læs gerne vores guide til sandsynlighedsregning ved siden af. Erik Vestergaards noter om sandsynlighedsregning og statistik på stx B-niveau kalder emnet kunsten at tælle endelige mængder, og beskrivelsen passer godt. Du tæller ikke ét ad gangen, du tæller med struktur. Strukturen består af fire byggesten, som du møder i rækkefølge herunder: multiplikationsprincippet, fakultet, permutationer og kombinationer.

Begreberne skifter navn fra bog til bog. Nogle lærebogssystemer kalder en permutation af k blandt n for en variation og reserverer ordet permutation til tilfældet, hvor alle n elementer ordnes. Notationen varierer også: du kan se \( P(n,k) \) eller \( _nP_k \) om permutationer og \( K(n,k) \), \( C(n,k) \), \( _nC_k \) eller \( \binom{n}{k} \) om kombinationer. Idéen bag er den samme, så lad dig ikke skræmme af forskelle i skrivemåde. Tjek din egen lærebogs definition, før du afleverer en opgave.

Multiplikationsprincippet: sådan ganger du valg sammen

En skolekantine tilbyder 3 hovedretter, 4 drikkevarer og 2 desserter. Hvor mange forskellige menuer kan du sammensætte, hvis du vælger én af hver? Vælger du først hovedret, har du 3 muligheder. Til hver af dem kan du tage en af 4 drikkevarer, så nu har du 3 · 4 = 12 kombinationer. Til hver af de 12 kan du tilføje en af 2 desserter, og du ender på 12 · 2 = 24 menuer. Du tegnede ikke noget træ, du gangede bare antallet af muligheder ved hvert valg.

Pinkoden fra indledningen er det samme princip med fire valg, hvor hvert valg har 10 muligheder: \( 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000 \). Princippet gælder, når valgene er uafhængige, og du skal træffe dem alle. Skal du i stedet vælge enten det ene eller det andet, bruger du additionsprincippet og lægger sammen. Tilbyder kantinen også 5 salater, som du kan tage i stedet for en varm hovedret, har du 3 + 5 = 8 muligheder for hovedretten, og regnestykket for hele menuen bliver \( 8 \cdot 4 \cdot 2 = 64 \). Ordet 'og' giver gange, ordet 'eller' giver plus.

Fakultet: hvad sker der, når du ordner alle elementer?

Fem venner skal stå på række til et gruppebillede. Hvem skal stå yderst til venstre? Der er 5 muligheder. Når den plads er besat, er der 4 tilbage til næste plads, derefter 3, derefter 2, og til sidst står den sidste person tilbage uden valg. Antallet af opstillinger er \( 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \). Det er samme tankegang som multiplikationsprincippet, men antallet af muligheder falder med én for hver plads, fordi en person ikke kan stå to steder på én gang.

Fakultet vokser eksplosivt. Allerede \( 10! = 3\,628\,800 \), så en klasse på ti elever kan sidde i over tre millioner forskellige rækkefølger. Definitionen \( 0! = 1 \) ser mærkelig ud, men den giver mening: der er præcis én måde at ordne ingenting på, nemlig at lade være. Den definition gør også, at formlerne længere nede virker, når alle elementer vælges eller ingen vælges. Grafen herunder viser, hvor hurtigt tallene stiger. Fra \( 5! = 120 \) til \( 6! = 720 \) er springet langt større end fra 1 til 2.

Du behøver sjældent regne store fakulteter ud. Skal du finde \( \frac{8!}{5!} \), skriver du \( 8! = 8 \cdot 7 \cdot 6 \cdot 5! \), og så forkortes \( 5! \) væk, så der står \( 8 \cdot 7 \cdot 6 = 336 \). Den lille omskrivning sparer dig for at taste tal med fem cifre ind på lommeregneren, og den bliver brugt i næsten alle regnestykker i resten af guiden.

Permutationer: når rækkefølgen betyder noget

Otte løbere stiller op til 100 meter, og kun de tre bedste får medalje. Guld, sølv og bronze er forskellige placeringer, så det gør en forskel, om Anna vinder og Bo bliver nummer to, eller om det er omvendt. Der er 8 muligheder for guldet, 7 for sølvet og 6 for bronzen, i alt \( 8 \cdot 7 \cdot 6 = 336 \) forskellige podier. Du har ikke ordnet alle otte løbere, kun tre af dem, men rækkefølgen tæller stadig. Det er en permutation.

Hvis du bedre kan lide at se en lærer regne det igennem, så gennemgår Michael Grankvists videolektion om permutation, kombination og binomialkoefficient forskellen mellem ordnet og uordnet udvalg med tavlen som hjælp. Se den og regn bagefter eksemplerne her i guiden igen uden at kigge.

1. 1

   Spørg: tæller rækkefølgen?

   Er der forskellige poster, placeringer eller pladser, er svaret ja og du bruger permutationer. Handler det kun om, hvem der er med, er svaret nej.

2. 2

   Spørg: må noget bruges flere gange?

   En pinkode kan indeholde samme ciffer flere gange. En bestyrelse kan ikke have samme person på to poster.

3. 3

   Find n og k

   n er antallet af elementer at vælge imellem, og k er antallet, du vælger.

4. 4

   Vælg formlen og forkort

   Skriv fakulteterne ud, forkort det, der er ens, og regn de sidste faktorer.

Permutationer med ens elementer: ordet ANANAS

Hvor mange forskellige ord kan du lave ved at blande bogstaverne i ANANAS? Der er seks bogstaver, så du fristes til at skrive \( 6! = 720 \). Men tre af bogstaverne er A, og to er N. Bytter du rundt på de tre A'er, får du det samme ord, og det samme gælder de to N'er. Hver rigtig rækkefølge er derfor talt med \( 3! \cdot 2! = 12 \) gange, og du skal dividere. Svaret er \( \frac{720}{12} = 60 \) forskellige ord. Reglen virker som kombinationsformlen: du starter med alle rækkefølger og fjerner dem, der ikke kan skelnes fra hinanden.

Samme princip bruger du, når du fordeler farvede kugler. Har du 3 røde og 2 blå kugler i en række, er der \( \frac{5!}{3! \cdot 2!} = 10 \) forskellige rækkefølger, og det er præcis \( \binom{5}{2} \). Det er ingen tilfældighed. At placere de to blå kugler er at vælge 2 af 5 pladser, og så ligger de røde kugler fast.

Kombinationer og binomialkoefficienten: når rækkefølgen er ligegyldig

Hvad sker der, hvis du skal vælge 3 personer til et gruppearbejde ud af 5, og det er ligegyldigt, hvem der bliver valgt først? Starter du med permutationer, får du \( 5 \cdot 4 \cdot 3 = 60 \). Men gruppen Anna, Bo og Cecilie er den samme gruppe som Cecilie, Anna og Bo. Hver gruppe på 3 personer er talt med i alle de rækkefølger, tre personer kan stå i, og det er \( 3! = 6 \) stykker. Du dividerer derfor med 6 og får 10 forskellige grupper. Du har lige udledt formlen for kombinationer.

Det enorme tal i lotteri-eksemplet viser, hvorfor du har brug for en formel. Du kan ikke skrive otte millioner rækker ned, men du kan regne dem ud på ti sekunder. Lommeregneren kan give dig svaret direkte, men en prøve kræver ofte, at du viser, hvordan du kom frem til tallet. Skriv derfor altid n og k, indsæt i formlen, forkort, og sæt til sidst resultatet ind i en sætning, så censor kan se, at du forstår, hvad tallet betyder.

Binomialkoefficienterne har en pæn symmetri: \( \binom{n}{k} = \binom{n}{n-k} \). At vælge de 7 tal, du vil have med, er det samme som at vælge de 29 tal, du vil lade ligge. Derfor er \( \binom{36}{7} = \binom{36}{29} \), og du kan altid vælge den mindste af de to k-værdier for at gøre regningen kortere. Grafen herunder viser alle værdier af \( \binom{8}{k} \). Den er spejlvendt omkring midten, og de største værdier ligger der, hvor du vælger halvdelen af elementerne.

Med og uden tilbagelægning: de fire typer samlet

En pinkode må gerne være 7777. Et podium kan ikke have Anna på både guld og sølv. Forskellen ligger i, om et element må bruges igen, og det kalder man med eller uden tilbagelægning. Med tilbagelægning har du de samme muligheder ved hvert valg, så pinkoden giver \( 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000 \). Uden tilbagelægning falder antallet af muligheder for hver gang, så en pinkode med fire forskellige cifre giver \( 10 \cdot 9 \cdot 8 \cdot 7 = 5\,040 \). Det er præcis permutationsformlen, \( P(10,4) = \frac{10!}{6!} = 5\,040 \). Næsten alle opgaver falder i en af de fire kasser i tabellen herunder.

Den sidste kasse møder du sjældnest. Forestil dig en isbar med 5 slags is, hvor du vælger 3 kugler, må tage samme sort flere gange, og rækkefølgen i bægeret er ligegyldig. Det kan du løse med \( \binom{5+3-1}{3} = \binom{7}{3} = 35 \) forskellige bægre. Den formel står ikke i alle læreplaner, så tjek, hvad dit niveau forventer, før du lærer den udenad. De tre første typer er dem, du oftest bliver bedt om at kende, og de dækker langt de fleste opgaver i en prøve.

Kombinatorik og sandsynlighed: hvad er chancen for at vinde?

Hvis der er 8 347 680 mulige lotterirækker, og kun én af dem er vinderrækken, er din chance for at ramme den \( \frac{1}{8\,347\,680} \). Det svarer til omkring 0,00001 procent. Du kan mærke, hvor meget kombinatorikken fortæller, selv før du har lært noget om sandsynlighed: tallet i nævneren er resultatet af en kombination. Den ene formel leverer tallet, den anden bruger det.

Når alle udfald er lige sandsynlige, regner du sandsynligheden som antal gunstige udfald divideret med antal mulige udfald. Begge tal kan være store, så du tæller dem med kombinatorik. Vil du se, hvordan faget forventer, at du arbejder med emnet i gymnasiet, kan du slå op i UVMs vejledning til læreplan i matematik B på stx. Metoden er altid den samme: tæl de mulige, tæl de gunstige, og divider.

Spørgsmålet 'mindst én' løser du med komplementærhændelsen. Hvad er chancen for, at mindst én dreng kommer med i gruppen? Det er lettere at finde sandsynligheden for, at der kun er piger, og trække den fra 1. Der er \( \binom{10}{3} = 120 \) grupper med kun piger, så sandsynligheden for kun piger er \( \frac{120}{816} \), og 'mindst én dreng' bliver \( 1 - \frac{120}{816} = \frac{696}{816} \approx 0{,}853 \). Tricket virker, fordi det er langt nemmere at tælle ét bestemt tilfælde end tre forskellige.

Binomialkoefficienten dukker op igen, når du gentager det samme forsøg flere gange og tæller, hvor mange gange noget lykkes. Det er idéen bag binomialfordelingen, hvor \( \binom{n}{k} \) fortæller, på hvor mange måder k succeser kan fordele sig på n forsøg. Har du styr på kombinationer, er du allerede halvvejs derhenne.

Binomialsætningen og Pascals trekant

Gang parenteserne ud i \( (a+b)^3 = (a+b)(a+b)(a+b) \), og du får \( a^3 + 3a^2b + 3ab^2 + b^3 \). Tallene foran leddene er 1, 3, 3, 1. De er ikke tilfældige. I leddet \( 3a^2b \) har du valgt b fra én af de tre parenteser og a fra de to andre, og der er \( \binom{3}{1} = 3 \) måder at udpege den ene parentes på. På samme måde får \( ab^2 \) koefficienten \( \binom{3}{2} = 3 \). Koefficienterne i en udregnet potens af en toleddet størrelse er altså binomialkoefficienter, og det er derfor, de har det navn.

Du kan finde koefficienterne uden formel ved at bygge Pascals trekant. Hver række starter og slutter med 1, og hvert tal indeni er summen af de to tal lige over. Række nummer n, talt fra 0, indeholder præcis tallene \( \binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n} \). Skal du bruge \( (a+b)^4 \), aflæser du række 4 og får koefficienterne 1, 4, 6, 4, 1. Trekanten er også en nem måde at kontrollere, at \( \binom{8}{4} = 70 \) ikke er en tastefejl.

Kombinatorik i praksis: kortspil, adgangskoder og begrænsninger

En pokerhånd består af 5 kort fra et spil med 52. Rækkefølgen, du får kortene i, er ligegyldig, så der er \( \binom{52}{5} = 2\,598\,960 \) forskellige hænder. Vil du vide, hvor sjælden en bestemt hånd er, tæller du de gunstige hænder på samme måde. Fire es plus ét vilkårligt kort kan kun dannes på 48 måder, fordi det femte kort kan være hvert af de 48 øvrige kort. Sandsynligheden er derfor \( \frac{48}{2\,598\,960} \), altså omkring 0,002 procent.

Adgangskoder er multiplikationsprincippet i praksis. Bruger du 8 tegn, og hvert tegn kan være et af 62 (små bogstaver, store bogstaver og cifre), er der \( 62^8 \approx 2{,}2 \cdot 10^{14} \) mulige koder. Hæver du længden til 12 tegn, bliver tallet \( 62^{12} \), og det er næsten 15 millioner gange så mange koder, fordi \( 62^4 \) er cirka 14,8 millioner. Det er derfor, en lang kode er langt sværere at gætte end en kode, der blot har et specialtegn i enden.

Begrænsninger gør opgaverne sjovere, og her skal du starte med det valg, der har flest krav. Hvor mange trecifrede tal har tre forskellige cifre og begynder ikke med 0? Første ciffer har 9 muligheder, nemlig 1 til 9. Andet ciffer kan være alle cifre undtagen det, du lige har brugt, og her er 0 med igen, så der er 9 muligheder. Tredje ciffer har 8. Resultatet er \( 9 \cdot 9 \cdot 8 = 648 \). Havde du startet med sidste ciffer, skulle du have holdt styr på, om 0 allerede var brugt, og det gør regnestykket besværligt.

Typiske fejl i kombinatorik

De fleste fejl i kombinatorik opstår, før du overhovedet har regnet noget. Du vælger den forkerte formel, fordi spørgsmålet ligner et andet, du har set før. Læs derfor opgaven to gange og stil de to kontrolspørgsmål fra trinene i guiden ovenfor, inden du tager lommeregneren frem. Herunder er de fire fejl, der oftest koster point.

Træn med et fast mønster. Skriv først, hvad der vælges, og om rækkefølgen tæller. Skriv derefter n og k. Regn til sidst med fakulteter, og tjek tallet mod et overslag. Regner du \( \binom{8}{3} \) og får et tal, der er større end \( 8 \cdot 7 \cdot 6 = 336 \), ved du, at noget er galt, for antallet af kombinationer kan aldrig overstige antallet af permutationer. Svaret er \( \binom{8}{3} = 56 \).

Hvis du alligevel sidder og bladrer rundt mellem de fire kasser, er det ikke et tegn på, at du er dårlig til matematik. Det er et tegn på, at du mangler nogen at tænke højt sammen med. En tutor fra Toptutors kan regne dine egne opgaver igennem med dig, og du kan læse mere om lektiehjælp i matematik. Den første prøvetime koster 99 kr., og der er ingen binding.