Generating Functions

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

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 1010 using exactly one element from each of the following two sets: {2,3,6,7} \{2, 3, 6, 7\} and {3,4,5,8} \{ 3, 4, 5, 8\} .

Solution: Consider the two polynomials x2+x3+x6+x7x^2 + x^3 + x^6 + x^7 and x3+x4+x5+x8x^3 + x^4 + x^5 + x^8. Note that for the first polynomial, the coefficient of xnx^n is the number of ways of making a sum of nn using one element from the first set, and similarly for the second polynomial. For example, the coefficient of x4x^4 in the second polynomial is 11, and there is 11 way of making a sum of 44 using only one element from the second set.

Now consider the product of the polynomials: (x2+x3+x6+x7)(x3+x4+x5+x8). (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 xnx^n means in the polynomial product: it represents the number of ways of making a sum of nn taking exactly one number from each set. The expansion of the product is:

(x2+x3+x6+x7)(x3+x4+x5+x8)=x5+2x6+2x7+x8+x9+3x10+3x11+x12+x14+x15.\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 xnx^n is 00 for n>15n > 15, since we cannot make a sum greater than 15 15 using one from each set. The same goes for n<5 n < 5 .

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

The idea of attaching meaning to the coefficient of xn x^n without attaching any meaning at all to x 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 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 R1(x)=x1+x2+x3+x4+x5+x6R_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

R2(x)=x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12 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 R2(x)=[R1(x)]2 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=20a + 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 a + b + c = n . Since the value of aa can be any non-negative integer 0,1,2,3,,i,0,1,2,3, \ldots, i , \ldots (see note below), we can represent this as the generating function A(x)=1+x+x2++xi+. A(x) = 1 + x + x^2 + \cdots + x^i + \cdots . We have the same generating function for the possible values of bb and cc. So our generating function for the number of solutions is A(x)×B(x)×C(x)=[A(x)]3A(x) \times B(x) \times C(x) = [A(x)]^3. However, finding this product could be extremely tedious.

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

1(1x)3=(22)+(32)x+(42)x2++(i+22)xi+ \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=20n=20 is given by (222) { 22 \choose 2 } . This agrees with what we know from the stars and bars method.

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

R2(x)=[R1(x)]2=[x(1+x+x2)(1+x)(1x+x2)]2 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

S1(x)=(x)(x+1)(x2+x+1)=x+2x2+2x3+x4S2(x)=x(x+1)(x2+x+1)(x2x+1)2=x+x3+x4+x5+x6+x8 \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 S1 S_1 corresponds to dice with face values of 1,2,2,3,3,41, 2, 2, 3, 3, 4 and S2S_2 corresponds to dice with face values of 1,3,4,5,6,8 1, 3, 4, 5, 6, 8 , then we have

R2(x)=S1(x)×S2(x) 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
5 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Adeetya Tantia - 5 years, 4 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...