# This note has been used to help create the Generating Functions wiki

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{align} (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{align}

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{align} 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{align}

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.

Note by Calvin Lin
4 years, 7 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

I guess there is a typo in question 3.. in R2, it will be (1+x) instead of (1-x)

- 4 years, 6 months ago

Thanks, fixed the typo. It doesn't affect the rest of the proof.

Staff - 4 years, 6 months ago