Generating functions

A counting problem usually asks for a whole sequence of answers, one for each size, and it would help to handle the sequence as a single object that can be added, multiplied and solved for.

The previous lesson solved every linear recurrence with constant coefficients by the characteristic equation: substitute $r^{n}$ , find the roots, fit the initial conditions. That method says nothing about a count built from independent choices, such as the ways to pay 50p in coins, and fails outright when earlier terms are multiplied together. This lesson packs a sequence into a power series, its generating function, so that operations on counts become algebra. It recovers Binet's formula without a guess, and finds the Catalan numbers, which no characteristic equation can reach.

A sequence as a power series

Given a sequence $a_{0}, a_{1}, a_{2}, \dots$ , its generating function is

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots

The power of $x$ is a label: the coefficient of $x^{n}$ is the $n$ th term, and nothing else is stored. The row $1, 3, 3, 1$ of Pascal's triangle becomes $(1 + x)^{3}$ , the binomial theorem read backwards. The notation $[x^{n}] A (x)$ means the coefficient of $x^{n}$ in $A (x)$ , so $[x^{2}] (1 + x)^{3} = 3$ .

Two series are added term by term and multiplied as polynomials are, so the coefficient of $x^{n}$ in $A (x) B (x)$ is $a_{0} b_{n} + a_{1} b_{n - 1} + \dots + a_{n} b_{0}$ . That is a finite sum: each coefficient of a sum or product needs only finitely many terms of the inputs, so every operation is ordinary arithmetic.

That is why convergence does not matter here. A series in this sense is a formal power series: an infinite list of coefficients written in a convenient notation, with $x$ never replaced by a number. The series $1 + x + 2 x^{2} + 6 x^{3} + 24 x^{4} + \dots$ , whose coefficients are the factorials $n!$ , converges for no $x$ other than $0$ , yet it is a perfectly good formal series and can be added and multiplied like any other. An identity between formal series means only that the two coefficient lists agree, place by place; nothing is ever summed.

Division needs one condition. If $A (x)$ has a nonzero constant term, there is exactly one series $B (x)$ with $A (x) B (x) = 1$ , found one coefficient at a time: the constant term of the product fixes $b_{0}$ , the coefficient of $x$ then fixes $b_{1}$ , and so on. So fractions like $\frac{x}{1 - x - x^{2}}$ below are genuine series, not symbols awaiting a value of $x$ .

The geometric series and its relatives

The most important series has every coefficient equal to $1$ . Multiply it by $1 - x$ :

(1 - x) (1 + x + x^{2} + x^{3} + \dots) = 1 + (x - x) + (x^{2} - x^{2}) + \dots = 1

Every coefficient after the constant cancels, and each cancellation involves only two terms, so this is a formal identity with no condition on $x$ . Therefore

\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots

The same cancellation works with $c x$ in place of $x$ , for any constant $c$ , so $\frac{1}{1 - c x}$ generates the powers $1, c, c^{2}, c^{3}, \dots$ . With $c = 2$ it generates $2^{n}$ ; with $c = - 1$ it generates $1, - 1, 1, - 1, \dots$ . Putting $x^{2}$ in place of $x$ gives $\frac{1}{1 - x^{2}} = 1 + x^{2} + x^{4} + \dots$ , which has a $1$ at every even power and a $0$ at every odd one, and in general $\frac{1}{1 - x^{c}}$ marks the multiples of $c$ .

Multiplying by $x$ shifts a sequence one place to the right, so $\frac{x^{3}}{1 - x}$ is $x^{3} + x^{4} + \dots$ . A finite sequence is a polynomial: $1 + x + x^{2} + x^{3}$ equals $\frac{1 - x^{4}}{1 - x}$ , the finite geometric sum.

These pieces are enough to read off many coefficients. For example, $[x^{8}] (\frac{x^{2}}{1 - 3 x} + \frac{5}{1 - x})$ is the coefficient of $x^{6}$ in $\frac{1}{1 - 3 x}$ , which is $3^{6} = 729$ , plus $5$ , giving $734$ . Each problem below turns a count into a product or quotient of such pieces, then reads the coefficients back.

Multiplying counts combined choices

Multiplying series has a meaning in counting. Suppose there are $a_{k}$ ways to make a choice of size $k$ from one source and $b_{j}$ ways from a second, independent source. A combined choice of total size $n$ takes some size $k$ from the first and the remaining $n - k$ from the second, in $a_{k} b_{n - k}$ ways by the product rule. Adding over $k$ by the sum rule gives

c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}

which is exactly the coefficient of $x^{n}$ in $A (x) B (x)$ . This sum is the convolution of the two sequences, and it is the whole reason generating functions count: exponents add, so $x^{k}$ from one factor meets $x^{n - k}$ from the other on $x^{n}$ .

One die generates $x + x^{2} + \dots + x^{6}$ , the exponent recording the score. In its square the coefficient of $x^{7}$ collects $x^{1} x^{6}$ up to $x^{6} x^{1}$ , the six ways to throw $7$ with two dice, and the cube gives the $27$ ways to throw $10$ with three.

Now take $k$ copies of $\frac{1}{1 - x}$ , each standing for an unlimited supply of one kind of object, with the exponent counting how many are taken. The coefficient of $x^{n}$ in $\frac{1}{(1 - x)^{k}}$ counts the ways to write $n = n_{1} + n_{2} + \dots + n_{k}$ with every $n_{i} \geq 0$ , which is a selection of $n$ objects from $k$ kinds with repetition. Stars and bars, from an earlier lesson (arrange $n$ stars and $k - 1$ dividing bars in a row), counts these as $(\binom{n + k - 1}{k - 1})$ . So

\frac{1}{(1 - x)^{k}} = \sum_{n \geq 0} (\binom{n + k - 1}{k - 1}) x^{n}

and in particular $\frac{1}{(1 - x)^{2}}$ generates the numbers $n + 1$ .

Example. A shop sells lemon, cherry and mint sweets. How many bags of $10$ sweets contain an even number of cherry and at most one mint?

Each flavour becomes a factor recording the allowed amounts. Lemon may be any number, $\frac{1}{1 - x}$ ; cherry must be even, $\frac{1}{1 - x^{2}}$ ; mint is $0$ or $1$ , $1 + x$ . The bags are counted by the product

\frac{1}{1 - x} \cdot \frac{1}{1 - x^{2}} \cdot (1 + x) = \frac{1}{(1 - x)^{2}}

because $1 - x^{2} = (1 - x) (1 + x)$ and the factor $1 + x$ cancels. So there are $n + 1$ bags of $n$ sweets, and $11$ bags of $10$ . A direct check agrees: with no mint the cherries number $0, 2, \dots, 10$ , six ways, and with one mint they number $0, 2, \dots, 8$ out of nine, five ways.

Now you. A basket of fruit holds an even number of apples, a multiple of $5$ bananas, at most $4$ oranges and at most $1$ pear. How many baskets of $20$ fruit are there?

Answer

The factors are $\frac{1}{1 - x^{2}}$ , $\frac{1}{1 - x^{5}}$ , $\frac{1 - x^{5}}{1 - x}$ for the oranges (the finite sum $1 + x + \dots + x^{4}$ ) and $1 + x$ . The $1 - x^{5}$ cancels, and $\frac{1 + x}{1 - x^{2}} = \frac{1}{1 - x}$ , so the product is $\frac{1}{(1 - x)^{2}}$ again and there are $21$ baskets.

Making change

In how many ways can 50p be paid using 1p, 2p, 5p, 10p and 20p coins, with any number of each? Order does not matter: two 20p and a 10p is one way, whichever coin is handed over first. Each coin type is an unlimited supply whose contribution comes in multiples of its value, so the 5p coins contribute $1 + x^{5} + x^{10} + \dots = \frac{1}{1 - x^{5}}$ , and the answer is the coefficient of $x^{50}$ in

P (x) = \frac{1}{(1 - x) (1 - x^{2}) (1 - x^{5}) (1 - x^{10}) (1 - x^{20})}

Its coefficients have no tidy closed form, but they are fast to compute. Suppose $A (x)$ counts the ways using some coins, and $B (x) = \frac{A (x)}{1 - x^{c}}$ adds a coin worth $c$ . Then $B (x) (1 - x^{c}) = A (x)$ , and comparing coefficients of $x^{n}$ gives $b_{n} - b_{n - c} = a_{n}$ , that is,

b_{n} = a_{n} + b_{n - c}

with $b_{n} = a_{n}$ for $n < c$ . In words, a payment either uses no coin worth $c$ or uses one that can be removed. So each new coin is one pass along a row, adding the entry $c$ places back.

Start with 1p coins alone, which give one way for every amount. Adding 2p coins gives $1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6$ for amounts $0$ to $10$ , the value $⌊ n / 2 ⌋ + 1$ from choosing how many 2p coins to use. Adding 5p coins then gives $1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10$ . Carried on to 50p, the rows end at $26$ with 1p and 2p only, then $146$ with 5p, $341$ with 10p, and finally

[x^{50}] P (x) = 450

A brute force count by computer agrees. Allowing a 50p coin as well adds exactly one way, the coin itself, for $451$ .

Example. In how many ways can 10p be made from 1p, 2p and 5p coins?

The last entry of the 1p, 2p and 5p row is $10$ , from the step $b_{10} = a_{10} + b_{5} = 6 + 4$ : six ways with no 5p coin, and four ways to make the rest once one 5p coin is set aside. Listing confirms it: with two 5p coins there is one way, with one 5p coin the remaining 5p takes $0$ , $1$ or $2$ of the 2p coins, three ways, and with none the 10p takes $0$ to $5$ of the 2p coins, six ways, and $1 + 3 + 6 = 10$ .

Now you. In how many ways can 20p be made from 1p, 2p, 5p and 10p coins?

Answer

Extend the 1p and 2p row to $20$ , where it ends at $11$ , then add 5p coins to get $1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 18, 20, 22, 24, 26, 29$ . Adding 10p coins changes each entry from $10$ on by adding the new entry ten places back: $b_{10} = 10 + 1 = 11$ and $b_{20} = 29 + b_{10} = 29 + 11 = 40$ . There are $40$ ways.

Fibonacci by partial fractions

A recurrence becomes an equation for its generating function. Let $F (x) = \sum F_{n} x^{n}$ for the Fibonacci numbers, with $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ . Shifting by one and two places gives $x F (x)$ and $x^{2} F (x)$ , whose coefficients of $x^{n}$ are $F_{n - 1}$ and $F_{n - 2}$ . So in $F (x) - x F (x) - x^{2} F (x)$ the coefficient of $x^{n}$ is $F_{n} - F_{n - 1} - F_{n - 2} = 0$ for every $n \geq 2$ , and only the first two terms survive: the constant $F_{0} = 0$ and $(F_{1} - F_{0}) x = x$ . Hence

F (x) = \frac{x}{1 - x - x^{2}}

The whole sequence is now one fraction. To read its coefficients, factor the denominator as $(1 - φ x) (1 - ψ x)$ . Expanding, this needs $φ + ψ = 1$ and $φ ψ = - 1$ , so $φ$ and $ψ$ are the roots of $t^{2} = t + 1$ : the golden ratio $φ = \frac{1 + \sqrt{5}}{2}$ and $ψ = \frac{1 - \sqrt{5}}{2}$ , with $φ - ψ = \sqrt{5}$ . Then split the fraction into partial fractions, a sum of the simple kind whose coefficients are known:

\frac{1}{1 - φ x} - \frac{1}{1 - ψ x} = \frac{(1 - ψ x) - (1 - φ x)}{(1 - φ x) (1 - ψ x)} = \frac{(φ - ψ) x}{1 - x - x^{2}}

Dividing by $φ - ψ = \sqrt{5}$ gives $F (x)$ . Each piece is a geometric series, $\frac{1}{1 - φ x}$ generating $φ^{n}$ , so

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}

which is Binet's formula from the previous lesson. There it came from guessing that solutions look like $r^{n}$ ; here nothing was guessed, and the powers appear because each factor of the denominator is a geometric series. A forcing term, which needed a separate particular solution before, is just another series on the right.

Example. Solve the Tower of Hanoi recurrence $T_{n} = 2 T_{n - 1} + 1$ , $T_{0} = 0$ , with a generating function.

For $n \geq 1$ the coefficient of $x^{n}$ in $T (x) - 2 x T (x)$ is $T_{n} - 2 T_{n - 1} = 1$ , and the constant term is $T_{0} = 0$ . So $(1 - 2 x) T (x) = x + x^{2} + \dots = \frac{x}{1 - x}$ , and

T (x) = \frac{x}{(1 - x) (1 - 2 x)} = \frac{1}{1 - 2 x} - \frac{1}{1 - x}

where the split checks because $(1 - x) - (1 - 2 x) = x$ . Reading coefficients, $T_{n} = 2^{n} - 1$ , as unrolling found.

Now you. Solve $a_{n} = a_{n - 1} + 6 a_{n - 2}$ with $a_{0} = 1$ and $a_{1} = 8$ by a generating function, and find $a_{6}$ .

Answer

$(1 - x - 6 x^{2}) A (x) = a_{0} + (a_{1} - a_{0}) x = 1 + 7 x$ , and $1 - x - 6 x^{2} = (1 - 3 x) (1 + 2 x)$ . Writing $\frac{1 + 7 x}{(1 - 3 x) (1 + 2 x)} = \frac{P}{1 - 3 x} + \frac{Q}{1 + 2 x}$ needs $P + Q = 1$ and $2 P - 3 Q = 7$ , so $P = 2$ and $Q = - 1$ . So $a_{n} = 2 \cdot 3^{n} - (- 2)^{n}$ , and $a_{6} = 1458 - 64 = 1394$ , which the recurrence confirms: $14, 62, 146, 518, 1394$ .

The Catalan numbers

How many ways can $n$ pairs of brackets be written so that they match? With three pairs there are five: $((()))$ , $(() ())$ , $(()) ()$ , $() (())$ and $() () ()$ . Call the number $C_{n}$ , with $C_{0} = 1$ for the empty string. A nonempty matched string opens with a bracket, and that bracket closes somewhere, so the string is $(A) B$ where $A$ and $B$ are matched strings. If the whole has $n + 1$ pairs and $A$ has $k$ , then $B$ has $n - k$ , and

C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}

This recurrence multiplies earlier terms together, so no characteristic equation applies. But the sum is a convolution, the coefficient of $x^{n}$ in $C (x)^{2}$ . Multiplying by $x$ to shift it into place and adding back $C_{0}$ gives

C (x) = 1 + x C (x)^{2}

a quadratic in $C (x)$ . The quadratic formula gives $C (x) = \frac{1 \pm \sqrt{1 - 4 x}}{2 x}$ , and the sign is forced: with the plus sign the numerator has constant term $2$ , so dividing by $2 x$ would leave a term $\frac{1}{x}$ . Taking the minus sign, the formal square root $\sqrt{1 - 4 x}$ is the one series with constant term $1$ whose square is $1 - 4 x$ , and Newton's generalisation of the binomial theorem to the power $\frac{1}{2}$ gives it:

\sqrt{1 - 4 x} = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} - \dots

Subtracting from $1$ and dividing by $2 x$ gives $C (x) = 1 + x + 2 x^{2} + 5 x^{3} + 14 x^{4} + \dots$ , matching the count of five for three pairs. The general coefficient of $x^{m}$ in the root, for $m \geq 1$ , is $(\binom{1 / 2}{m}) (- 4)^{m}$ . Its numerator $\frac{1}{2} (\frac{1}{2} - 1) \dots (\frac{1}{2} - m + 1)$ is $(- 1)^{m - 1}$ times $1 \cdot 3 \cdot 5 \dots (2 m - 3)$ over $2^{m}$ , and the odd product equals $\frac{(2 m - 2)!}{2^{m - 1} (m - 1)!}$ . Multiplying by $(- 4)^{m}$ and dividing by $m!$ leaves $- \frac{2}{m} (\binom{2 m - 2}{m - 1})$ . Put $m = n + 1$ , negate and halve, and

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

So $C_{4} = \frac{70}{5} = 14$ and $C_{10} = \frac{184 756}{11} = 16 796$ . The same numbers count the ways to cut a convex polygon with $n + 2$ sides into triangles, which Euler worked out in 1751; they are named after Eugène Catalan, who met them counting bracketings in 1838, and a later lesson meets them again counting binary trees.

The end of counting

Generating functions close the counting half of the course because they absorb what came before. The binomial theorem is the generating function $(1 + x)^{n}$ ; stars and bars is the coefficient of $\frac{1}{(1 - x)^{k}}$ ; a linear recurrence is a rational function taken apart by partial fractions; and a count built from independent pieces, like a pile of coins, is a product. The limits are honest ones: many generating functions, $P (x)$ for coins among them, have no closed formula for their coefficients, and then the method becomes an efficient way to compute rather than a formula.

Everything so far has asked how many. The second half of the course asks what the integers themselves are made of, beginning with the most basic relation between two of them: whether one divides the other. The next lesson proves that division always leaves a well defined remainder, and turns that fact into Euclid's algorithm for the greatest common divisor, one of the oldest algorithms still in use.