Advanced counting: recurrences and the pigeonhole principle
Some counting problems are best solved by building up from smaller cases, and some by showing that a collision is unavoidable.
Counting with recurrences
Count bit strings of length \(n\) with no two consecutive 1s. A valid string ends in 0 (preceded by any valid string of length \(n-1\)) or in 01 (preceded by any valid string of length \(n-2\)). So \(a_n = a_{n-1} + a_{n-2}\), with \(a_1 = 2\), \(a_2 = 3\): a Fibonacci pattern.
Derangements
A derangement is a permutation with no item in its original place, like returning hats so that nobody gets their own. The number is \(D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}\right)\), from inclusion-exclusion. As \(n\) grows, the fraction of permutations that are derangements approaches \(\frac{1}{e} \approx 0.368\).
D_n \approx \frac{n!}{e}The pigeonhole principle
If \(n + 1\) objects go into \(n\) boxes, some box has at least two. The generalised form: if \(N\) objects go into \(k\) boxes, some box has at least \(\lceil N/k \rceil\). Among 100 people, at least \(\lceil 100/12 \rceil = 9\) share a birth month.
\left\lceil \frac{N}{k} \right\rceilPigeonhole in action
Choose any 6 integers from 1 to 10: two of them must sum to 11. The pairs (1,10), (2,9), (3,8), (4,7), (5,6) are 5 boxes, and 6 numbers must put two in one box. Pigeonhole arguments are short but often surprising.
Catalan numbers
The Catalan numbers \(C_n = \frac{1}{n+1}\binom{2n}{n}\), beginning 1, 1, 2, 5, 14, 42, count balanced bracket strings, ways to triangulate a polygon, and binary tree shapes. When the same sequence appears in very different problems, a hidden bijection usually connects them.
C_n = \frac{1}{n+1}\binom{2n}{n}Generating functions, briefly
A generating function encodes a sequence as coefficients of a power series: \(\sum a_nx^n\). Multiplying generating functions corresponds to combining counting choices. For example, the number of ways to make change for an amount is a coefficient in a product of geometric series.
Worked example
How many ways can you climb 6 stairs taking 1 or 2 steps at a time? Let \(s_n\) be the count; the last move is a 1-step or a 2-step, so \(s_n = s_{n-1} + s_{n-2}\), with \(s_1 = 1\), \(s_2 = 2\). Then \(s_3 = 3\), \(s_4 = 5\), \(s_5 = 8\), \(s_6 = 13\).
Common mistakes
Missing cases when setting up a recurrence. Using the pigeonhole principle without clearly defining the boxes. Confusing derangements with ordinary permutations. Off-by-one errors in initial conditions.
Key takeaways
Recurrences count by building from smaller cases and often produce Fibonacci-like sequences. Derangements use inclusion-exclusion and approach \(n!/e\). The pigeonhole principle guarantees collisions, with \(\lceil N/k \rceil\) in its general form. Catalan numbers count many recursive structures.
Flashcard
a_n = a_{n-1} + a_{n-2}
Check your understanding
At least how many of 50 people must share the same day of the week as their birthday this year?