# 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{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. Note by Calvin Lin
7 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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)

- 7 years, 2 months ago

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

Staff - 7 years, 2 months ago