Combinatorics and discrete mathematics

Generating functions

Power series that encode a sequence of numbers as coefficients, turning combinatorics into algebra.

IntuitionWhat is a generating function?

Imagine a clothesline with infinitely many pegs, numbered $0, 1, 2, 3, \dots$ . To describe a sequence of numbers $a_0, a_1, a_2, \dots$ , you pin the number $a_n$ at peg $n$ . A generating function is this clothesline written as a single algebraic object: the number $a_n$ becomes the coefficient of $x$ $^n$ in a power series. The variable $x$ is never plugged in with a number — it just keeps every term in its own slot, so that adding, multiplying or shifting sequences becomes ordinary algebra on polynomials.

The curve is the cubic

1+x+x^2+x^3

, the first four terms of

\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n

, the generating function of the constant sequence

a_n=1

. Each coefficient (drag

a,b,c,d

) is one peg of the sequence packed into the curve.

SchoolPacking a sequence into a power series

Definition: Ordinary generating function

The ordinary generating function (OGF) of a sequence $a_0, a_1, a_2, \dots$ is the formal power series $G(x)=\sum_{n=0}^{\infty}a_nx^n$ . "Formal" means we treat this sum as an algebraic expression, not a function to be evaluated numerically; questions of convergence for particular values of $x$ are irrelevant to combinatorics.

G(x)=\sum_{n=0}^{\infty}a_nx^n

The simplest building block is the sequence $a_n=1$ for every $n \ge 0$ , whose OGF is the geometric series $\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n$ . This identity is the engine behind most generating-function arguments: it says that $\frac{1}{1-x}$ encodes "choose $n$ items from an unlimited supply, order irrelevant, one way each".

\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n

Common sequences and their ordinary generating functions
Sequence	Generating function
Constant, $a_n=1$	$\frac{1}{1-x}$
Linear, $a_n=n+1$	$\frac{1}{(1-x)^2}$
Fibonacci, $a_n=F_n$	$\frac{x}{1-x-x^2}$
Binomial row, $a_n=\binom{k}{n}$	$(1+x)^k$

UndergraduateFrom recurrences to closed forms

Theorem: Closed form for the Fibonacci generating function

Let $F_0=0,\ F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\ge2$ . Then the ordinary generating function $F(x)=\sum_{n=0}^{\infty}F_nx^n$ equals $F(x)=\frac{x}{1-x-x^2}$ .

Why is it true?

A linear recurrence with constant coefficients always turns into a simple algebraic (in fact, rational) equation once you multiply through by $x$ $^n$ and sum over all $n$ — the recurrence becomes multiplication by a polynomial in $x$ .

Proof

Multiply the recurrence $F_n=F_{n-1}+F_{n-2}$ (valid for $n\ge2$ ) by $x^n$ and sum over $n\ge2$ : $\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n$ .

The left side is $F(x)-F_0-F_1x=F(x)-x$ . The first sum on the right is $x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x)$ . The second sum is $x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x)$ .

So $F(x)-x=xF(x)+x^2F(x)$ , i.e. $(1-x-x^2)F(x)=x$ .

Solving for $F(x)$ gives $F(x)(1-x-x^2)=x$ , hence $F(x)=\frac{x}{1-x-x^2}$ , a single rational function that packs the entire infinite Fibonacci sequence.

Theorem: Partial fractions give Binet's formula

With $\varphi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ , the roots of $1-x-x^2$ give the closed form $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ for every $n\ge0$ .

Why is it true?

Every rational generating function with distinct linear factors in its denominator splits into a sum of simple geometric series, and each geometric series is read off directly as an explicit formula for the coefficient.

Proof

Factor the denominator: since the roots of $1-x-x^2=0$ are $x=1/\varphi$ and $x=1/\psi$ , we have $1-x-x^2=(1-\varphi x)(1-\psi x)$ .

Write $\frac{x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\psi x}$ for constants $A,B$ . Clearing denominators and matching the constant term and the coefficient of $x$ gives a linear system whose solution is $A=\frac{1}{\sqrt5}$ , $B=-\frac{1}{\sqrt5}$ , so $\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right)$ .

Expand each term as a geometric series: $\frac{1}{1-\varphi x}=\sum_{n\ge0}\varphi^nx^n$ and $\frac{1}{1-\psi x}=\sum_{n\ge0}\psi^nx^n$ .

Reading off the coefficient of $x^n$ on both sides gives $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ , known as Binet's formula.

UndergraduateReal-world applications and worked examples

Generating functions are a working tool, not just a theoretical curiosity: computer scientists use them to find exact and asymptotic running times of recursive algorithms, physicists use closely related partition functions in statistical mechanics, and probabilists encode entire probability distributions as generating functions to compute moments by differentiating instead of summing.

Example: Change-making with two coin types

In how many ways can an amount of $4$ be made using an unlimited supply of $1$ -unit and $2$ -unit coins, if the order of the coins does not matter?

Solution

Each way to make an amount is a choice of how many $1$ -coins and how many $2$ -coins to use, so the generating function is the product of the OGF for $1$ -coins, $\frac{1}{1-x}$ , and the OGF for $2$ -coins, $\frac{1}{1-x^2}$ : the combined generating function is $\frac{1}{(1-x)(1-x^2)}$ .

Expand the two factors as geometric series and multiply: $\left(\sum_{i\ge0}x^i\right)\left(\sum_{j\ge0}x^{2j}\right)$ . The coefficient of $x^4$ counts pairs $(i,j)$ with $i+2j=4$ and $i,j\ge0$ .

The valid pairs are $(4,0)$ , $(2,1)$ , $(0,2)$ , so there are $3$ ways: four $1$ -coins; two $1$ -coins and one $2$ -coin; two $2$ -coins.

Example: Binet's formula from the generating function

Use the closed form $F(x)=\frac{x}{1-x-x^2}$ and Binet's formula $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ to compute $F_5$ directly, without listing $F_0,\dots,F_4$ one by one.

Solution

By the theorem above, $\varphi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ are the roots feeding Binet's formula $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ .

Numerically, $\varphi\approx1.618$ and $\psi\approx-0.618$ , so $\varphi^5\approx11.09$ and $\psi^5\approx-0.09$ .

Then $F_5=\frac{1}{\sqrt5}(\varphi^5-\psi^5)\approx\frac{1}{\sqrt5}(11.09-(-0.09))=\frac{11.18}{\sqrt5}\approx5$ .

Indeed $F_5=5$ , matching the value obtained by iterating the recurrence $0,1,1,2,3,5$ — but Binet's formula lets us jump directly to any single $F_n$ without computing the ones before it.

What is the ordinary generating function for the constant sequence $a_n=1$ for every $n\ge0$ ?

What is the coefficient of $x^3$ in $\frac{1}{(1-x)^2}$ ?

Which of the following problems is most naturally solved using generating functions?

The generating function of the Fibonacci sequence $F(x)=\sum F_nx^n$ satisfies which closed form?

References

Herbert S. Wilf (1994). generatingfunctionology
Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics