Math Core

A generating function stores an entire sequence of counts as the coefficients of one polynomial or power series. The payoff is that combining choices becomes multiplying polynomials, and questions like "how many ways to reach a total of $n$ " become "what is the coefficient of $x^n$ ?"

Encoding choices as polynomials

Suppose one choice contributes an amount $a$ in $c_a$ ways. Record it as the polynomial $\sum c_a x^a$ . When you make several independent choices and add the amounts, the exponents add when you multiply, and each way of getting a total shows up exactly once in the product.

Definition

Generating function

The generating function of a sequence $c_0, c_1, c_2, \dots$ is $c_0 + c_1 x + c_2 x^2 + \dots$ . The coefficient of $x^n$ is written $[x^n]$ of the function.

Products count combinations

If choice $1$ has generating function $A(x)$ and choice $2$ has generating function $B(x)$ , and the totals add, then the number of ways to reach total $n$ is $[x^n]\,A(x)B(x)$ .

A fair die is $x + x^2 + x^3 + x^4 + x^5 + x^6$ . Rolling three dice is $(x + x^2 + \dots + x^6)^3$ , and the coefficient of $x^{10}$ counts the outcomes with sum $10$ .

Useful series

$\dfrac{1}{1 - x} = 1 + x + x^2 + \dots$ (any number of an item, each worth $1$ ).
$\dfrac{1}{1 - x^k} = 1 + x^k + x^{2k} + \dots$ (any number of an item worth $k$ ).
$1 + x + \dots + x^m = \dfrac{1 - x^{m+1}}{1 - x}$ (at most $m$ of an item).
$\dfrac{1}{(1 - x)^k} = \displaystyle\sum_{n \ge 0} \binom{n + k - 1}{k - 1} x^n$ , which is stars and bars in disguise.

The last two together give a fast way to extract dice coefficients:

$(x + \dots + x^6)^3 = x^3 \frac{(1 - x^6)^3}{(1 - x)^3}.$

Evaluating at special points

Plugging in numbers gives sums of coefficients. For $f(x) = \sum c_n x^n$ :

$f(1)$ is the sum of all coefficients.
$\dfrac{f(1) + f(-1)}{2}$ is the sum of the coefficients of even powers.
With $\omega$ a primitive $k$ th root of unity, the sum of $c_n$ over $n$ divisible by $k$ is $\dfrac{1}{k}\displaystyle\sum_{j=0}^{k-1} f(\omega^j)$ . This is the roots of unity filter.

The filter works because $1 + \omega^n + \omega^{2n} + \dots + \omega^{(k-1)n}$ equals $k$ when $k$ divides $n$ and $0$ otherwise.

Common mistake

Match each factor to one choice, with the right exponents. A coin worth $5$ cents is $\dfrac{1}{1 - x^5}$ , not $\dfrac{5}{1 - x}$ . Writing a factor for the wrong range (for example, allowing $0$ when a die can't show $0$ ) shifts every coefficient.

Worked example: Three dice

In how many of the $216$ outcomes of rolling three dice is the sum $10$ ?

We want $[x^{10}]\,x^3 (1 - x^6)^3 (1 - x)^{-3} = [x^7]\,(1 - 3x^6 + \dots)(1 - x)^{-3}$ . That is

$\binom{9}{2} - 3\binom{3}{2} = 36 - 9 = 27.$

Worked example: Making change

In how many ways can you make $10$ cents from $1$ -cent, $2$ -cent, and $5$ -cent coins?

The generating function is $\dfrac{1}{(1 - x)(1 - x^2)(1 - x^5)}$ . Extracting $[x^{10}]$ by the number of $5$ -cent coins: with none, $10$ cents from $1$ s and $2$ s can use $0$ to $5$ twos ( $6$ ways); with one, $5$ cents uses $0$ to $2$ twos ( $3$ ways); with two, $1$ way. The total is $10$ .

Worked example: A roots of unity filter

How many subsets of $\{1, 2, \dots, 10\}$ (including the empty set) have a sum divisible by $5$ ?

The generating function is $f(x) = (1 + x)(1 + x^2) \cdots (1 + x^{10})$ , and we want the sum of the coefficients of $x^n$ with $5 \mid n$ . Let $\omega$ be a primitive $5$ th root of unity. For $j = 1, 2, 3, 4$ , the numbers $\omega^{j}, \omega^{2j}, \dots, \omega^{10j}$ run through each $5$ th root of unity exactly twice, so

$f(\omega^j) = \Big(\prod_{r=0}^{4} (1 + \omega^r)\Big)^2.$

Since $\prod_{r=0}^{4} (z - \omega^r) = z^5 - 1$ , putting $z = -1$ gives $\prod (-1 - \omega^r) = -2$ , so $\prod (1 + \omega^r) = 2$ . Hence $f(\omega^j) = 4$ , and the count is

$\frac{f(1) + 4 \cdot 4}{5} = \frac{1024 + 16}{5} = 208.$

Tip

Euler's identity $\displaystyle\prod_{k \ge 1}(1 + x^k) = \prod_{k \ge 1}\frac{1}{1 - x^{2k-1}}$ says that the number of partitions of $n$ into distinct parts equals the number of partitions into odd parts. It follows from $1 + x^k = \dfrac{1 - x^{2k}}{1 - x^k}$ and cancelling.

Practice

Practice 1

Twelve identical candies are shared among Ann, Bea, and Cy. Ann must get an even number, Bea at most $4$ , and Cy a multiple of $3$ (zero counts as even and as a multiple of $3$ ). In how many ways can the candies be shared?