Counting principles · The Lumenary

Lens

MotivationH

Counting without listing

Many mobile-money services protect an account with a 4-digit PIN. How many different PINs are there? You could start listing them — 0000, 0001, 0002, … — but there is a quicker way.

At a school sports day in Addis Ababa, 8 runners race. In how many different ways can the gold, silver and bronze medals be awarded?
A website asks for a 4-character password made of capital letters and digits, with at least one digit. How many passwords are allowed?
How many different orders can a deck of 52 cards be shuffled into?

Listing works for small problems, and the lesson on systematic listing showed how to list without missing anything. But for these questions, listing would take hours, years — or, for the deck of cards, far longer than the age of the universe. We need principles that count without listing, and proofs that they give the right answer.

IntuitionH

Branches that multiply

Neha has 3 shirts (red, blue, green) and 2 pairs of trousers (black, grey). How many outfits can she make? A tree diagram shows every choice:

Three choices of shirt, each followed by two choices of trousers: $3 \times 2 = 6$ outfits. Every outfit is one path from the root to a leaf.

Each of the 3 shirt branches splits into 2 trouser branches, so there are $3 \times 2 = 6$ leaves. Add 4 pairs of shoes and every leaf splits again into 4: $3 \times 2 \times 4 = 24$ outfits.

But suppose Neha is choosing either a shirt or a hat (she has 5 hats) to give to her cousin. Now there is no second stage — she makes one choice from $3 + 5 = 8$ items.

DefinitionsH

Definitions

We write $|A|$ for the number of elements of a finite set $A$ , as in the lesson on sets. Two sets are disjoint if they have no element in common. The Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$ .

Definition— factorial

For a whole number $n \ge 1$ , $n$ factorial is $n! = n \times (n - 1) \times \cdots \times 2 \times 1$ . We also define $0! = 1$ .

So $1! = 1$ , $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , and $n! = n \times (n - 1)!$ .

Definition— arrangement (permutation)

An arrangement, or permutation, of a collection of different objects is an ordering of all of them in a row. An ordered selection of $k$ objects from $n$ different objects is a row of $k$ of them, all different, in which order matters. We write $P(n, k)$ for the number of ordered selections of $k$ objects from $n$ .

Definition— complement

If $A$ is a subset of a set $S$ , its complement in $S$ is $S \setminus A$ , the elements of $S$ that are not in $A$ .

Worked examplesH

Worked examples

Example— Or, and

A café in Hanoi offers 4 rice dishes and 3 noodle dishes, and 5 drinks.

Choose one main dish: $4 + 3 = 7$ ways (addition principle: the two kinds of dish don't overlap).
Choose a rice dish and a drink: $4 \times 5 = 20$ ways (multiplication principle).
Choose a main dish and a drink: $7 \times 5 = 35$ ways.

Example— PINs

Any 4-digit PIN: 10 choices for each of 4 digits, so $10 \times 10 \times 10 \times 10 = 10^4 = 10\,000$ .
PINs with no repeated digit: 10 choices for the first digit, then 9 for the second (anything except the first), 8, then 7: $10 \times 9 \times 8 \times 7 = 5040$ .
PINs with at least one repeated digit: everything else. $10\,000 - 5040 = 4960$ (complementary counting).

Example— Medals and bookshelves

Gold, silver and bronze among 8 runners: $8 \times 7 \times 6 = 336$ ways. That is $P(8, 3) = \tfrac{8!}{5!} = \tfrac{40\,320}{120} = 336$ .
Five different books on a shelf: $5 \times 4 \times 3 \times 2 \times 1 = 5! = 120$ orders.

Example— Passwords with at least one digit

There are $26 + 10 = 36$ symbols, so $36^4 = 1\,679\,616$ four-character passwords in all. Those with no digit use only letters: $26^4 = 456\,976$ . So $1\,679\,616 - 456\,976 = 1\,222\,640$ passwords contain at least one digit.

Counting “at least one digit” directly would mean adding the cases “exactly one digit”, “exactly two”, “exactly three” and “four” — possible, but slower and easier to get wrong.

Example— The most restricted position first

How many two-digit numbers have two different digits? The first digit can't be $0$ : 9 choices. The second can be any digit except the first: also 9 choices. So $9 \times 9 = 81$ .

If we chose the second digit first, the number of choices left for the first digit would depend on whether the second digit was $0$ — the multiplication principle would not apply directly. Deal with the most restricted position first.

Example— Overlapping cases

How many numbers from 1 to 100 are divisible by 2 or by 5? There are 50 multiples of 2 and 20 multiples of 5, but $50 + 20 = 70$ is wrong: the multiples of 10 (there are 10 of them) were counted twice. The answer is $50 + 20 - 10 = 60$ .

ProofH

Why the principles are true

Theorem— Theorem 1 (addition principle)

If $A$ and $B$ are disjoint finite sets, then $|A \cup B| = |A| + |B|$ .

Proof

Count the elements of $A$ as $1, 2, \ldots, |A|$ , then carry on counting the elements of $B$ as $|A| + 1, \ldots, |A| + |B|$ . Every element of $A \cup B$ receives exactly one number: it is in $A$ or in $B$ , and not in both, because the sets are disjoint. So $A \cup B$ has $|A| + |B|$ elements.

∎

Theorem— Theorem 2 (multiplication principle)

For finite sets $A$ and $B$ , $|A \times B| = |A| \cdot |B|$ .

Proof

Split the pairs by their first entry. For each $a \in A$ , the pairs $(a, b)$ form a “row” with exactly $|B|$ elements, one for each $b \in B$ . Different rows are disjoint, because their pairs have different first entries. By the addition principle, used again and again, $|A \times B| = |B| + |B| + \cdots + |B|$ , with one term for each element of $A$ , which is $|A| \cdot |B|$ .

∎

So multiplication of whole numbers really is repeated addition — of the rows of a rectangle of pairs.

Theorem— Theorem 3 (multiplication principle in stages)

Suppose a choice is made in $k$ stages: there are $n_1$ options at stage 1; whatever was chosen at stage 1, there are $n_2$ options at stage 2; and so on, up to $n_k$ options at stage $k$ . Then there are $n_1 \times n_2 \times \cdots \times n_k$ ways to make the whole choice.

Proof

By induction on the number of stages $k$ . For $k = 1$ there is nothing to prove. For more stages, sort the complete choices by what was chosen at stage 1. That makes $n_1$ disjoint groups. In each group, the remaining $k - 1$ stages offer $n_2, \ldots, n_k$ options, so by the induction hypothesis each group has $n_2 \times \cdots \times n_k$ choices. By the addition principle, the total is $n_1 \times (n_2 \times \cdots \times n_k)$ .

∎

Notice what the theorem requires: the options at a stage may depend on earlier choices (which digits are still unused), but their number must not.

Theorem— Theorem 4 (arrangements)

$n$ different objects can be arranged in a row in exactly $n!$ ways.

Proof

Fill the positions one at a time. The first position can hold any of the $n$ objects; the second, any of the $n - 1$ objects not yet used; the third, any of $n - 2$ ; …; the last position, the $1$ object left. By Theorem 3 there are $n \times (n - 1) \times \cdots \times 1 = n!$ arrangements.

∎

Why is $0! = 1$ ? There is exactly one way to arrange no objects at all: the empty row. The definition also makes the next formula work when $k = n$ .

Theorem— Theorem 5 (ordered selections)

For $0 \le k \le n$ , the number of ordered selections of $k$ objects from $n$ different objects is

P(n, k) = n \times (n - 1) \times \cdots \times (n - k + 1) = \frac{n!}{(n - k)!}.

Proof

There are $n$ choices for the first object, $n - 1$ for the second, …, and $n - k + 1$ for the $k$ -th; multiply by Theorem 3. Multiplying this product by $(n - k)! = (n - k) \times \cdots \times 1$ completes it to $n!$ , which gives the second form.

∎

Theorem— Theorem 6 (complementary counting)

If $A \subseteq S$ and $S$ is finite, then $|S \setminus A| = |S| - |A|$ .

Proof

Every element of $S$ is either in $A$ or in $S \setminus A$ , and not both. By the addition principle, $|S| = |A| + |S \setminus A|$ .

∎

Theorem— Theorem 7 (overlapping cases)

For finite sets $A$ and $B$ , $|A \cup B| = |A| + |B| - |A \cap B|$ .

Proof

$A \cup B$ is the disjoint union of $A$ and $B \setminus A$ , so $|A \cup B| = |A| + |B \setminus A|$ . Also $B$ is the disjoint union of $A \cap B$ and $B \setminus A$ , so $|B \setminus A| = |B| - |A \cap B|$ . Substitute.

∎

Formal mathematicsF

Counting in Lean

In Lean we model a finite collection as a list, so “how many?” is the length of a list. The addition principle is a library fact about joining lists; the multiplication principle is proved from it by induction, just as in Theorem 2.

addition_principleLean 4Applies a library theoremFormally verified

/-- **The addition principle.** Choosing one item from a list `A` or from a separate list `B`
can be done in `|A| + |B|` ways: putting the two lists together adds their lengths.
This applies core Lean's `List.length_append`. -/
theorem addition_principle (A B : List α) : (A ++ B).length = A.length + B.length :=
  List.length_append

Axioms used: propextformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

pairsLean 4Formally verified

/-- All ordered pairs `(a, b)` with `a` from `A` and `b` from `B` (the Cartesian product, as a
list): for each `a`, pair it with every `b`. -/
def pairs (A : List α) (B : List β) : List (α × β) := A.flatMap (fun a => B.map (fun b => (a, b)))

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

multiplication_principleLean 4Proved here from basic factsFormally verified

/-- **The multiplication principle.** There are `|A| · |B|` ordered pairs. The proof is the
addition principle used again and again: the pairs starting with the first `a` (there are
`|B|` of them), then those starting with the next `a`, and so on. -/
theorem multiplication_principle (A : List α) (B : List β) :
    (pairs A B).length = A.length * B.length := by
  induction A with
  | nil => simp [pairs]
  | cons a A ih =>
    simp only [pairs, List.flatMap_cons, List.length_append, List.length_map] at ih ⊢
    rw [ih, List.length_cons, Nat.succ_mul, Nat.add_comm]

Axioms used: propextformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

Complements (Theorem 6) and overlaps (Theorem 7), each proved by going through the list one item at a time:

complement_principleLean 4Proved here from basic factsFormally verified

/-- **Complementary counting.** Every item either has property `p` or does not, so
`|with p| = |all| - |without p|`. Here in the form `|with p| + |without p| = |all|`.
Proof by induction on the list. -/
theorem complement_principle (S : List α) (p : α → Bool) :
    (S.filter p).length + (S.filter (fun x => !p x)).length = S.length := by
  induction S with
  | nil => rfl
  | cons a S ih =>
    cases h : p a <;> simp [h] <;> omega

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

overlap_ruleLean 4Proved here from basic factsFormally verified

/-- **Counting overlapping cases.** Items with property `p` or `q`, plus items with both, equal
items with `p` plus items with `q`: `|A ∪ B| + |A ∩ B| = |A| + |B|`. Adding `|A| + |B|` counts the
overlap twice, so it must be subtracted once. Induction, with four cases for the first item. -/
theorem overlap_rule (S : List α) (p q : α → Bool) :
    (S.filter (fun x => p x || q x)).length + (S.filter (fun x => p x && q x)).length
      = (S.filter p).length + (S.filter q).length := by
  induction S with
  | nil => rfl
  | cons a S ih =>
    cases hp : p a <;> cases hq : q a <;> simp [hp, hq] <;> omega

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

Factorials and ordered selections are defined by recursion, mirroring “choose the first, then the rest”. Theorem 5 is stated without division, as $P(n, k) \cdot (n - k)! = n!$ ; division of whole numbers in Lean rounds down, so the multiplied-out form is the honest one.

factLean 4Formally verified

/-- The factorial `n! = n · (n - 1) ⋯ 2 · 1`, with `0! = 1`. -/
def fact : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * fact n

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

permLean 4Formally verified

/-- `perm n k` is the number of ordered selections of `k` objects from `n` different objects:
`n · (n - 1) ⋯ (n - k + 1)`. To choose `k + 1` objects in order from `n + 1`, pick the first
(`n + 1` ways), then `k` more in order from the `n` that are left. -/
def perm : Nat → Nat → Nat
  | _, 0 => 1
  | 0, _ + 1 => 0
  | n + 1, k + 1 => (n + 1) * perm n k

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

perm_mul_factLean 4Proved here from basic factsFormally verified

/-- **Ordered selections: `P(n, k) = n! / (n - k)!`**, in the division-free form
`P(n, k) · (n - k)! = n!` for `k ≤ n`. Proof by induction on `n`. -/
theorem perm_mul_fact : ∀ n k : Nat, k ≤ n → perm n k * fact (n - k) = fact n := by
  intro n
  induction n with
  | zero =>
    intro k hk
    have : k = 0 := by omega
    subst this
    rfl
  | succ n ih =>
    intro k hk
    cases k with
    | zero => simp [perm]
    | succ k =>
      have hk' : k ≤ n := by omega
      have hsub : n + 1 - (k + 1) = n - k := by omega
      rw [perm, hsub, Nat.mul_assoc, ih k hk', fact]

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

perm_selfLean 4Proved here from basic factsFormally verified

/-- Arranging all `n` objects in order: `P(n, n) = n!`. (Take `k = n` in `perm_mul_fact`:
`(n - n)! = 0! = 1`.) -/
theorem perm_self (n : Nat) : perm n n = fact n := by
  have h := perm_mul_fact n n (Nat.le_refl n)
  rw [Nat.sub_self, fact, Nat.mul_one] at h
  exact h

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

perm_eq_zeroLean 4Proved here from basic factsFormally verified

/-- You cannot choose more objects than you have: `P(n, k) = 0` when `k > n`. -/
theorem perm_eq_zero : ∀ n k : Nat, n < k → perm n k = 0 := by
  intro n
  induction n with
  | zero =>
    intro k hk
    cases k with
    | zero => omega
    | succ k => rfl
  | succ n ih =>
    intro k hk
    cases k with
    | zero => omega
    | succ k => rw [perm, ih k (by omega), Nat.mul_zero]

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

Theorem 4, done the way a computer would: build the actual list of arrangements by inserting the first object into every position of every arrangement of the rest, and prove that the list has $n!$ entries.

insertAllLean 4Formally verified

/-- `insertAll a l` lists the ways of inserting a new object `a` into the row `l`: in front, or
after the first object, …, or at the end. -/
def insertAll (a : α) : List α → List (List α)
  | [] => [[a]]
  | b :: l => (a :: b :: l) :: (insertAll a l).map (fun m => b :: m)

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

arrangementsLean 4Formally verified

/-- All arrangements (orderings) of a list: arrange the rest, then insert the first object in
every possible position. -/
def arrangements : List α → List (List α)
  | [] => [[]]
  | a :: l => (arrangements l).flatMap (insertAll a)

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

length_insert_allLean 4Proved here from basic factsFormally verified

/-- A new object can go into a row of `n` objects in `n + 1` places. -/
theorem length_insert_all (a : α) (l : List α) : (insertAll a l).length = l.length + 1 := by
  induction l with
  | nil => rfl
  | cons b l ih => simp [insertAll, ih]

Axioms used: propextformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

mem_arrangements_lengthLean 4Proved here from basic factsFormally verified

/-- Every arrangement of `l` has the same length as `l`. -/
theorem mem_arrangements_length (l m : List α) (h : m ∈ arrangements l) : m.length = l.length := by
  induction l generalizing m with
  | nil =>
    simp [arrangements] at h
    subst h
    rfl
  | cons a l ih =>
    simp only [arrangements, List.mem_flatMap] at h
    obtain ⟨m', hm', hm⟩ := h
    rw [mem_insert_all_length a m' m hm, ih m' hm', List.length_cons]

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

length_arrangementsLean 4Proved here from basic factsFormally verified

/-- **`n` different objects can be arranged in `n!` ways.** Each of the `(n - 1)!` arrangements of
the other objects (induction hypothesis) gives `n` arrangements, one for each place the new
object can go, so there are `(n - 1)! · n = n!` in all. -/
theorem length_arrangements (l : List α) : (arrangements l).length = fact l.length := by
  induction l with
  | nil => rfl
  | cons a l ih =>
    rw [arrangements, List.length_flatMap]
    have hconst : (arrangements l).map (fun m => (insertAll a m).length)
        = (arrangements l).map (fun _ => l.length + 1) := by
      apply List.map_congr_left
      intro m hm
      rw [length_insert_all, mem_arrangements_length l m hm]
    rw [hconst, List.map_const', List.sum_replicate_nat, ih, List.length_cons, fact,
      Nat.mul_comm]

Axioms used: propext, Quot.soundformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

arrangements_threeLean 4Proved here from basic factsFormally verified

/-- The `3! = 6` arrangements of three objects, listed by Lean. -/
theorem arrangements_three :
    arrangements [1, 2, 3] = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]] := by
  decide

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

arrangements_four_distinctLean 4Proved here from basic factsFormally verified

/-- The arrangements of four different objects are all different from one another, and there
are `4! = 24` of them: nothing is missed and nothing is counted twice. Checked by Lean. -/
theorem arrangements_four_distinct :
    (arrangements [1, 2, 3, 4]).Nodup ∧ (arrangements [1, 2, 3, 4]).length = 24 := by
  decide

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

Finally, the counts from the examples, and a brute-force check of complementary counting over all 1000 three-digit codes:

lesson_countsLean 4Proved here from basic factsFormally verified

/-- Counts from the lesson, computed by Lean: 4-digit PINs with no repeated digit (`5040`),
podium finishes for 8 runners (`336`), arrangements of 5 different letters (`120`), and
4-symbol passwords from 26 letters and 10 digits that contain at least one digit. -/
theorem lesson_counts :
    perm 10 4 = 5040 ∧ perm 8 3 = 336 ∧ fact 5 = 120 ∧ 36 ^ 4 - 26 ^ 4 = 1222640 := by
  decide

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

at_least_one_sevenLean 4Proved here from basic factsFormally verified

/-- **Complementary counting, checked by brute force.** Of the 1000 codes `000`–`999`, the
number containing at least one digit `7` is `1000 - 9³ = 271`. Lean checks this by going
through all 1000 codes. -/
theorem at_least_one_seven :
    ((List.range 1000).filter
      (fun n => n % 10 == 7 || n / 10 % 10 == 7 || n / 100 == 7)).length = 1000 - 9 ^ 3 := by
  decide +kernel

Axioms used: No axiomsformal/Lumenary/CountingPrinciples.leanTry it in the Lean web editor

ComputationC

Formulas against brute force

Counting principles checked by listing every casePythonExact computationExhaustive finite checkComputationally tested

"""Counting without listing - and then listing anyway, to check.

Each counting principle predicts a number: the multiplication principle for
PINs and podiums, factorials for arrangements, complementary counting for
"at least one", and the overlap rule for "or". This experiment computes
each prediction from the formula and then lists every possibility with
itertools to count them one by one. It also shows the classic mistake of
adding overlapping cases without subtracting the overlap.
"""

from itertools import permutations, product
from math import factorial

DIGITS = "0123456789"
LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def ordered_selections(n, k):
    """n * (n - 1) * ... * (n - k + 1), the number of ordered selections."""
    if k > n:
        return 0
    return factorial(n) // factorial(n - k)

def count_pins(repeats_allowed=True):
    """Count 4-digit PINs by listing them (optionally with distinct digits)."""
    pins = product(DIGITS, repeat=4)
    if repeats_allowed:
        return sum(1 for _ in pins)
    return sum(1 for p in pins if len(set(p)) == 4)

def count_codes_with_digit(length):
    """Count codes of `length` symbols (letters or digits) with a digit."""
    symbols = LETTERS + DIGITS
    return sum(1 for code in product(symbols, repeat=length)
               if any(c in DIGITS for c in code))

def count_divisible_by_either(limit, a, b):
    """How many of 1..limit are divisible by a or by b, by listing."""
    return sum(1 for n in range(1, limit + 1) if n % a == 0 or n % b == 0)

def main():
    rows = [
        ("4-digit PINs", 10 ** 4, count_pins()),
        ("PINs, no repeated digit", ordered_selections(10, 4),
         count_pins(repeats_allowed=False)),
        ("PINs, some digit repeated", 10 ** 4 - ordered_selections(10, 4),
         count_pins() - count_pins(repeats_allowed=False)),
        ("podiums: 8 runners", ordered_selections(8, 3),
         sum(1 for _ in permutations(range(8), 3))),
        ("arrangements of LUMEN", factorial(5),
         len(set(permutations("LUMEN")))),
        ("3-symbol codes with a digit", 36 ** 3 - 26 ** 3,
         count_codes_with_digit(3)),
        ("1-100 divisible by 2 or 5", 50 + 20 - 10,
         count_divisible_by_either(100, 2, 5)),
    ]
    print(f"{'what is counted':<30}{'formula':>9}{'listed':>9}  agree?")
    for name, formula, listed in rows:
        print(f"{name:<30}{formula:>9}{listed:>9}  {formula == listed}")
    print()
    print("The overlap mistake: 50 multiples of 2 plus 20 multiples of 5 is")
    print("70, but 10, 20, ..., 100 were counted twice. 70 - 10 = 60.")
    print()
    word = "LETTER"
    print(f"Arrangements of {word} (two Es and two Ts look identical):")
    print(f"  {len(word)}! = {factorial(len(word))} orders of the "
          f"{len(word)} tiles, but only {len(set(permutations(word)))} "
          "different words.")
    print()
    print("Epistemic status: exact counts, exhaustive for the cases listed")
    print("(up to 46,656 codes). Agreement in these cases is evidence; the")
    print("lesson's proofs show the formulas hold for every n and k.")

if __name__ == "__main__":
    main()

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Every formula agrees with the listing. The last lines show a trap: the principles of this lesson are for different objects. Rearranging the tiles of LETTER gives $6! = 720$ orders, but swapping the two Es or the two Ts changes nothing you can see, so there are only $\tfrac{720}{2 \times 2} = 180$ different words.

How fast factorials grow: exact values and Stirling's formulaPythonExact computationNumerical approximationComputationally tested

"""How fast does n! grow? Exact factorials and a famous approximation.

The number of ways to arrange n different objects is n!. This experiment
prints exact factorials next to 2^n and 10^n, finds where n! overtakes
each, counts the digits of 52! (the number of ways to shuffle a deck of
cards), and estimates how long listing all those orders would take. It
ends with Stirling's approximation n! ~ sqrt(2 pi n) (n/e)^n, a result
from analysis that is quoted here, not proved, with its exact relative
error for several n.
"""

import math

SECONDS_PER_YEAR = 365.25 * 24 * 3600
AGE_OF_UNIVERSE_YEARS = 1.38e10

def first_n_where_factorial_exceeds(base):
    """Smallest n >= 1 with n! > base**n."""
    n = 1
    while math.factorial(n) <= base ** n:
        n += 1
    return n

def digits(n):
    """Number of decimal digits of a positive integer."""
    return len(str(n))

def stirling(n):
    """Stirling's approximation sqrt(2 pi n) (n / e)^n, as a float."""
    return math.sqrt(2 * math.pi * n) * (n / math.e) ** n

def relative_error(n):
    """(n! - Stirling) / n!, computed in floating point."""
    return (math.factorial(n) - stirling(n)) / math.factorial(n)

def years_to_list(count, per_second):
    """Years needed to list `count` items at `per_second` items a second."""
    return count / per_second / SECONDS_PER_YEAR

def main():
    print("  n            n!          2^n")
    for n in (1, 2, 3, 4, 5, 8, 10, 13):
        print(f"{n:3d} {math.factorial(n):>13,} {2 ** n:>12,}")
    print(f"n! first exceeds 2^n at n = {first_n_where_factorial_exceeds(2)},"
          f" and 10^n at n = {first_n_where_factorial_exceeds(10)}.")
    print()
    deck = math.factorial(52)
    print(f"Shuffles of a 52-card deck: 52! has {digits(deck)} digits,")
    print(f"  about {float(deck):.3e}.")
    years = years_to_list(deck, 1e9)
    print(f"  Listing a billion shuffles a second would take about "
          f"{years:.1e} years,")
    print(f"  roughly {years / AGE_OF_UNIVERSE_YEARS:.0e} times the age of "
          "the universe.")
    print()
    print("Stirling's approximation sqrt(2 pi n) (n/e)^n:")
    print("    n    relative error    1/(12n)")
    for n in (1, 2, 5, 10, 20, 52):
        print(f"  {n:3d}    {relative_error(n):.6f}        {1 / (12 * n):.6f}")
    print()
    print("Epistemic status: the factorials, powers and digit count are exact")
    print("integers; times and Stirling values are floating-point estimates.")
    print("Stirling's formula is a theorem of analysis quoted here, not")
    print("proved; the table only shows its error for six values of n.")

if __name__ == "__main__":
    main()

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The number of shuffles, $52!$ , has 68 digits. A shuffled deck is almost certainly in an order that no deck has ever been in before. Here exact integer arithmetic (the factorials) sits beside floating-point estimates (the years, and Stirling's approximation, a theorem from analysis that we quote but do not prove).

Explore

Explore: counting overlaps

Multiples of 2 or 5 up to 100

Mark the multiples of a number and look for patterns. Add a second number to find common multiples.

Multiples of2

and multiples of5

multiple of 2
multiple of 5
common multiple (both)

There are 50 multiples of 2 from 1 to 100.

Common multiples of 2 and 5: 10, 20, 30, 40, 50, 60, 70, 80, …. The smallest one, 10, is the least common multiple.

Tap a number to see how it is related.

The circles mark multiples of $2$ and the squares multiples of $5$ ; numbers with both marks are counted twice by $50 + 20$ . How many are there, and what do they have in common? Change the second number to $3$ , then to $4$ : predict the size of the overlap before you look. (For $2$ and $4$ the overlap is all the multiples of $4$ !)

Exercises

1. Counting principles

Warm-upHuman

Kofi has $4$ shirts, $3$ pairs of trousers and $2$ pairs of shoes. An outfit is one shirt, one pair of trousers and one pair of shoes. How many different outfits can he make?

2. Counting principles

Warm-upHuman

A school library in Quito has $12$ novels and $8$ comics on a display shelf. Ana may borrow one book from the shelf. In how many ways can she choose?

Choose one

20

96

12

4

3. Counting principles

Warm-upHuman

In how many different orders can $6$ different books be arranged on a shelf?

4. Counting principles

CoreHuman

Ten swimmers race in a final. In how many ways can the gold, silver and bronze medals be awarded? (No ties.)

5. Counting principles

CoreHuman

How many 4-digit PINs (from $0000$ to $9999$ ) contain at least one repeated digit?

6. Counting principles

CoreHuman

How many of the whole numbers from $1$ to $100$ are divisible by $3$ or by $5$ (or both)?

7. Counting principles

CoreHuman

Which of these are good reasons for defining $0! = 1$ ? (Choose all that apply.)

Choose all that apply

There is exactly one way to arrange no objects: the empty arrangementIt makes

P(n, n) = \tfrac{n!}{(n - n)!} = n!

trueIt keeps the rule

n! = n \times (n - 1)!

true for

n = 1

Because zero times anything is zero

8. Counting principles

StretchHuman

A code has $3$ symbols, each a capital letter ( $26$ choices) or a digit ( $10$ choices). How many codes contain at least one letter and at least one digit?

9. Counting principles

CoreFormal

In the Lean file, perm n k is $P(n, k)$ and fact n is $n!$ . Which statement correctly formalises $P(n, k) = \tfrac{n!}{(n - k)!}$ ?

Choose one

∀ n k : Nat, k ≤ n → perm n k * fact (n - k) = fact n∀ n k : Nat, perm n k * fact (n - k) = fact n∀ n k : Nat, k ≤ n → perm n k = fact n / fact k∀ n k : Nat, k ≤ n → perm n k = fact n * fact (n - k)

10. Counting principles

StretchComputational

Write a recursive function arrangements(items) that returns a list of all orderings of the list items (each ordering a list), without using itertools. Idea: for each item, put it first and follow it by every arrangement of the remaining items. Then check that $4$ items give $4! = 24$ different arrangements.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Common misconceptionsH

Common misconceptions

Misconception

Adding where you should multiply, or multiplying where you should add. “A rice dish and a drink” is a two-stage choice: multiply ( $4 \times 5$ ). “A rice dish or a noodle dish” is one choice from two separate groups: add ( $4 + 3$ ). Ask: is it one choice, or one choice followed by another?

Misconception

Counting overlapping cases twice. Multiples of 2 or 5 up to 100 number $50 + 20 - 10 = 60$ , not $70$ . The addition principle needs disjoint groups; when groups overlap, subtract the overlap once.

Misconception

“The multiplication principle needs the same options at every stage.” It needs the same number of options. In a PIN with no repeated digit, the 9 digits available for the second place depend on the first digit, but there are always 9 of them.

Misconception

“ $0! = 0$ .” $0! = 1$ : there is one way to arrange nothing, and it keeps $P(n, n) = \tfrac{n!}{0!} = n!$ true.

Misconception

Forgetting whether order matters. A podium (gold, silver, bronze) is an ordered selection: $8 \times 7 \times 6 = 336$ . Choosing 3 runners for a relay team, where order doesn't matter, gives fewer: each team of 3 was counted $3! = 6$ times, so there are $\tfrac{336}{6} = 56$ teams. Selections without order are the subject of combinatorics.

ViewpointsH

Other ways of seeing

Algebra— The laws of arithmetic are counting facts

Why is $a \times b = b \times a$ ? Because swapping the entries of each pair, $(x, y) \mapsto (y, x)$ , matches $A \times B$ with $B \times A$ one-to-one, so they have the same size. Why is $a \times (b + c) = a \times b + a \times c$ ? Because if $B$ and $C$ are disjoint, the pairs in $A \times (B \cup C)$ are exactly the pairs in $A \times B$ together with those in $A \times C$ . Proving an equation by showing that both sides count the same set is called a combinatorial proof — a favourite tool of combinatorialists.

Computation— When brute force is hopeless

A delivery driver must visit $n$ towns and return home. Trying every route means checking $\tfrac{(n - 1)!}{2}$ routes: for $n = 20$ that is about $6 \times 10^{16}$ , more than a fast computer can check in a reasonable time. Counting tells computer scientists before they write any code that listing everything won't work, and sends them looking for cleverer algorithms. This “travelling salesperson problem” is one of the most studied problems in algorithms and efficiency.

Probability— Counting gives probabilities

When outcomes are equally likely, a probability is a count divided by a count. A randomly guessed 4-digit PIN is right with probability $\tfrac{1}{10\,000}$ ; a random PIN has no repeated digit with probability $\tfrac{5040}{10\,000} \approx 0.5$ — less than you might guess. See probability.

Wonder Trails

Counting finite sets is the start of a long road: what does it mean to count an infinite set, and can products be described without counting at all? Both trails are optional.

Wonder Trail · Optional · never gradedHow many infinities?There are infinitely many counting numbers and infinitely many infinite 0–1 sequences. Are these two infinities the same size?Follow the trail Wonder Trail · Optional · never gradedThe product, by its mapsCan you describe the set of pairs

A \times B

without ever looking inside it — only by how functions go into it?Follow the trail

Set-theoretic connectionH

Set-theoretic connection

To say a set $A$ has $n$ elements is to say there is a one-to-one correspondence — a bijection — between $A$ and $\{1, 2, \ldots, n\}$ : counting is pairing objects with numbers. The proof of the addition principle builds exactly such a pairing. And an arrangement of $n$ objects is a bijection from the positions $\{1, \ldots, n\}$ to the objects, so Theorem 4 says: there are $n!$ bijections between two sets of size $n$ .

Category-theoretic connectionH

A glimpse of structure

In the world of finite sets and functions, the disjoint union $A \sqcup B$ and the Cartesian product $A \times B$ are the two most basic ways of combining sets — category theorists call them the coproduct and the product. Counting turns them into $+$ and $\times$ : $|A \sqcup B| = |A| + |B|$ and $|A \times B| = |A| \cdot |B|$ . Even powers appear: the number of functions from $B$ to $A$ is $|A|^{|B|}$ , which is why $10^4$ counts PINs (a PIN is a function from the 4 positions to the 10 digits). The Products by maps trail describes $A \times B$ without counting at all.

History & global context

History and global context

India. The medical text Suśruta Saṃhitā (compiled over many centuries, from the first millennium BCE) counts $63$ combinations of six basic tastes. Piṅgala's work on poetic metre (around the 3rd–2nd century BCE) counts the patterns of long and short syllables, and Jain texts discuss combinations too. Bhāskara II's Līlāvatī (1150) gives rules for counting the arrangements of digits, including the product $n \times (n-1) \times \cdots \times 1$ .
The Middle East and North Africa. The Hebrew Sefer Yetzirah (of uncertain date, early first millennium CE) counts arrangements of letters: “two stones build two houses, three build six houses, four build twenty-four…”. In 8th-century Basra, al-Khalīl ibn Aḥmad planned the first Arabic dictionary by counting the possible arrangements of letters in words. In 13th-century Marrakesh, Ibn Munʿim developed systematic counting methods.
Europe. Levi ben Gershon, in France, proved formulas for arrangements and selections in 1321 using an early form of induction. Christian Kramp introduced the notation $n!$ in 1808.

Counting without listing

Branches that multiply

Definitions

Worked examples

Why the principles are true

Counting in Lean

Formulas against brute force

Explore: counting overlaps

Exercises

Common misconceptions

Other ways of seeing

Wonder Trails

Set-theoretic connection

A glimpse of structure

History and global context

Further reading