Kombinatorik — permutation, kombination

Matematik A · STX · A-niveau · Statistik og sandsynlighed

🧮 Kombinatorik — permutation og kombination

Kombinatorik er læren om systematisk tælling — hvor mange måder kan vi arrangere eller udvælge ting på? Det er fundament for sandsynlighed, statistik, kryptografi og mange andre felter.

Multiplikationsprincippet

Det grundlæggende princip:

Hvis du har:

• Trin 1 med n₁ muligheder
• Trin 2 med n₂ muligheder
• ...
• Trin k med nₖ muligheder

Så er total antal måder = n₁ · n₂ · ... · nₖ

Eksempel: Du har 3 skjorter, 4 bukser og 2 par sko.

• Total kombinationer: 3 × 4 × 2 = 24 outfits

Permutation — rækkefølge betyder noget

#### Antal arrangementer af n forskellige

$$n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$$

Læses som "n fakultet".

Eksempler:

• 3! = 3·2·1 = 6
• 5! = 120
• 10! = 3.628.800
• 0! = 1 (per definition)

#### Antal permutationer af k udvalgt af n

$$P(n, k) = \frac{n!}{(n-k)!}$$

#### Konkrete eksempler

Eks 1: Sæt 5 personer på række

• 5! = 120 måder

Eks 2: Vælg 3 podie-stillinger (guld, sølv, bronze) blandt 10 atleter

• P(10, 3) = 10!/(10-3)! = 10·9·8 = 720 måder

Eks 3: Antal arrangementer af bogstaverne i "MATH"

• 4! = 24 måder

Kombination — rækkefølge betyder IKKE noget

#### Antal måder at udvælge k blandt n

$$C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$

Læses som "n vælg k" eller "binomialkoefficient".

#### Konkrete eksempler

Eks 1: Træk 5 kort blandt 52

• C(52, 5) = 2.598.960 måder

Eks 2: Lottorækkers chancer (vælg 7 tal blandt 36)

• C(36, 7) = 8.347.680
• Sandsynlighed for at vinde: 1 i 8.347.680
• Du har større chance for at blive ramt af lyn!

Eks 3: Vælg 3 elever til en gruppe blandt 20

• C(20, 3) = 20!/(3!·17!) = 1140 måder

Forskel: permutation vs. kombination

| Type | Spørgsmål | Eksempel |

|---|---|---|

| Permutation | "Hvilken rækkefølge?" | Sæt på række |

| Kombination | "Bare hvilke?" | Lottotal |

Tommelfingerregel:

• "Arrangement" → permutation (rækkefølge tæller)
• "Udvælgelse" → kombination (rækkefølge tæller ikke)

Multinomial-koefficient

Når vi opdeler n elementer i r grupper af størrelse k₁, k₂, ..., kᵣ:

$$\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1! \cdot k_2! \cdots k_r!}

Eksempel: Antal måder at fordele 10 elever i 3 hold med 4, 3, 3 elever:

• 10!/(4!·3!·3!) = 4200

Pascals trekant

Pascals trekant er en visualisering af binomialkoefficienter:

```

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

```

Egenskab:

$$C(n,k) = C(n-1,k-1) + C(n-1,k)$$

Dette giver en rekursiv metode til at beregne kombinationer.

Anvendelser

#### Sandsynlighed

Klassisk sandsynlighed:

$$P(A) = \frac{\text{gunstige}}{\text{totale}}$$

Og kombinatorik bruges til at tælle totale og gunstige udfald.

#### Eksempel: poker

• Sandsynlighed for royal flush (10, J, Q, K, A i samme farve):
• Antal gunstige: 4 (én pr. farve)
• Totale: C(52,5) = 2.598.960
• P(royal flush) = 4/2.598.960 ≈ 1 i 650.000

#### Genetik

Kromosomkombinationer:

• Menneske har 23 par kromosomer
• Antal kombinationer: 2²³ = ~8,4 millioner
• Plus crossing over: praktisk uendeligt
• Derfor er vi alle unikke

#### Kryptografi

• Antallet af mulige nøgler i en kryptering
• AES-256: 2²⁵⁶ ≈ 10⁷⁷ kombinationer
• Mere end atomer i universet!

#### Statistisk mekanik

• Antallet af mulige tilstande for molekyler
• Entropi: S = k·ln(W) hvor W er antal tilstande

CAS-værktøjer

TI-Nspire:

```

nPr(10, 3) → permutationer

nCr(52, 5) → kombinationer

fact(5) → fakultet

```

Excel:

```

=PERMUT(10, 3)

=COMBIN(52, 5)

=FACT(5)

```

Klassiske problemer

#### Fødselsdagsproblemet

Hvor mange personer skal der til, før 50% chance for fælles fødselsdag?

• Svar: kun 23 personer!
• Bruger kombinatorisk argument

#### Monty Hall (sandsynlighed)

• 3 døre, 1 har bilen
• Brug kombinatorik til at vise: skift altid → 2/3 vinder

Almindelige fælder

• ❌ Bytte om på permutation/kombination
• ❌ Glemme at nogle elementer er ens (multinomial vs. simpel permutation)
• ❌ Bruge for store tal (10! er allerede 3,6 mio.!)
• ❌ Glemme 0! = 1

Vidste du at...

♟️ Antallet af mulige skakpartier er ~10¹²⁰ — flere end atomer i det observerbare univers (~10⁸⁰).

🎴 Hvis du blander et kortspil korrekt, har den specifikke rækkefølge sandsynligvis aldrig været oprettet før i universets historie — 52! ≈ 8·10⁶⁷ kombinationer.

🧬 Antallet af DNA-sekvenser for en gen er ekstremt stort — derfor er det så svært at "designe" nye gener fra bunden.

Læringsmål

• Anvende multiplikationsprincippet til at tælle sammensatte valg
• Beregne fakultet og permutationer P(n,k) hvor rækkefølge tæller
• Beregne kombinationer C(n,k) og forklare forskellen til permutationer
• Anvende Pascals trekant og dens rekursive egenskab
• Anvende kombinatorik til at beregne klassiske sandsynligheder (poker, lotto)

Sådan kan du arbejde med emnet

• Beregn på hvor mange måder 5 personer kan stilles op i en kø
• Beregn hvor mange forskellige hold på 3 personer der kan vælges ud af en gruppe på 8
• Forklar forskellen mellem en permutation og en kombination med et eksempel for hver

Træningsforslag

• Beregn på hvor mange måder 5 personer kan stilles på række (5!), og hvor mange måder 3 podieplaceringer kan fordeles blandt 10 atleter.
• Beregn C(36,7) for det danske lotto og find sandsynligheden for at vinde med én tipning.
• Forklar med et eksempel forskellen mellem en "arrangerings"-opgave og en "udvælgelses"-opgave.
• Beregn sandsynligheden for royal flush i poker ved hjælp af kombinationer.

Brobygning

Kombinatorik er værktøjet, der gør binomialfordelingen mulig — C(n,k) i P(X=k) = C(n,k)·pᵏ·(1-p)ⁿ⁻ᵏ kommer direkte herfra.