Generating Functions: A Powerful Counting Tool Explained

A generating function is a clever way of packaging an entire infinite sequence into a single algebraic expression. For a sequence a0, a1, a2, …, its ordinary generating function is the power series G(x) = a0 + a1 x + a2 x squared + …, where the coefficient of x to the power n is exactly the nth term.

This matters because operations on the function mirror operations on the sequence: adding functions adds sequences term by term, and multiplying functions combines sequences through a rule called convolution. Hard counting problems thus become algebra problems, which are often far easier.

Key Concepts

• Ordinary generating function: G(x) = sum from n = 0 to infinity of a_n times x to the power n; the sequence is stored as coefficients.
• Coefficient extraction: written [x to the power n] G(x), meaning the coefficient of x to the power n in the series, which equals a_n.
• Convolution: if C(x) = A(x)B(x) then c_n = a_0 b_n + a_1 b_{n-1} + … + a_n b_0.
• Exponential generating function: E(x) = sum of a_n x^n / n!; used when order matters, as in permutations.
• Formal power series: x is a formal symbol, not a number to substitute; only the algebra of coefficients matters.

Formulas

• Constant sequence 1, 1, 1, 1 and so on: G(x) = 1 / (1 - x). Every coefficient is 1.
• Geometric sequence 1, 2, 4, 8 and so on (a_n = 2 to the power n): G(x) = 1 / (1 - 2x).
• Fibonacci numbers (1, 1, 2, 3, 5, 8 and so on): G(x) = x / (1 - x - x squared).
• Product rule: A(x)B(x) generates c_n = sum from k = 0 to n of a_k b_{n-k}.
• Differentiation shift: x G'(x) generates n a_n, useful for sums involving n.

Worked Example

Let us verify that 1 / (1 - 2x) really is the generating function of the sequence 1, 2, 4, 8 and so on. Write the candidate series S = 1 + 2x + 4x squared + 8x cubed + …. Multiply by (1 - 2x): the constant term is 1. The x coefficient is 2 − 2 = 0, the x squared coefficient is 4 − 4 = 0, and the x cubed coefficient is 8 − 8 = 0. Higher coefficients cancel identically. So (1 − 2x)S = 1, giving S = 1/(1 − 2x), and the x cubed coefficient is 2 cubed = 8, the fourth term.

Common Misconceptions

• You must plug a number into x. Here x is a formal placeholder; the function stores coefficients, and substituting values is usually meaningless.
• Generating functions generate random numbers. Here generate means encode the sequence as coefficients, not create random values.
• There is only one kind. Ordinary GFs suit unlabelled counting (combinations, partitions); exponential GFs suit labelled counting (permutations).

Real-World Applications

• Combinatorics: coin-change combinations, integer partitions and lattice paths via multiplied GFs.
• Recurrence relations: solving recurrences like a_n = a_{n-1} + a_{n-2} via equations for G(x).
• Probability: moment generating functions simplify sums of independent random variables.
• Algorithm analysis: average-case runtimes of sorting and searching algorithms.

Generating functions turn sequence problems into algebra: encode the sequence as coefficients, manipulate the function, and read the answer back. This translation is one of the most powerful skills in counting mathematics.