Generating Functions, An Introduction

Introduction

At the heart of it, a generating function is a convenience, a form of concise notation.

Assume there are an ways to arrange n items, according to some bizarre rules that aren't important here. The sequence a0 a1 a2 etc is the solution to our combinatorial problem, specifying the number of arrangements for each n. However, the pattern may not be obvious, even after 100 terms. The sequence may follow a pattern; we just can't see it.

Sometimes the sequence holds the taylor coefficients for a function f. In other words, f(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + etc. In this case we say that f is the "generating function" that solves the combinatorial problem, through its taylor coefficients.

We want f to be analytic, so that it agrees with its power series, at least for a while. This allows us to fold f into other expressions, and evaluate things term by term. Unless you're a big fan of real/complex analysis, the details aren't important here. All the functions you know and love, like exp() and log() and sin(), are analytic.

Here is a silly example. There is exactly one way to put n green marbles into a box. We want a generating function whose coefficients are all 1. Set f(x) = 1/(1-x). That's the solution, expressed as a generating function: 1/(1-x).

Now ask how many ways you can select one marble from a batch of n different colored marbles. The answer is n, of course, but what is the generating function? Take the derivative of 1+x+x2+x3+…, and multiply by x, and the coefficients come out right. Thus the corresponding generating function is x/(1-x)2.

All this is a little bit backwards. We usually use generating functions to find the coefficients, rather than the other way around. You'll see this as we solve a few problems.