The equation a sequence satisfies

A recursion is a machine for producing a sequence one term at a time, and it is very bad at answering questions about the sequence as a whole. The Catalan recursion

$$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$$

computes $C_{40}$ in a moment and says nothing whatever about how fast the numbers grow, whether they have a closed form, or what fraction of all paths they represent. Every one of those questions is answered in a few lines by a single change of viewpoint: stop treating the sequence as a list and treat it as the coefficients of one object.

Generating functions have a reputation for being a formal trick, and the reputation is half deserved. Everything below the closed form is bookkeeping; everything above it is analysis; and the reason the method is worth learning is that the bookkeeping and the analysis are the same object seen from two sides.

Turning a sequence into a function #

Write

$$C(x) = C_0 + C_1 x + C_2 x^2 + C_3 x^3 + \cdots = \sum_{n \geq 0} C_n x^n.$$

Nothing has happened yet. $x$ is a formal marker, the series is not being evaluated anywhere, and the object is a bookkeeping device for holding a whole sequence in one symbol.

What makes the device worth having is what multiplication does. The coefficient of $x^n$ in a product $A(x)B(x)$ is

$$\sum_{k} A_k B_{n-k},$$

which is exactly the shape of the Catalan recursion. A convolution of two sequences is a product of two series, and that single correspondence is why the whole method exists: a recursion involving a sum over a split becomes an equation involving a product.

The Catalan recursion, read that way, says: the sequence shifted by one is the convolution of the sequence with itself. Shifting by one is multiplying by $x$. So

$$C(x) = 1 + x\,C(x)^2,$$

where the $1$ accounts for the empty object, which the convolution does not produce.

The equation can also be read straight off the objects, without going through the recursion at all. Every object on this ladder decomposes into a marker and two smaller copies of itself, and that sentence translates symbol for symbol: either (the $+$) empty (the $1$) or a marker (the $x$) followed by an object (a $C$) and another object (another $C$). Setting up a generating function correctly is usually a matter of writing the decomposition down in the right notation.

Solving it #

The equation is a quadratic in $C$:

$$xC^2 - C + 1 = 0,$$

so

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

There are two roots and only one of them is a power series. Take $x \to 0$: the numerator with the plus sign tends to $2$ while the denominator tends to $0$, so that branch blows up and cannot be a series with $C_0 = 1$. The minus sign gives $0/0$, and expanding the square root resolves it. So

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

It is worth seeing that the rejected branch is not nonsense, merely not this problem’s answer. Writing $D(x)$ for the plus-sign root, $D(x) = 1/x - C(x)$, which is a Laurent series with a pole at the origin — a perfectly respectable object that simply does not count anything, because a counting sequence has no term of negative index. The quadratic has two roots because it is a quadratic; only one of them is a generating function.

Choosing the branch by asking which one is finite at zero is the step that gets skipped, and it is where the combinatorics enters an otherwise purely algebraic calculation. The quadratic knows nothing about counting; the requirement that the answer be an honest power series with the right constant term is the counting.

Now expand. The binomial series for $(1 - 4x)^{1/2}$ has coefficients

$$\binom{1/2}{n}(-4)^n,$$

and simplifying the half-integer binomial coefficient — which is a short manipulation of double factorials — gives, after dividing by $2x$,

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

The closed form that the reflection argument produced by a subtraction has arrived a second way, from an equation rather than from a bijection. Neither derivation is a corollary of the other.

The expansion, carried out #

The step from the square root to the closed form is usually waved at, and it is short enough to do.

Newton’s binomial series says that for any exponent $\alpha$,

$$(1 + u)^\alpha = \sum_{n \geq 0} \binom{\alpha}{n} u^n, \qquad \binom{\alpha}{n} = \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}.$$

Put $\alpha = 1/2$ and $u = -4x$. The numerator of the coefficient is

$$\tfrac12 \cdot \left(-\tfrac12\right) \cdot \left(-\tfrac32\right) \cdots \left(\tfrac{3-2n}{2}\right),$$

which has $n$ factors, one positive and $n-1$ negative, and a $2^{-n}$ pulled out of all of them. Collecting the signs and the powers of two against the $(-4)^n$ from $u^n$ leaves

$$\binom{1/2}{n}(-4)^n = -\frac{2}{n}\binom{2n-2}{n-1}.$$

So $\sqrt{1-4x} = 1 - \sum_{n \geq 1} \frac{2}{n}\binom{2n-2}{n-1}x^n$, and dividing $1 - \sqrt{1-4x}$ by $2x$ shifts the index down by one and cancels the two:

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

Nothing in that calculation is about counting anything. It is the binomial series and some arithmetic with double factorials, and the fact that it lands on a formula about triangulated polygons is a consequence of the one combinatorial step taken earlier — writing down the equation.

What the equation knows that the recursion does not #

Having a closed form is the least of it. The generating function answers three questions the recursion cannot even be asked.

It is worth being clear about why any of the three is even a question the series can answer, since nothing so far has evaluated the series anywhere. The move is this: a power series with a positive radius of convergence defines an actual function on a disc, that function extends as far as its singularities allow, and the coefficients of the series are recoverable from the function by a contour integral. So a statement about where the function misbehaves becomes a statement about the integral, and hence about the coefficients. The series is doing two jobs at once — a formal one and an analytic one — and it is the analytic job that answers questions about size.

How fast does the sequence grow? The radius of convergence of $C(x)$ is the distance from the origin to its nearest singularity, and $\sqrt{1-4x}$ is singular at $x = 1/4$ and nowhere nearer. So the coefficients grow like $4^n$ up to sub-exponential corrections, and that is read off the location of the singularity without computing a single coefficient.

What is the correction? The type of the singularity gives it. A square-root singularity at $\rho$ contributes coefficients of order $\rho^{-n} n^{-3/2}$, by a standard transfer theorem, and the constant comes from the expansion around the singular point. The result is

$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.$$

Both of those readings are worth separating from the closed form, because the closed form is a piece of luck and they are not. Had the expansion produced nothing recognisable, the location $1/4$ and the square-root type would still have been visible in the equation, and the growth $4^n n^{-3/2}$ would still have followed. The asymptotics do not go through the closed form; they go through the singularity, which is why the method survives on problems where no closed form exists.

What fraction of all paths is this? All paths number $\binom{2n}{n} \sim 4^n/\sqrt{\pi n}$, and dividing gives $1/n$ up to a constant — which agrees with the exact answer $1/(n+1)$ obtained combinatorially. Two routes to the same statistic, one exact and one asymptotic, agreeing is the sort of consistency check that catches an algebra slip immediately.

The general principle is worth stating plainly, because it is the whole content of analytic combinatorics: the location of the nearest singularity controls the exponential growth, and its type controls the polynomial correction. Neither depends on the coefficients.

Where the square root comes from #

A square root in a generating function is not an accident of this problem. It is the signature of the decomposition being into two pieces.

An object that splits into one smaller object gives a linear equation and a rational generating function, whose coefficients are eventually periodic combinations of powers — the Fibonacci numbers are the standard case. An object that splits into two gives a quadratic, hence a square root, hence the $n^{-3/2}$ correction. Trees, bracket strings, non-crossing structures and every other family on this ladder have that $n^{-3/2}$ because they all split in two, and the exponent is a fact about the shape of the recursion rather than about any of them individually.

The converse reading is just as useful and is how the exponent is used in practice. Meeting a sequence measured in an experiment or produced by a simulation, fitting its growth and finding an exponent of $-3/2$ is evidence that whatever is being counted decomposes in two — that it is tree-like rather than chain-like. Exponents of $-1/2$ and $-5/2$ carry their own structural readings, and the catalogue of which exponents arise from which schemes is one of the genuinely predictive parts of the subject.

That is one of the sharper predictions the method makes. Meet an unfamiliar combinatorial family, notice it decomposes into a marker and two sub-objects, and the growth is $\rho^{-n}n^{-3/2}$ before anything has been counted.

The general tool the calculation is a special case of #

Solving the quadratic worked because the equation was a quadratic. There is a general theorem that does the same job for any equation of the form $C = \phi(xC)$ or $C = 1 + x\phi(C)$, and it is worth naming because it is the tool the subject actually uses.

Lagrange inversion says: if $w = x\phi(w)$ with $\phi(0) \neq 0$, then the coefficient of $x^n$ in $w$ is $\frac{1}{n}$ times the coefficient of $u^{n-1}$ in $\phi(u)^n$. That is a formula for the coefficients of an implicitly defined series in terms of the coefficients of an explicit one, and it needs no solving of anything.

Applied here with $\phi(u) = (1+u)^2$, the coefficient of $u^{n-1}$ in $(1+u)^{2n}$ is $\binom{2n}{n-1}$, and dividing by $n$ gives $\frac{1}{n}\binom{2n}{n-1}$, which is the Catalan number again after one identity. Two lines, no branch to choose, no square root to expand.

The reason to know both routes is that they fail in different places. The quadratic formula fails as soon as the decomposition is into more than four pieces. Lagrange inversion does not care how complicated $\phi$ is, and it fails instead when the equation is not of that shape at all — when the object’s decomposition involves the object at two different sizes, say, which is what happens for the sequences counting balanced trees.

Putting the two figures side by side is the honest summary of what a generating function is. It holds every one of those galleries, at every size, in a single symbol — and pays for that by showing none of them.

What it costs #

Three things go wrong with generating functions, and it is worth knowing them before reaching for one.

The manipulation can be purely formal or genuinely analytic, and the two are different subjects. Everything up to the closed form is formal — no series is evaluated anywhere, and $x$ never takes a value — and that part is valid for any sequence whatever. The asymptotic reading is analytic: it requires the series to converge somewhere, requires the singularity to be located, and requires a transfer theorem to convert a statement about the function into a statement about coefficients. Skipping from one to the other without noticing is the standard error.

The equation may not be solvable. $C = 1 + xC^2$ is a quadratic and yields to the formula. A family whose decomposition is into three pieces gives a cubic, which is solvable but unpleasant; four gives a quartic; five gives nothing. Beyond that, the useful information is extracted from the equation without solving it — the singularity’s location is where the implicit function theorem fails, which is computable from the equation directly — and that is how the method survives.

The formal and the analytic parts can also disagree about what is true. A divergent series is a perfectly good formal object — the sequence $n!$ has a generating function that converges nowhere, and formal manipulations of it are valid and useful. It has no singularity to locate, because it has no domain, so every asymptotic technique above is unavailable and the growth has to be got another way. Reaching for the singularity of a series that does not converge is the error this distinction exists to prevent, and it is easy to make because the algebra looks identical.

And the answer can be a series nobody recognises. The closed form here is a gift. Plenty of well-posed counting problems have generating functions with no closed form and no name, and the honest output is an asymptotic estimate and a recurrence. That is still more than the recursion gives.

Who found it, and in what order #

The chronology is instructive because the generating function came first and the objects came later, which is the reverse of how the subject is taught.

Euler, in correspondence with Christian Goldbach around 1751, asked how many ways a convex polygon can be cut into triangles, computed the first several by hand, and guessed the closed form. He could not prove it. Johann Segner supplied the recursion in 1758 — the convolution above — and Euler then observed that the recursion and the guessed formula agree as far as anybody had checked.

The gap was closed by Lamé in 1838 and, in the generating-function language, by Catalan in the same period, whose name attached to the sequence for reasons that have more to do with his notes being widely read than with priority. The objects the sequence counts multiplied afterwards, over two centuries.

What is worth taking from that is which step was hard. Producing the numbers was easy; guessing the formula was easy; connecting them required the observation that a convolution is a product, and that observation is the entire content of the method. Euler had the sequence, the formula and the recursion for eighty years without the sentence that joins them.

What the pictures cannot show #

The series is infinite and the table has ten entries. Agreement of two computations at ten terms is not a proof that they agree at all of them, and the proof is the binomial expansion, which is algebra with no picture in it. The figure’s value is that it would catch a wrong constant instantly, not that it establishes anything.

The singularity is not drawn. The whole asymptotic argument is about the behaviour of a function of a complex variable near $x = 1/4$, and every figure here plots real numbers indexed by whole numbers. The connection between the two — that a fact about a function near a point on the complex plane controls the size of numbers in a list — is the part with no picture, and it is the part that does the work.

And the convergence is drawn as a curve approaching a line. A limit cannot be shown by any finite plot, and the figure’s honest content is the assertion that the sequence is monotone and bounded in the range drawn, which is checked. That the limit is exactly one is the transfer theorem’s statement, not the plot’s.

Where the ladder goes next #

The last rung on this ladder stops counting and starts building: the triangulations become the corners of a solid, and the recursion that gives the generating function reappears as the shape of the solid’s faces.

Named here as a debt: the same equation, solved over a finite field rather than over the rationals, produces the Catalan numbers modulo a prime, and the pattern that appears is a fractal for Lucas’ reason. This rung sets that calculation up and does not carry it out.

Sideways, the method here is the general machinery a polynomial that counts sets up, the coefficients are read off Pascal’s triangle, and the singularity analysis is a cousin of the way a growth rate is read off a matrix’s largest eigenvalue — in both cases a global feature of an operator predicts the behaviour of a sequence it generates.

Sideways: one sequence counting everything is where the objects this equation counts were first put side by side, and sixteen trees on four points is a counting problem whose generating function behaves quite differently.

What is worth carrying away #

A recursion tells the next term. An equation tells the shape.

The change of viewpoint costs one paragraph — replace the sequence by a series, replace the convolution by a product — and it converts a rule for continuing a list into an algebraic object with a nearest singularity, a branch to choose and an expansion to take. The growth rate, the correction, the closed form and the fraction all fall out, and none of them was available before.

The habit worth taking is to look at where a generating function stops being nice rather than at the function. Its coefficients are decided by the nearest place it fails to be analytic, and that place is usually easy to find even when the function is not.