Combinatorics

The multiplication principle is the foundation: when you make several choices in sequence, you multiply the number of options for each step.

You have 3 shirts and 4 pairs of trousers. Number of combinations: 3 · 4 = 12.

Two questions determine which formula you need:

Order matters is called a permutation. Order does not matter is called a combination. This distinction is the most common source of calculation errors.

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

The number of ways to arrange $n$ objects in a row is $n!$. The value increases extremely rapidly:

The last number is larger than the number of atoms in the Milky Way. If you shuffle a deck of cards properly, it is almost certain that this specific order has never existed before.

The binomial coefficient $\binom{n}{k}$ is read as «n over k» and indicates the number of ways to choose $k$ out of $n$ without regard to order.

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

The division by $k!$ is the difference from permutations: each selection has been counted $k!$ times (once for each possible order), and these should be counted as a single case.

Two properties to know:

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

The first is intuitive: choosing 3 out of 10 is the same as choosing which 7 are not included.

Connection to probability. When all outcomes are equally likely:

$P(\text{event}) = \frac{\text{number of favourable outcomes}}{\text{number of possible outcomes}}\$

Lotto as an example: 7 correct out of 35 numbers.

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

The birthday problem is a classic example of how intuition can mislead: how many people are needed for the probability to be over 50% that two people share a birthday? Calculate the opposite — that everyone has a different birthday:

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

At $n = 23$, the probability of all different days is under 0.5. 23 people are enough — which most people guess incorrectly.

from math import factorial, comb, perm

# Multiplication principle
print(3 * 4, "outfits")                      # 12

# With order, without repetition: gold, silver, bronze from 8 runners
print(perm(8, 3), "=", factorial(8) // factorial(5))      # 336 = 336

# Without order: choose 5 out of 12 for a team
print(comb(12, 5))                            # 792

# With repetition, with order: four-digit code lock
print(10 ** 4, "codes")                       # 10000

# Symmetry: choosing 3 out of 10 = excluding 7 out of 10
print(comb(10, 3), comb(10, 7))               # 120 120

# Lotto: 7 correct out of 35
mojliga = comb(35, 7)
print(f"{mojliga:,} possible lines → the chance is 1 in {mojliga:,}")
# 6,724,520 possible lines → the chance is 1 in 6,724,520

# Four correct out of seven drawn, from 35 numbers
gynnsamma = comb(7, 4) * comb(28, 3)
print(f"4 correct: {gynnsamma:,} ways → {gynnsamma / mojliga:.5f}")

# Birthday problem — calculate the opposite
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} people: P(at least two same day) = {1 - alla_olika(n):.3f}")
#   10 people: 0.117
#   23 people: 0.507      ← over half already here
#   50 people: 0.970
#   70 people: 0.999

# How fast factorials grow
for n in (5, 10, 20, 52):
    print(f"  {n}! = {factorial(n):.3e}")
#   52! = 8.066e+67     ← more than atoms in the Milky Way