Counting Principles & Pigeonhole

Counting answers "how many?" — how many passwords, how many paths, how many comparisons an algorithm makes. Almost every counting problem is built from a few simple rules.

#The sum rule

If a task can be done in one of m ways or one of n ways, with no overlap, there are m + n ways.

A student picks one elective from 5 CS electives or 3 maths electives: 5 + 3 = 8 choices.

#The product rule

If a task is a sequence of steps with m ways for the first and n ways for the second, there are m × n ways.

#Counting with the complement

Often it is easier to count what you don't want and subtract:

How many 8-bit strings contain at least one 1? All strings minus the all-zero string: 2⁸ − 1 = 255.

from itertools import product

passwords = ["".join(p) for p in product("ab1", repeat=4)]
with_digit = [p for p in passwords if "1" in p]
print(len(passwords), "passwords of length 4 over {a, b, 1}")
print(len(with_digit), "contain the digit, and 3^4 - 2^4 =", 3**4 - 2**4)

81 passwords of length 4 over {a, b, 1}
65 contain the digit, and 3^4 - 2^4 = 65

#The pigeonhole principle

If n + 1 (or more) pigeons fly into n holes, some hole contains at least two pigeons.

It sounds obvious, but it proves surprising things:

• Among any 13 people, two share a birth month.
• In any group of 367 people, two share a birthday.
• A hash table with m slots and m + 1 keys must have a collision.
• Among any 6 integers, two have the same remainder mod 5 — so their difference is divisible by 5.

#Generalised pigeonhole principle

If N objects go into k boxes, some box contains at least ⌈N/k⌉ objects.

• 100 students, 12 months → some month has at least ⌈100/12⌉ = 9 birthdays.
• How many cards must you draw from a standard deck to guarantee 3 of the same suit? Need ⌈N/4⌉ ≥ 3, so N = 2 × 4 + 1 = 9.

from math import ceil

def guarantee(per_box, boxes):
    return (per_box - 1) * boxes + 1          # smallest N with ceil(N/boxes) >= per_box

print("cards to guarantee 3 of a suit:", guarantee(3, 4))
print("people to guarantee 2 share a birth month:", guarantee(2, 12))
print("students so that 5 share a grade (grades O, A+, A, B+, P, F):", guarantee(5, 6))
print("minimum in the fullest month for 100 birthdays:", ceil(100 / 12))

cards to guarantee 3 of a suit: 9
people to guarantee 2 share a birth month: 13
students so that 5 share a grade (grades O, A+, A, B+, P, F): 25
minimum in the fullest month for 100 birthdays: 9

#Tree diagrams

When later choices depend on earlier ones, draw a tree. Example: how many bit strings of length 4 have no two consecutive 1s? Branching only on allowed bits gives 8 leaves: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010. (In general the count is a Fibonacci number — see Recurrence Relations.)