Level 8: Clever counting

Counting and combinations · level 8 of 8 · rough age 17 and beyond (a guide for parents; anyone can start anywhere)

The earlier levels gave you formulas: \(n!\), \(\dbinom{n}{k}\), stars and bars. This last level is about the problems no single formula answers, and the clever ideas mathematicians invented for them: counting by recursion (build the answer for \(n\) from smaller answers), reflection and inclusion-exclusion, pictures made of dots, polynomials that store counts, and counting up to symmetry. These are the first steps of the subject called combinatorics, studied at university and used everywhere from computer science to chemistry.

Lesson	You will be able to
Counting with recursion	Set up and solve a recurrence for tilings, staircases and the Tower of Hanoi, and prove the Hanoi count by induction
Catalan numbers	Recognise Catalan problems (brackets, mountain paths, triangulations) and prove \(C_n = \frac{1}{n+1}\binom{2n}{n}\) with the reflection trick
Derangements	Count the arrangements in which nothing is in its own place by inclusion-exclusion, and explain why the fraction tends to \(1/e\)
Partitions of a number	Count the ways to write a number as a sum, draw Ferrers diagrams, and show why odd parts and distinct parts give the same count
Generating functions	Store a counting sequence in a polynomial, multiply polynomials to combine choices, and find the Sicherman dice
Counting with symmetry, properly	Count necklaces and coloured cubes up to rotation by averaging fixed colourings (Burnside's lemma)

Previous: Level 7: the binomial theorem · This is the last level · Counting topic page