Counting principles: sums, products and the pigeonhole principle

Almost every counting argument in this course is built from a handful of simple principles. Two of them, the sum rule and the product rule, tell us how to combine counts. A third, counting the complement, often turns a hard count into an easy one. A fourth, the pigeonhole principle, does not count anything exactly but guarantees that something must happen once the numbers are large enough. Each principle is close to obvious when stated, yet using them correctly takes practice, because the hard part is always deciding how to break a problem into pieces that the principles can handle.

Throughout, the number of elements of a finite set \(A\) is written \(|A|\) and called its size or cardinality. The questions MATH-228 asks about infinite cardinalities do not arise here; all our sets are finite.

The sum rule

If a task can be done in one of two ways that cannot both happen, and there are \(m\) ways of the first kind and \(n\) of the second, then the task can be done in \(m + n\) ways. In the language of sets: if \(A\) and \(B\) are disjoint, meaning they have no element in common, then \(|A \cup B| = |A| + |B|\). The rule extends to any number of pairwise disjoint sets: the size of the union is the sum of the sizes.

A student choosing one elective from 7 science courses or 5 arts courses, with no course in both lists, has \(7 + 5 = 12\) choices. The word to watch for is or, together with a guarantee that the cases do not overlap. When the cases do overlap, adding the sizes counts the shared elements twice. For two sets the correction is simple:

\[ |A \cup B| = |A| + |B| - |A \cap B|. \]

This is the two-set case of the inclusion-exclusion principle. MATH-460 develops the general version for any number of sets; here we need only two or three. For example, among the integers from 1 to 100, 50 are divisible by 2, 33 are divisible by 3 and 16 are divisible by both, that is by 6. So \(50 + 33 - 16 = 67\) are divisible by 2 or 3, and the remaining 33 are divisible by neither.

The product rule

If a task consists of two steps, with \(m\) ways to do the first and, for each of those, \(n\) ways to do the second, then the task can be done in \(mn\) ways. More generally, a sequence of \(k\) choices with \(n_1, n_2, \dots, n_k\) options at each step can be made in \(n_1 n_2 \cdots n_k\) ways. In the language of sets, \(|A \times B| = |A| \cdot |B|\), where \(A \times B\) is the set of ordered pairs.

The important words in the statement are for each of those. The number of options at the second step may depend on what was chosen at the first step, as long as the number itself does not. When you choose a president and then a vice-president from a club of 20 members, the vice-president can be any of the 19 people other than the president. Who those 19 are depends on the first choice, but there are always 19 of them, so there are \(20 \cdot 19 = 380\) ways.

A tree diagram makes the product rule visible. Each level of the tree is one step; each branch is one option; each leaf is one complete outcome. The number of leaves is the product of the branching numbers when every node at a level has the same number of branches. When the branching is uneven, add up the leaves instead, which is the sum rule at work.

Strings and passwords

A string of length \(k\) over an alphabet of \(n\) symbols is a sequence of \(k\) symbols, repetition allowed. By the product rule there are \(n^k\) such strings: \(n\) choices for each of the \(k\) positions. There are \(2^8 = 256\) bytes, \(10^4 = 10\,000\) four-digit PINs and \(26^3 = 17\,576\) three-letter codes.

Counting the complement is one of the most useful tricks in the subject. Whenever a condition says at least one, it is usually easier to count the arrangements with none and subtract from the total. The trick rests on the sum rule: every arrangement either has at least one digit or has none, never both, so the two counts add up to the total.

The code below checks the method on a small alphabet, where every password can be listed, and then applies it to the real sizes. It also estimates how long an attacker guessing a billion passwords per second would need, which is why security guidance prefers longer passwords over more complicated ones. Each extra character multiplies the count by 62, while adding a required digit removes possibilities.

from itertools import product

# small check: alphabet of 3 letters and 2 digits, length 4
letters, digits = "abc", "12"
alphabet = letters + digits
all_pw = list(product(alphabet, repeat=4))
with_digit = [p for p in all_pw if any(ch in digits for ch in p)]
print("small alphabet:", len(all_pw), "passwords,", len(with_digit), "with a digit")
print("complement count:", len(alphabet)**4 - len(letters)**4)

# real sizes
total = 62 ** 8
no_digit = 52 ** 8
print(f"8 characters: {total:.3e} total, {total - no_digit:.3e} with a digit")
for length in (8, 10, 12):
    years = 62 ** length / 1e9 / (3600 * 24 * 365)
    print(f"length {length}: {62**length:.2e} passwords, {years:.3g} years at 1e9 guesses per second")

small alphabet: 625 passwords, 544 with a digit
complement count: 544
8 characters: 2.183e+14 total, 1.649e+14 with a digit
length 8: 2.18e+14 passwords, 0.00692 years at 1e9 guesses per second
length 10: 8.39e+17 passwords, 26.6 years at 1e9 guesses per second
length 12: 3.23e+21 passwords, 1.02e+05 years at 1e9 guesses per second

Counting divisors

The product rule also answers questions that do not look like sequences of choices at first. How many positive divisors does 720 have? Factor it: \(720 = 2^4 \cdot 3^2 \cdot 5\). Every divisor has the form \(2^a 3^b 5^c\) with \(0 \le a \le 4\), \(0 \le b \le 2\) and \(0 \le c \le 1\), and different choices of exponents give different divisors because prime factorizations are unique (lesson 11). So choosing a divisor means choosing three exponents, and there are \(5 \cdot 3 \cdot 2 = 30\) divisors. In general, if \(n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}\), then \(n\) has \((e_1 + 1)(e_2 + 1) \cdots (e_r + 1)\) positive divisors.

Counting subsets

How many subsets does a set of \(n\) elements have? Walk through the elements one at a time and decide, for each, whether it is in the subset or not. That is a sequence of \(n\) choices with 2 options each, so there are \(2^n\) subsets, including the empty set and the whole set. Equivalently, subsets of \(\{1, \dots, n\}\) correspond exactly to bit strings of length \(n\): the \(k\)th bit is 1 when \(k\) is in the subset. This correspondence between subsets and strings is the first example of a bijection used for counting, an idea we return to often. If two sets can be matched up one to one, they have the same size, so counting one counts the other.

The pigeonhole principle

If \(n + 1\) pigeons fly into \(n\) holes, some hole contains at least two pigeons. Stated for functions: if \(f\) maps a set of size \(n + 1\) into a set of size \(n\), then \(f\) is not injective; two elements have the same image. The proof is a single line. If every hole held at most one pigeon there would be at most \(n\) pigeons. Despite its simplicity, the principle proves surprising results, because it guarantees a coincidence without telling us where it is.

Some quick consequences. Among any 13 people, two were born in the same month. Among any 367 people, two share a birthday, counting 29 February. In any set of 6 integers, two leave the same remainder when divided by 5, so their difference is divisible by 5. If a drawer holds black, brown and navy socks, taking 4 socks in the dark guarantees a matching pair.

The generalized pigeonhole principle sharpens the statement. If \(N\) objects are placed in \(k\) boxes, some box contains at least \(\lceil N / k \rceil\) objects, where \(\lceil x \rceil\) is the smallest integer greater than or equal to \(x\). Proof: if every box held at most \(\lceil N/k \rceil - 1\) objects, the total would be at most \(k(\lceil N/k \rceil - 1) < k(N/k) = N\), which is too few. For example, among 100 people at least \(\lceil 100/12 \rceil = 9\) were born in the same month.

The art in a pigeonhole proof lies in choosing the holes. Here the holes were odd parts, chosen because two numbers with the same odd part automatically divide one another. The code below tests the claim on random selections and also confirms that the set \(\{51, \dots, 100\}\) shows 51 cannot be lowered to 50.

import random
random.seed(260)

def odd_part(n):
    while n % 2 == 0:
        n //= 2
    return n

def find_divisible_pair(nums):
    seen = {}
    for x in sorted(nums):
        m = odd_part(x)
        if m in seen:
            return seen[m], x
        seen[m] = x
    return None

for trial in range(5):
    chosen = random.sample(range(1, 101), 51)
    a, b = find_divisible_pair(chosen)
    print(f"trial {trial}: {a} divides {b} (odd part {odd_part(a)})")

top = list(range(51, 101))
pairs = [(a, b) for a in top for b in top if a < b and b % a == 0]
print("pairs in 51..100 with one dividing the other:", pairs)

trial 0: 1 divides 2 (odd part 1)
trial 1: 5 divides 10 (odd part 5)
trial 2: 2 divides 4 (odd part 1)
trial 3: 3 divides 6 (odd part 3)
trial 4: 3 divides 6 (odd part 3)
pairs in 51..100 with one dividing the other: []

The birthday problem

The pigeonhole principle says 367 people are needed to guarantee a shared birthday. But a shared birthday becomes likely with far fewer people. Assume 365 equally likely birthdays and count by the complement: the number of ways for \(n\) people to have all different birthdays is \(365 \cdot 364 \cdots (365 - n + 1)\) by the product rule, out of \(365^n\) possible assignments. The probability that all birthdays differ is the ratio, and the probability of a shared birthday is one minus it. With 23 people the probability of a shared birthday already exceeds one half.

def p_shared(n, days=365):
    p_distinct = 1.0
    for k in range(n):
        p_distinct *= (days - k) / days
    return 1 - p_distinct

for n in (10, 20, 23, 30, 40, 50, 60):
    print(f"{n:2d} people: probability of a shared birthday {p_shared(n):.3f}")

10 people: probability of a shared birthday 0.117
20 people: probability of a shared birthday 0.411
23 people: probability of a shared birthday 0.507
30 people: probability of a shared birthday 0.706
40 people: probability of a shared birthday 0.891
50 people: probability of a shared birthday 0.970
60 people: probability of a shared birthday 0.994

The same calculation explains a fact about computer security. A hash function assigns a short fingerprint to each file; if fingerprints have \(N\) possible values, two files with the same fingerprint are likely to appear after only about \(\sqrt{N}\) files, not \(N\). Designers therefore choose fingerprint lengths with this square-root effect in mind.