Counting: permutations and combinations

Combinatorics is the art of counting without listing everything. It answers questions like "how many passwords are possible?" and "how many steps can this algorithm take?"

Two basic rules

• Sum rule: if a task can be done in one of m ways or one of n other ways (never both), there are m + n ways. A canteen with 4 rice dishes and 3 noodle dishes offers 4 + 3 = 7 choices of one dish.
• Product rule: if a task is done in two steps, with m ways for the first and n ways for the second, there are m × n ways. A rice dish and a drink, with 5 drinks: 4 × 5 = 20 meals.

A 4-digit PIN has 10 × 10 × 10 × 10 = 10⁴ = 10,000 possibilities. A password of 8 characters from 62 (letters and digits) has 62⁸, about 2.2 × 10¹⁴.

Permutations: order matters

A permutation is an ordered arrangement. The number of ways to arrange r items chosen from n different items:

P(n, r) = n × (n − 1) × ... × (n − r + 1) = n! / (n − r)!

Gold, silver and bronze among 10 runners: P(10, 3) = 10 × 9 × 8 = 720. All n items in a row: P(n, n) = n!.

Combinations: order does not matter

A combination is a choice where order does not matter. Each group of r items can be ordered in r! ways, so:

C(n, r) = P(n, r) / r! = n! / (r! (n − r)!)

A committee of 3 from 10 people: C(10, 3) = 720 / 6 = 120. It is written (n choose r) too.

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

people = ["Rahim", "Nadia", "Karim", "Tania"]

podiums = list(permutations(people, 2))      # first and second place
print(len(podiums), "podiums, math.perm says", perm(4, 2))
print(podiums[:4], "...")

pairs = list(combinations(people, 2))        # a team of two
print(len(pairs), "teams, math.comb says", comb(4, 2))
print(pairs)

# Each team of 2 can be ordered in 2! ways, so P = C × 2!
print(perm(4, 2) == comb(4, 2) * 2)

itertools.permutations and itertools.combinations list the arrangements; math.perm and math.comb count them. The counts match the formulas.

With repetition

The last one is called stars and bars: r stars (the sweets) and n − 1 bars that split them into n kinds.

Pascal's triangle

Each number is the sum of the two above it, which is the identity C(n, r) = C(n − 1, r − 1) + C(n − 1, r): a group of r either contains a particular person (choose the other r − 1 from n − 1) or does not (choose all r from n − 1).

row = [1]
for n in range(6):
    print(n, row, "sum", sum(row))
    # each inner number is the sum of the two above it
    row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]

Row n of the triangle gives the coefficients of (x + y)ⁿ: the binomial theorem says (x + y)ⁿ = Σ C(n, k) x^n−k y^k. So (x + y)³ = x³ + 3x²y + 3xy² + y³, and each row adds up to 2ⁿ.

Mark lesson complete