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 using exactly one element from each of the following two sets: and .
Solution: Consider the two polynomials and . Note that for the first polynomial, the coefficient of is the number of ways of making a sum of using one element from the first set, and similarly for the second polynomial. For example, the coefficient of in the second polynomial is , and there is way of making a sum of using only one element from the second set.
Now consider the product of the polynomials:
Before we expand out this product, let us consider what the coefficient of means in the polynomial product: it represents the number of ways of making a sum of taking exactly one number from each set. The expansion of the product is:
Note that the coefficient of is for , since we cannot make a sum greater than using one from each set. The same goes for .
When , the coefficient is . This means that there are ways of making . If we expand the product fully using the distributive formula, we see that the three terms come from the products of with , with , and with .
The idea of attaching meaning to the coefficient of without attaching any meaning at all to 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 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.
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 . 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
A more direct method is to realize (from above) that , hence we can calculate it directly without having to count each individual term.
2. How many solutions in non-negative integers does the equation have?
First, we look at a more general question of finding the number of solutions in non-negative integers to the equation . Since the value of can be any non-negative integer (see note below), we can represent this as the generating function We have the same generating function for the possible values of and . So our generating function for the number of solutions is . However, finding this product could be extremely tedious.
We instead transform into the rational function , which we recognize from the sum of a geometric progression. Thus, we are interested in . This can be expanded using the negative binomial theorem, which gives
Hence, the answer when is given by . This agrees with what we know from the stars and bars method.
Note: It might be confusing why we allow to be any non-negative integer, even those which are larger than , which clearly would not lead to a solution. Consider what would happen if we let or or any larger integer: In the final product of polynomials, the exponents of these terms would be larger than so they will not contribute to the term we want, which has exponent
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 can be expressed as
George Sichermann realized that if we instead use the factors
where corresponds to dice with face values of and corresponds to dice with face values of , then we have
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.