Generating Functions

This article is written by Alexander B., as a comment in Plentiful Pile of Polynomials.

Generating functions are useful tools for solving advanced counting problems. There are several types of generating functions; we will often use ordinary generating functions for the types of problems we are interested in. Consider the following problem:

How many ways are there to make a sum of $10$ using exactly one element from each of the following two sets: $\{2, 3, 6, 7\}$ and $\{ 3, 4, 5, 8\}$.

Solution: Consider the two polynomials $x^2 + x^3 + x^6 + x^7$ and $x^3 + x^4 + x^5 + x^8$. Note that for the first polynomial, the coefficient of $x^n$ is the number of ways of making a sum of $n$ using one element from the first set, and similarly for the second polynomial. For example, the coefficient of $x^4$ in the second polynomial is $1$, and there is $1$ way of making a sum of $4$ using only one element from the second set.

Now consider the product of the polynomials: $(x^2 + x^3 + x^6 + x^7) (x^3 + x^4 + x^5 + x^8).$

Before we expand out this product, let us consider what the coefficient of $x^n$ means in the polynomial product: it represents the number of ways of making a sum of $n$ taking exactly one number from each set. The expansion of the product is:

$\begin{aligned} (x^2 + x^3 + x^6 + x^7) & (x^3 + x^4 + x^5 + x^8) \\ & = x^5+2 x^6+2 x^7+x^8+x^9+3 x^{10}+3 x^{11}+x^{12}+x^{14}+x^{15}. \end{aligned}$

Note that the coefficient of $x^n$ is $0$ for $n > 15$, since we cannot make a sum greater than $15$ using one from each set. The same goes for $n < 5$.

When $n = 10$, the coefficient is $3$. This means that there are $3$ ways of making $10$. If we expand the product fully using the distributive formula, we see that the three $x^{10}$ terms come from the products of $x^2$ with $x^8$, $x^6$ with $x^4$, and $x^7$ with $x^3$. $_\square$

The idea of attaching meaning to the coefficient of $x^n$ without attaching any meaning at all to $x$ is the idea of a generating function. A generating function encodes the numbers of objects using formal power series, which are polynomials with (possibly) infinitely many terms (of integer powers). Note: The term formal is used because this is an algebraic concept, not an analytic concept.

In the above example, we could have simply counted the number of ways of making $10$ by inspection. However, generating functions are incredibly more useful if the polynomials may be expressed in a more compact form (such as using the geometric series sum), and then multiplication may lead to cancellation and an easier calculation.

Worked Example

1. Find the generating function for the face value of 1 die. Find the generating function for the sum of faces values of 2 dice.

Solution: For a standard six-sided die, there is exactly 1 way of rolling each of the numbers from 1 to 6. Hence, we can encode this as the power series $R_1(x) = x^1 + x^2 + x^3 + x^4 + x^5 + x^6$. The exponents represent the value rolled on the die, and the coefficients represent the number of ways this value can be attained.

For rolling 2 dice, we could likewise list out the possible sums, and arrive at

$R_2 (x) = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 5x^8 + 4x^9 + 3x^{10} + 2x^{11} + x^{12}$

A more direct method is to realize (from above) that $R_2(x) = [R_1(x) ]^2$, hence we can calculate it directly without having to count each individual term.

2. How many solutions in non-negative integers does the equation $a + b + c = 20$ have?

First, we look at a more general question of finding the number of solutions in non-negative integers to the equation $a + b + c = n$. Since the value of $a$ can be any non-negative integer $0,1,2,3, \ldots, i , \ldots$ (see note below), we can represent this as the generating function $A(x) = 1 + x + x^2 + \cdots + x^i + \cdots .$ We have the same generating function for the possible values of $b$ and $c$. So our generating function for the number of solutions is $A(x) \times B(x) \times C(x) = [A(x)]^3$. However, finding this product could be extremely tedious.

We instead transform $A(x)$ into the rational function $\frac{1}{1-x}$, which we recognize from the sum of a geometric progression. Thus, we are interested in $[A(x)]^3 = \frac{1}{(1-x)^3}$. This can be expanded using the negative binomial theorem, which gives

$\frac{1}{(1-x)^3} = {2 \choose 2} + {3 \choose 2} x + { 4 \choose 2 } x^2 + \ldots + { i+2 \choose 2 } x^ i + \ldots$

Hence, the answer when $n=20$ is given by ${ 22 \choose 2 }$. This agrees with what we know from the stars and bars method.

Note: It might be confusing why we allow $a$ to be any non-negative integer, even those which are larger than $n$, which clearly would not lead to a solution. Consider what would happen if we let $a = n+1$ or $a = n+2$ or any larger integer: In the final product of polynomials, the exponents of these terms would be larger than $n,$ so they will not contribute to the term we want, which has exponent $n.$

3. Use the generating function for two dice given above to find another pair of 6-sided dice with positive integer sides that gives the same set of possible results with the same probabilities.

The generating function $R_2$ can be expressed as

$R_2 (x) = [R_1 (x) ]^2 = \left[ x ( 1+x+x^2) (1+x)(1-x+x^2) \right] ^2$

George Sichermann realized that if we instead use the factors

$\begin{aligned} S_1 (x) & = (x)(x+1)(x^2+x+1) = x + 2x^2 + 2x^3 + x^4\\ S_2 (x) & = x (x+1)(x^2+x+1)(x^2-x+1)^2 = x + x^3 + x^4 + x^5 + x^ 6 + x^ 8 \\ \end{aligned}$

where $S_1$ corresponds to dice with face values of $1, 2, 2, 3, 3, 4$ and $S_2$ corresponds to dice with face values of $1, 3, 4, 5, 6, 8$, then we have

$R_2(x) = S_1 (x) \times S_2 (x)$

and hence they give the same set of possible results with the same probabilities.

Note: By testing various other products, we can show that there is no other pair of 6-sided dice with positive integer sides that gives the same set of possible results with the same probabilities.