Combinatorics: permutations, combinations, inclusion–exclusion · Probability & Statistics

Counting things sounds trivial — until the things you're counting number in the millions. Three ideas let you count without ever listing a single outcome.

This matters because of the classical definition from two lessons ago: on an equally likely sample space, P(A) is a count divided by a count. Being able to compute those counts is being able to compute those probabilities.

The multiplication principle

Everything below is built on one observation. If a choice is made in stages, with n_1 options at the first stage, n_2 at the second, and so on, the total number of outcomes is the product:

$n_1 \times n_2 \times \cdots \times n_k$

Three shirts and four pairs of trousers make twelve outfits. You don't list them; you multiply.

Permutations: when order matters

Five racers finish a race, and we hand out gold, silver and bronze. Order matters — being first is very different from being third.

Five people could win gold. Once that's taken, four could win silver. Then three could win bronze:

$5 \times 4 \times 3 = 60$

In general, arranging r items chosen from n when order matters:

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

Check it: \frac{5!}{2!} = \frac{120}{2} = 60. The (n-r)! in the denominator cancels exactly the factors you never got to.

Two special cases worth knowing on sight:

P(n, n) = n! — arranging everything.
P(n, 1) = n — picking one.

Combinations: when order doesn't matter

Now pick an unordered three-person committee from those same five people. Alice, Bob and Cara is the same committee whichever order we picked them in.

But 60 counts every ordering separately. Each committee got counted 3! = 6 times, once for every way to order its three members. So divide:

$\binom{n}{r} = \frac{n!}{r!\,(n-r)!} \qquad \binom{5}{3} = \frac{60}{6} = 10$

Ten possible committees. Read \binom{n}{r} aloud as "n choose r".

The whole distinction in one line: if swapping two chosen items gives you a different outcome, it's a permutation; if it gives you the same outcome, it's a combination.

A useful symmetry: \binom{n}{r} = \binom{n}{n-r}. Choosing which 3 of 5 are in is the same as choosing which 2 are out.

Inclusion–exclusion: when groups overlap

How many numbers from 1 to 30 are divisible by 2 or by 3?

Fifteen are divisible by 2. Ten are divisible by 3. But the multiples of 6 — there are five of them — are in both groups, and adding the counts has double-counted every one:

$15 + 10 - 5 = 20$

This is the counting version of the rule you met for probabilities:

$|A \cup B| = |A| + |B| - |A \cap B|$

With three overlapping sets, one more correction appears. Subtracting all three pairwise overlaps removes the triple overlap one time too many, so add it back:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

The pattern continues: alternate signs, one term for every non-empty subset.

Worked example

A standard 52-card deck. What's the probability a five-card hand is a flush (all five the same suit)?

The sample space is every five-card hand, order irrelevant:

$|\Omega| = \binom{52}{5} = 2{,}598{,}960$

Now count flushes. Pick the suit (4 ways), then pick 5 of that suit's 13 cards:

$4 \times \binom{13}{5} = 4 \times 1287 = 5148$

$P(\text{flush}) = \frac{5148}{2598960} \approx 0.00198$

About 1 in 505 hands.

Two things to notice. First, we used combinations for the cards (a hand is unordered) but the multiplication principle across the two independent choices. Second, this figure conventionally includes straight flushes; poker rankings usually exclude them, giving 5148 - 40 = 5108.

Doing it in Python

math has all three, exactly — comb and perm use integer arithmetic, so they're exact for any size:

from math import comb, perm, factorial

print("orderings of 5 racers on the podium:", perm(5, 3))
print("3-person committees from 5:        ", comb(5, 3))
print("5-card hands from 52:              ", comb(52, 5))

# Exact for numbers no float could hold:
print("choose 25 from 50:", comb(50, 25))

# Flush probability
print("P(flush) =", round(4 * comb(13, 5) / comb(52, 5), 5))

itertools gives you the objects themselves, which is the honest way to check a formula on a small case before trusting it on a large one:

from itertools import permutations, combinations
from math import comb, perm

racers = ["A", "B", "C", "D", "E"]

podiums = list(permutations(racers, 3))
committees = list(combinations(racers, 3))

print("podiums   ", len(podiums), "== perm(5,3)?", len(podiums) == perm(5, 3))
print("committees", len(committees), "== comb(5,3)?", len(committees) == comb(5, 3))
print("first three podiums:   ", podiums[:3])
print("first three committees:", committees[:3])

Your turn

1. How many different 4-digit PINs are there? How many with no repeated digit?

2. A pizza place has 8 toppings. How many pizzas can you order with exactly 3 toppings? With at most 3 (including a plain pizza)?

3. How many integers from 1 to 100 are divisible by 2, 3 or 5?

Solutions

1. Four independent choices from ten digits each, so by the multiplication principle 10^4 = 10{,}000 PINs (0000 through 9999).

With no repeats, each choice shrinks the pool: $10 \times 9 \times 8 \times 7 = 5040 = P(10, 4)$

So 5040 of the 10,000 have distinct digits — just over half. (Which is why "no repeated digits" is a poor security rule: it discards half the keyspace for no benefit.)

2. Exactly 3 from 8, order irrelevant: \binom{8}{3} = 56.

At most 3 means 0, 1, 2 or 3 toppings: $\binom{8}{0} + \binom{8}{1} + \binom{8}{2} + \binom{8}{3} = 1 + 8 + 28 + 56 = 93$

The \binom{8}{0} = 1 term is the plain pizza — there is exactly one way to choose nothing, which is why 0! = 1 is defined the way it is.

3. Let A, B, C be the multiples of 2, 3 and 5. Counting with floor division:

|A| = 50, |B| = 33, |C| = 20.

Triple overlap: |A \cap B \cap C| = \lfloor 100/30 \rfloor = 3.

$50 + 33 + 20 - 16 - 10 - 6 + 3 = 74$

So 74 of the first 100 integers are divisible by at least one of 2, 3, 5 — and 26 are coprime to all three.

Check yourself in code

Verify the inclusion–exclusion answer to question 3 by brute force, then by the formula, and confirm they agree.

Print exactly this:

by counting: 74
by formula: 74
agree: True

from math import floor

n = 100
divisors = (2, 3, 5)

# Brute force: how many integers 1..n are divisible by at least one divisor?
brute = sum(1 for k in range(1, n + 1) if any(k % d == 0 for d in divisors))
print("by counting:", brute)

# Now the inclusion-exclusion formula: singles - pairs + triple.
# Hint: floor(n / d) counts the multiples of d up to n.

from math import floor

n = 100
divisors = (2, 3, 5)

brute = sum(1 for k in range(1, n + 1) if any(k % d == 0 for d in divisors))
print("by counting:", brute)

singles = floor(n / 2) + floor(n / 3) + floor(n / 5)
pairs = floor(n / 6) + floor(n / 10) + floor(n / 15)
triple = floor(n / 30)
formula = singles - pairs + triple

print("by formula:", formula)
print("agree:", brute == formula)

Order matters: permutations. Order doesn't: combinations. And whenever sets overlap, add them up, then correct for the double-counting.

Next: the single most useful idea in probability — how to update what you believe once you learn something new.

4. Combinatorics: permutations, combinations, inclusion–exclusion