A polynomial that counts

A counting problem produces a sequence: one answer for each size. The sequence is the thing wanted, and it is also, usually, the thing that is hard to get hold of, because the answers are related to each other in ways that a list of numbers hides.

The device is to stop treating the answers as a list and start treating them as the coefficients of a polynomial — or of an infinite series, when there are infinitely many. Then the two operations that combinatorics is made of become operations on polynomials, and a problem about counting becomes a problem about algebra, where there are techniques.

Why multiplication is the right operation #

Suppose a choice is made from box one and a choice from box two, and the total is recorded. Write each box as a polynomial: a term $x^v$ for each value $v$ the box offers, with a coefficient counting how many ways that value can be chosen. Then the number of ways of reaching a total of $n$ from the two boxes together is the coefficient of $x^n$ in the product.

The reason is a single line: multiplying out picks one term from each factor and adds the exponents, which is exactly the operation of choosing one value from each box and adding. Nothing has been assumed about what the boxes contain.

The rule that comes out of that picture has a name — the coefficients of a product are the convolution of the coefficients of the factors,

$$c_n = \sum_{i=0}^{n} a_i\, b_{n-i}$$

— and the name matters because the same sum turns up wherever independent things are combined. It is how the distribution of a sum of independent draws is built from the distribution of one, and it is why that construction and this one produce identical arithmetic on different objects.

Addition, meanwhile, is the or of the two operations: if a thing is either of the first kind or of the second, and the kinds do not overlap, the counts add and so do the series. Between them, addition and multiplication cover the two ways a combinatorial description usually reads, which is why so many descriptions translate directly into an expression.

A recursion becomes an equation #

The tactic pays best where a sequence is defined by a rule referring to itself, because a self-referential rule becomes an equation in one unknown.

Count the tilings of a $1 \times n$ strip by squares and dominoes. The first tile is a square, leaving a strip of $n-1$, or a domino, leaving $n-2$; so $t_n = t_{n-1} + t_{n-2}$ with $t_0 = t_1 = 1$. Now let $T(x) = \sum t_n x^n$ and multiply the recursion by $x^n$ and sum. Every term is a shifted copy of $T$, and the whole thing collapses to

$$T(x) = 1 + x\,T(x) + x^2\,T(x), \qquad\text{so}\qquad T(x) = \frac{1}{1 - x - x^2} .$$

The sequence is now a single rational function, and its coefficients can be recovered by expanding it — by long division, by partial fractions, or by reading off the recursion again.

Every figure in this family computes each coefficient twice: once by the series arithmetic the argument is about, and once by enumerating the objects the coefficient claims to count. A generating function is a bookkeeping device, and bookkeeping is exactly the kind of thing that can be internally consistent and wrong; listing the tilings is the check that the books describe the world.

What has been gained is not the numbers, which the recursion already gave. It is the closed form. Partial fractions on $1/(1-x-x^2)$ gives the golden ratio and its conjugate as the poles, and hence Binet’s formula for the Fibonacci numbers — an exact expression for the $n$th term with no earlier terms in it. The position of the poles is the growth rate, and that is the general lesson: the singularity nearest the origin governs how fast the coefficients grow, so a question about asymptotics becomes a question about where a function blows up.

A quadratic, and the numbers that solve it #

Some recursions are not linear, and the method survives.

A balanced path of $n$ up-steps and $n$ down-steps that never dips below its start decomposes at the moment it first returns to the start: an up-step, a smaller such path, a down-step, and another such path. In series form that description is $C = 1 + x\,C^2$, where the $x$ pays for the pair of steps and the two copies of $C$ are the two smaller paths.

That is a quadratic, and it can be solved:

$$C(x) = \frac{1 - \sqrt{1 - 4x}}{2x},$$

the negative root being rejected because $C(0)$ must be $1$. Expanding the square root by the binomial series gives the coefficients in closed form,

$$C_n = \frac{1}{n+1}\binom{2n}{n},$$

which is the Catalan number. The route from a description of the objects to a formula for how many there are went through algebra and never through a bijection — which is worth pausing on, because a bijective proof of the same formula exists and is beautiful and took considerably longer to find.

Two remarks on what “solve” means here. The square root is being expanded as a formal series, and no value of $x$ is ever substituted; the manipulation is legitimate because every coefficient of the result is determined by finitely many coefficients of the input. And the quadratic formula is being applied to an equation whose unknown is a series rather than a number, which needs the same justification and gets it the same way.

Products, not just powers #

The third standard shape is an infinite product, and the example is the oldest one in the subject.

To count the ways of writing $n$ as a sum of whole numbers with order disregarded, decide separately how many 1s to use, how many 2s, how many 3s. Using $k$ copies of the part $j$ contributes $jk$ to the total, so the decisions about part $j$ are the series $1 + x^j + x^{2j} + \cdots = 1/(1-x^j)$, and the whole count is

$$\prod_{j \ge 1} \frac{1}{1 - x^j}.$$

Each coefficient is a finite computation despite the product being infinite, because factors with $j > n$ contribute nothing to the coefficient of $x^n$.

The product form is where generating functions stop being bookkeeping and start proving things. Restrict the parts to odd numbers and the product becomes $\prod_{j \text{ odd}} 1/(1-x^j)$; restrict them to distinct parts and it becomes $\prod_{j \ge 1} (1 + x^j)$. Those two look unrelated. But $1 + x^j = (1-x^{2j})/(1-x^j)$, and substituting turns the second product into a telescoping cancellation that leaves exactly the first. So the partitions of $n$ into odd parts and the partitions of $n$ into distinct parts are equinumerous — Euler’s theorem, proved by an algebraic identity with no bijection in sight, though a diagram turned on its side supplies one for a different partition identity.

What the variable is not #

The variable $x$ is never given a value. That is not an oversight; it is the definition. A generating function is a formal power series: an infinite sequence of coefficients written with $x$ as punctuation, with addition and multiplication defined by the rules above and no notion of substituting a number.

This matters for two reasons. First, series that converge nowhere are perfectly good — $\sum n!\,x^n$ has radius of convergence zero and manipulates exactly as well as any other. Second, and more subtly, it means the manipulations need justifying on their own terms rather than by analysis. Multiplying two series is legitimate because each coefficient of the product is a finite sum; inverting a series is legitimate when its constant term is invertible, because the coefficients can then be solved for one at a time; substituting one series into another needs the inner one to have zero constant term, or the constant term of the result is an infinite sum and undefined.

When the series does converge, an extra tool becomes available and it is the powerful one: the analytic behaviour of the function controls the growth of the coefficients. The nearest singularity gives the exponential growth rate, and its type gives the polynomial correction. That is how one learns that the Catalan numbers grow like $4^n/n^{3/2}$ — from the square-root branch point at $x = 1/4$, not from the binomial coefficient. But nothing about the identities requires convergence, and keeping the two levels separate is what keeps the subject honest.

What the coefficients grow like #

One more thing falls out of the closed form, and it is the thing a list of numbers never gives: how fast the sequence grows.

For the tiling sequence, $1/(1 - x - x^2)$ has two poles, at the roots of $1 - x - x^2$, which are $1/\varphi$ and $-\varphi$ where $\varphi = (1+\sqrt5)/2$ is the golden ratio. Partial fractions splits the function into two pieces, each a geometric series, and the coefficients come out as

$$t_n = \frac{\varphi^{\,n+2} - (-\varphi)^{-(n+2)}}{\sqrt 5}.$$

The second term is smaller than a half for every $n$, so $t_n$ is the nearest whole number to $\varphi^{n+2}/\sqrt5$ — an exact formula and a growth rate in one line, from a factorisation of a quadratic.

The general statement behind that computation is worth stating even though nothing here proves it. The coefficients of a series grow like $r^{-n}$, where $r$ is the distance from the origin to the nearest point at which the function stops being well behaved, and the correction to that exponential is decided by what kind of misbehaviour it is: a simple pole gives a constant, a square root gives a factor of $n^{-3/2}$, a logarithm gives $1/n$. The Catalan numbers grow like $4^n n^{-3/2}$ for exactly that reason, and the $4$ is the reciprocal of the $1/4$ at which $\sqrt{1-4x}$ turns.

Where it came from #

The device is Euler’s, in the 1740s, and he used it for exactly the problem above: counting partitions. Before him, de Moivre had used series to solve linear recurrences in work on probability, and Laplace later turned the same construction into the transform that carries his name — the continuous version, where a sum over $n$ becomes an integral and $x^n$ becomes $e^{-st}$.

The nineteenth century added the analytic half, and the twentieth turned the whole thing into a systematic translation. The modern view is that a description of a class of objects — a tree is a root with a set of trees hanging from it, a permutation is a set of cycles — translates directly into an equation between series, without ever writing a recursion. The dictionary has entries for sequence, set, cycle and substitution, and it comes in two flavours: the ordinary one used here, and the exponential one, in which the coefficient of $x^n$ is divided by $n!$ and which is the right dictionary for labelled objects. Counting labelled trees is a problem for the exponential version.

Where it fails, and what it costs #

Not every sequence has a usable generating function. Every sequence has one, trivially; the question is whether it satisfies an equation simpler than the sequence itself. The number of partitions has a product but no rational or algebraic generating function; the primes have neither. When the series is no simpler than the list, nothing has been gained.

The translation can be harder than the counting. Setting up the equation requires a decomposition of the objects that is exhaustive and non-overlapping, and getting that wrong produces a series that counts something else. The check against enumeration in the figures here exists for exactly this failure, and it is the failure a beginner meets first: a decomposition that double-counts by one case.

Extracting coefficients is a second problem. A closed form for the generating function is not a closed form for the numbers. Sometimes the extraction is a binomial expansion; often it needs partial fractions, Lagrange inversion or a contour integral, and sometimes only the asymptotics are available.

What the pictures cannot show #

The figures show finitely many coefficients, and a generating function is an infinite object. Agreement of the first nine terms is evidence and not proof, and the proof is always the decomposition argument — which is prose, not a picture. Where the figure is genuinely doing the work is in the second row: those numbers come from listing tilings, paths and partitions, so what is checked is that the algebra describes the objects, at the sizes drawn.

Nor can a picture show the analytic half. The claim that the coefficients of $1/(1-x-x^2)$ grow like the golden ratio to the $n$ is a statement about the poles of a function of a complex variable, and the drawn coefficient rows do not contain it — the growth is visible in them, but the reason sits in a plane the figures here never enter.

The ladder from here #

Below: Catalan numbers, whose quadratic is the worked example above, and Pascal’s triangle, whose rows are the coefficients of $(1+x)^n$ and whose recursion is the simplest instance of the whole method. Sideways: partitions and their diagrams, where the same identities are proved by folding a picture instead, and the distribution of a sum, which is convolution again with probabilities in place of counts. Above: the analytic theory, where the location of a singularity is read as a growth rate.

What is worth carrying away #

The move being made here is one of the most transferable in mathematics: encode a family of objects as a single algebraic thing, so that the operations on the family become operations on the thing.

It works because the encoding is faithful in one direction — the series determines the sequence — and because the operations chosen, addition and multiplication, are exactly the ones the combinatorics already uses. When a description reads this or that and this and that, the translation writes itself, and the resulting equation can be attacked with tools that know nothing about tilings or paths. That is the whole trick, and everything else in the subject is a matter of building a better dictionary.