ISEGORIA / MATH ENCYCLOPEDIA
Combinatorics: counting by building
The cleanest way to show that two collections have the same size is to turn one into the other, piece by piece. A partition into odd parts becomes a partition into distinct parts by merging equal pieces; a mountain range of up and down steps becomes a tree and then a triangulated polygon. And once a count is packed into a generating function, the function’s nearest singularity in the complex plane says how fast the count grows.
Before you begin: Elementary counting, number theory and power series
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Odd parts and distinct parts
A partition of n writes it as a sum of positive integers, ignoring order. Euler proved that the partitions of n into odd parts are exactly as many as those into distinct parts: for n = 6 there are four of each, 5+1, 3+3, 3+1+1+1 and 1+1+1+1+1+1 against 6, 5+1, 4+2 and 3+2+1. Glaisher’s bijection makes this visible. Take a partition into odd parts and, whenever two parts are equal, merge them into one part twice as long. Merging never changes the sum or the odd part of a row, so it ends at a partition into distinct parts in which each odd number o has split its multiplicity into powers of two. Press Play to watch the merges, step through the partitions with the slider, and drag n on the count chart.
Worked example. Take \(n=12\) and the odd partition \(3+3+3+1+1+1\). Two 1s merge into a 2, giving \(3+3+3+2+1\); two 3s merge into a 6, giving \(6+3+2+1\), whose parts are distinct. In binary the three 3s became \(3=2+1\) copies, that is \(3\cdot2+3\cdot1\), and the three 1s became \(1\cdot2+1\cdot1\). Reading backwards, \(6=3\cdot2^1\) splits into two 3s and \(2=1\cdot2^1\) into two 1s, which recovers the start. There are 15 partitions of 12 of each kind, against \(p(12)=77\) in all.
Watch out. The order in which equal parts are merged does not matter: whatever the order, the multiplicity of each odd part ends up written in binary, and binary expansions are unique. That is why the process is a function at all. The generating-function proof on the formula line is shorter but explains less; the bijection says which partition goes to which. The count chart stops at 24 because listing every partition of larger n would be slow, not because anything changes.
Why does every partition into distinct parts come from exactly one partition into odd parts?
Every positive integer is uniquely \(o\cdot2^j\) with \(o\) odd. Splitting each distinct part \(o\cdot2^j\) into \(2^j\) copies of \(o\) gives a partition into odd parts with the same sum, and merging that back reproduces the distinct parts, because distinct powers of two in the same odd class are exactly the binary digits of the multiplicity. Two maps that undo each other are bijections.
2. Catalan objects in lockstep
The Catalan numbers 1, 1, 2, 5, 14, 42, 132, 429 count more than two hundred kinds of objects, and the reason is always a decomposition into two smaller objects of the same kind. A Dyck path, a walk of n up steps and n down steps that never goes below its start, splits at its first return to the axis into U A D B, with A and B smaller Dyck paths. Make A the left subtree and B the right subtree of a root node, and the path becomes a binary tree with n nodes. Stand a triangle on the base of a polygon with n + 2 corners, place the left subtree’s triangulation on its left side and the right subtree’s on its right, and the tree becomes a triangulation. Choose n, step through the objects, and pick a matched pair to see the same piece in all three.
Worked example. For \(n=3\) there are \(\binom63-\binom64=20-15=5\) Dyck paths: UDUDUD, UDUUDD, UUDDUD, UUDUDD and UUUDDD. Take UUDUDD: it first returns at the last step, so it is U A D with \(A=\) UDUD and \(B\) empty. The root therefore has only a left subtree, a node with a right child. In the pentagon with vertices 0 to 4 the root triangle stands on the side (0, 4) with apex 3, the left subtree fills the quadrilateral 0, 1, 2, 3 with the triangles (0, 1, 3) and (1, 2, 3), and the diagonals are 0–3 and 1–3.
Watch out. Many bijections between Catalan families exist and they do not all agree; this one is built from the first-return decomposition, so the root triangle corresponds to the first up step and its matching down step. A different convention, for instance last return, would pair the objects differently while counting them the same. The reflection count assumes paths that start and end at height zero.
Why does the reflection trick count the bad paths as C(2n, n+1)?
A bad path first touches height \(-1\) at some step. Reflect everything after that step, swapping ups and downs: the path now ends at \(-2\) instead of 0, so it has \(n-1\) ups and \(n+1\) downs. Every path with those step counts must cross \(-1\), and reflecting back after its first touch undoes the map, so bad paths and paths with \(n+1\) downs are in bijection, and there are \(\binom{2n}{n+1}\) of the latter.
3. Singularities predict growth
Pack a sequence into a power series A(z) = Σ aₙ zⁿ. The series converges inside a disc whose radius ρ is the distance to the nearest singularity, so the coefficients grow like (1/ρ)ⁿ, and the type of the singularity fixes the correction: a simple pole gives a constant, a square-root branch point gives n^{−3/2}. This is singularity analysis, and it turns a picture of a function in the complex plane into a counting formula. The left panel colours each z by the argument of A(z), with bands at powers of two in modulus, so poles and branch points stand out as places where every colour meets. Choose a sequence and drag n to compare the true coefficients with the prediction.
Worked example. For the Catalan numbers \(C(z)=(1-\sqrt{1-4z})/2z\), the nearest singularity is the branch point \(z=1/4\), where \(C(z)=2-2\sqrt{1-4z}+O(1-4z)\). Here \(\alpha=-1/2\), \(c=-2\) and \(\Gamma(-1/2)=-2\sqrt\pi\), so \(C_n\sim4^n/(\sqrt\pi\,n^{3/2})\). At \(n=10\) this predicts 18 708 against the true \(C_{10}=16\,796\), a ratio of 0.898; at \(n=100\) the ratio is 0.9889, close to the next-order estimate \(1-9/8n\).
Watch out. The transfer theorem needs more than the nearest singularity: the function must extend a little beyond the circle except near \(\rho\), in a so-called Delta domain, and every singularity on the circle contributes. Partitions fail this completely, since their generating function has the whole unit circle as a natural boundary; their asymptotics come from the saddle-point method instead. The colour plots of the algebraic functions use the principal square root, so the cuts drawn are a convention, not part of the function.
Why do the derangement fractions converge so much faster than the Catalan ratio?
Because \(e^{-z}/(1-z)\) has nothing but a simple pole at 1: subtracting \(e^{-1}/(1-z)\) leaves an entire function, whose coefficients shrink faster than any geometric rate, so \(D_n/n!-1/e\) is about \(1/(n+1)!\). The Catalan function has a branch point, whose expansion \((1-4z)^{1/2},(1-4z)^{3/2},\dots\) contributes corrections in powers of \(1/n\), and those die out slowly.