Kombinatorik

Multiplikationsprincipen är grunden för allt: ska du välja flera saker efter varandra multiplicerar du antalet val.

Du har 3 tröjor och 4 byxor. Antal outfits: 3 · 4 = 12.

Två frågor avgör vilken formel du behöver:

Ordning spelar roll heter permutation. Ordning spelar ingen roll heter kombination. Skillnaden är den vanligaste förväxlingen.

Fakultet: $n! = n \cdot (n-1) \cdots 2 \cdot 1$, och $0! = 1$.

Antalet sätt att ordna $n$ saker i rad är $n!$. Det växer obegripligt fort:

Det sista talet är större än antalet atomer i vår galax. Blandar du en kortlek ordentligt har den ordningen med största sannolikhet aldrig funnits förut.

Binomialkoefficienten $\binom{n}{k}$ läses «n över k» och är antalet sätt att välja $k$ av $n$ utan hänsyn till ordning.

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

Delningen med $k!$ är hela skillnaden mot permutationer: varje urval har räknats $k!$ gånger, en för varje möjlig ordning, och de ska räknas som en.

Två egenskaper värda att kunna:

$\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{0} = \binom{n}{n} = 1$

Den första är intuitiv: att välja ut 3 av 10 är samma sak som att välja ut vilka 7 som inte ska med.

Kopplingen till sannolikhet. När alla utfall är lika sannolika:

$P(\text{händelse}) = \frac{\text{antal gynnsamma utfall}}{\text{antal möjliga utfall}}\$

Lotto som exempel: 7 rätt av 35 tal.

$\binom{35}{7} = 6\,724\,520 \;\Longrightarrow\; P(\text{7 rätt}) = \frac{1}{6\,724\,520}$

Födelsedagsproblemet är det klassiska motexemplet mot magkänslan: hur många personer behövs för att två troligen fyller år samma dag? Räkna på motsatsen — att alla har olika dagar:

$P(\text{alla olika}) = \frac{365}{365}\cdot\frac{364}{365}\cdots\frac{365-n+1}{365}$

Vid $n = 23$ är den under 0,5. 23 personer räcker — vilket nästan alla gissar fel på.

from math import factorial, comb, perm

# Multiplikationsprincipen
print(3 * 4, "outfits")                      # 12

# Med ordning, utan upprepning: guld, silver, brons av 8 löpare
print(perm(8, 3), "=", factorial(8) // factorial(5))      # 336 = 336

# Utan ordning: välj 5 av 12 i ett lag
print(comb(12, 5))                            # 792

# Med upprepning, med ordning: fyrsiffrigt kodlås
print(10 ** 4, "koder")                       # 10000

# Symmetrin: att välja 3 av 10 = att välja bort 7 av 10
print(comb(10, 3), comb(10, 7))               # 120 120

# Lotto: 7 rätt av 35
mojliga = comb(35, 7)
print(f"{mojliga:,} möjliga rader → chansen är 1 på {mojliga:,}")
# 6,724,520 möjliga rader → chansen är 1 på 6,724,520

# Fyra rätt av sju dragna, av 35 tal
gynnsamma = comb(7, 4) * comb(28, 3)
print(f"4 rätt: {gynnsamma:,} sätt → {gynnsamma / mojliga:.5f}")

# Födelsedagsproblemet — räkna på motsatsen
def alla_olika(n, dagar=365):
    p = 1.0
    for i in range(n):
        p *= (dagar - i) / dagar
    return p

for n in (10, 20, 23, 30, 50, 70):
    print(f"  {n:>2} personer: P(minst två samma dag) = {1 - alla_olika(n):.3f}")
#   10 personer: 0.117
#   23 personer: 0.507      ← över hälften redan här
#   50 personer: 0.970
#   70 personer: 0.999

# Hur snabbt fakulteter växer
for n in (5, 10, 20, 52):
    print(f"  {n}! = {factorial(n):.3e}")
#   52! = 8.066e+67     ← fler än atomerna i Vintergatan