Mathematics.

enumerative combinatorics

Generating Functions

Combinatorics40 minDifficulty4 out of 10

You should know: sequences and series

Overview

A generating function encodes an infinite sequence of numbers as the coefficients of a formal power series, turning combinatorial questions about the sequence into algebraic questions about the series. The ordinary generating function of a sequence a₀,a₁,a₂,… is the power series ∑aₙxⁿ; operations like addition, multiplication, and substitution on generating functions correspond to natural combinatorial operations (like combining or interleaving structures) on the sequences they represent. Generating functions are central to solving recurrence relations, counting combinatorial structures, and proving identities.

Intuition

Think of a generating function as a clothesline: each coefficient aₙ is 'hung' on the peg xⁿ, and the whole infinite sequence is packaged into a single algebraic object. Multiplying two generating functions convolves their sequences — the coefficient of xⁿ in A(x)B(x) is ∑ₖ aₖb_{n-k} — which is exactly how you count the ways to split n items between two independent structures. This turns problems like 'in how many ways can I make change with these coins' or 'solve this linear recurrence' into problems of manipulating rational or algebraic expressions, then reading off coefficients (often via partial fractions).

Formal Definition

Definition

The ordinary generating function (OGF) of a sequence (aₙ) is the formal power series:

A(x)=∑n=0∞anxnA(x) = \sum_{n=0}^{\infty} a_n x^n
Ordinary generating function
11−x=∑n=0∞xn\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n
OGF of the all-ones sequence
(1+x)n=∑k=0n(nk)xk(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k
OGF for a row of Pascal's triangle
x1−x−x2=∑n=0∞Fnxn\frac{x}{1-x-x^2} = \sum_{n=0}^{\infty} F_n x^n
Generating function for the Fibonacci sequence

Worked Examples

  1. The OGF of the all-ones sequence is the geometric series.

    11−x=1+x+x2+x3+⋯\frac{1}{1-x} = 1+x+x^2+x^3+\cdots

  2. The coefficient of x⁵ is simply 1, matching a₅=1.

    [x5]11−x=1[x^5]\frac{1}{1-x} = 1

Answer: The coefficient of x⁵ is 1.

Practice Problems

Difficulty 4/10

What is the coefficient of x³ in the expansion of 1/(1-x)² (the OGF for the sequence a_n = n+1)?

Difficulty 5/10

Using the generating function (1+x)^5, find the coefficient of x^3.

Difficulty 6/10

How many ways can you make a sum of 4 using an unlimited supply of coins of value 1 and 2 (order doesn't matter, i.e. count partitions of 4 into parts of size 1 and 2)?

Quiz

The ordinary generating function of the sequence 1,1,1,1,... is:
Multiplying two generating functions A(x) and B(x) corresponds to which operation on their sequences?
The coefficient of x^2 in (1+x)^4 is:

Summary

  • A generating function packages an entire sequence as coefficients of a formal power series, turning combinatorics into algebra.
  • Multiplying generating functions corresponds to convolving their sequences, which models combining independent counting structures.
  • Generating functions solve recurrence relations (like Fibonacci) and counting problems (like coin change / partitions) by extracting coefficients.

References

  1. WebsiteWikipedia — Generating function