Generating functions

Why can turning a counting problem into an infinite polynomial make it easier rather than harder?

Suppose you want to know how many ways there are to make 37 pence from coins, or how many binary strings of length n avoid two consecutive ones. These are finite, concrete questions. The standard advanced technique is to replace the question with an infinite object: a power series whose coefficients are all the answers at once.

That should look like a bad trade. We swapped one number for infinitely many, and a counting problem for algebra. Why would anyone expect that to help?

Start by noticing what is awkward about the sequence itself. A sequence of answers a₀, a₁, a₂, … is infinitely many separate facts. Even when a recurrence ties them together, the recurrence is a rule for producing facts one at a time. To ask a question about the whole sequence — what does it grow like, is there a closed form — you have nothing to point at. There is no single object in your hands.

So the first move is bookkeeping: write the whole sequence as the coefficients of one series, a₀ + a₁x + a₂x² + … . Now there is one object. Ask yourself whether that alone bought anything. Not yet — it is the same information, differently arranged.

The purchase comes at the second step. Ask what happens when you multiply two such series. To get the coefficient of xⁿ in the product, you take every way of splitting n into i plus j and add up the products of the corresponding coefficients. Read that sentence again as a combinatorialist would: every way of splitting a total between two independent choices. That is exactly what "build a structure by choosing a part of size i here and a part of size j there" means.

So multiplication of series performs the operation of combining independent choices, automatically, for all n at once. The exponent is not a number; it is a running tally of the size, and multiplication makes tallies add. That is the entire trick, and everything else is consequence.

Watch it work on coins. Using pennies alone, you can contribute 0, 1, 2, … pence, one way each: 1 + x + x² + …, which sums to 1/(1 - x). Twopence pieces contribute even amounts: 1/(1 - x²). Since the choices are independent, the number of ways to make each total using both is the coefficient in the product 1/((1 - x)(1 - x²)), and adding another coin denomination is one more factor. Notice what we did not do: we never enumerated a single combination.

Now the other direction, a recurrence. Fibonacci says F_n = F_n-1 + F_n-2. Multiply the recurrence by xⁿ and sum over all n — since shifting an index by one corresponds to multiplying the series by x, the infinitely many equations collapse into one equation about F(x), which rearranges to F(x) = x/(1 - x - x²). One rational function now contains every Fibonacci number, and splitting it by partial fractions and expanding each piece as a geometric series delivers Binet's closed form. The infinitely many facts became a single equation because the series turned an index shift into an algebraic operation.

Two things to be honest about. First, does the series converge? For this style of argument it does not need to: we work with formal power series, where x is a symbol and the only legal operations are those defined coefficient by coefficient. Convergence matters only when you later want to evaluate at a number or use analytic tools to estimate growth — and then it matters a great deal. Second, the method does not abolish difficulty; it moves it. Encoding the problem is usually easy, and the hard part becomes extracting the coefficient. When the resulting function is rational the extraction is routine; when it is not, it can be as hard as the problem you started with.

The misconception to clear away is that x is a quantity. It is not. Ask "what is x equal to?" and the answer, at least while you are manipulating formally, is that the question does not apply — x is a position marker, and the only thing that matters about xⁱ times x^j is that i and j add.

That also explains why the swap to an infinite object is not the extravagance it appears. You did not make the problem infinite; the problem was already infinite, sitting there as a family of questions indexed by n. What changed is that the whole family became one object that closed-form algebra can act on. Solving all of them together turns out to be easier than solving any one of them alone, because the relation between the answers is what the algebra grips.

And the choice of encoding is a real choice. The ordinary form used above suits problems where structures are combined without regard to labels. When the objects being counted carry distinguishable labels — permutations, set partitions, labelled trees — the exponential form, dividing each coefficient by n factorial, is the one whose multiplication matches how labelled structures combine. Picking the wrong encoding does not make the method fail loudly; it just fails to simplify.

• Exponential generating functions, and why labelled structures need a different encoding.
• Reading asymptotic growth off the singularities of the function, once convergence is back in play.
• Euler's use of infinite products to count integer partitions.
• Probability generating functions, where the same object stores a distribution and its moments.

Every term the collection defines is gathered in the glossary.