7.3: Using Generating Functions To Count Things

As you might expect of something that has come up in our study of enumeration, generating functions can be useful in solving problems about counting. We’ve already seen from the Binomial Theorem, that the coefficient of \(x^r\) in \((1 + x)^n\), is \(\binom{n}{r}\), so the generating function for the binomial coefficients is \((1 + x)^n\). In fact, the argument we used to prove the Binomial Theorem explained why this works: if we want the coefficient of \(x^r\) in \((1 + x)^n\), it must be the number of ways of choosing the \(x\) from \(r\) of the \(n\) factors, while choosing the \(1\) from the other factors. We can use similar reasoning to solve other counting questions.

Example \(\PageIndex{1}\)

The grocery store sells paper plates in packages of \(1\), \(5\), \(20\), or \(75\). In how many different ways can Jiping buy a total of \(95\) paper plates?

Solution

We model this with generating functions. The exponent of \(x\) will represent the number of paper plates, and the coefficient of \(x^n\) will represent the number of ways in which he can buy \(n\) paper plates.

We begin by considering the single paper plates that he buys. He could buy \(0\), or \(1\), or any other number of these, so we represent this by the generating function.

\(1 + x + x^2 + x^3 + x^4 + . . . = \sum_{i=0}^{\infty} x^i = \dfrac{1}{(1-x)} \)

There is exactly one way of choosing any particular number of single paper plates (we are assuming the plates are indistinguishable).

Now, he could also buy any number of packages of \(5\) paper plates, but the difference is that each package he buys contributes \(5\) to the exponent, since it represents \(5\) plates. We represent this by the generating function

\(1 + x^5 + x^{10} + x^{15} + . . . = \sum_{i=0}^{\infty} x^{5i} = \dfrac{1}{(1-x^5)} \)

where \(i\) represents the number of packages he buys.

Similarly, he could buy any number of packages of \(20\) paper plates, and each package he buys contributes \(20\) to the exponent, since it represents \(20\) plates. We represent this by the generating function

\(1 + x^{20} + x^{40} + x^{60} + . . . = \sum_{i=0}^{\infty} x^{20i} = \dfrac{1}{(1-x^{20})} \)

where \(i\) represents the number of packages he buys.

Finally, he could buy any number of packages of \(75\) paper plates, and each package he buys contributes \(75\) to the exponent, since it represents \(75\) plates. We represent this by the generating function

\(1 + x^{75} + x^{150} + x^{225} + . . . = \sum_{i=0}^{\infty} x^{75i} = \dfrac{1}{(1-x^{75})} \)

where \(i\) represents the number of packages he buys.

Obviously, for this particular question, Jiping can’t actually buy \(2\) or more of the packages of \(75\) paper plates, since that would be too many. There are also limits on the number of packages of other sizes that he should buy since he doesn’t want to end up with more than \(95\) plates. So for this problem, we can assume that the generating function for the full problem actually looks like this:

\((1 + x + x^2 + . . . + x^{95})(1 + x^5 + x^{10} + . . . + x^{95})(1 + x^{20} + x^{40} + x^{60} + x^{80})(1 + x^{75})\)

and we are looking for the coefficient of \(x^{95}\).

We could multiply this all out to get our answer. We could be a bit more clever, recognising that we only really care about the coefficient of \(x^{95}\), and break the problem down into cases depending on how many of the bigger packages he buys. It should be noted that the generating function hasn’t really saved us any work. This approach involves saying, “Well, if he takes the \(x^{75}\) from the final factor, then there are only six ways to contribute to the coefficient of \(x^{95}\): he could choose an \(x^{20}\) from the previous factor and \(1\)s from both of the other factors; or he could choose \(1\) from the third factor and any of \(1\), \(x^5\), \(x^{10}\), \(x^{15}\), or \(x^{20}\) from the second factor, in each case, choosing whichever term from the first factor brings the exponent up to \(95\).” This is exactly equivalent to saying, “Well, if he buys a package of \(75\) plates, then there are only six ways to buy \(95\) plates in total: he could buy a package of \(20\) plates and be done; or he could buy \(0\), \(1\), \(2\), \(3\), or \(4\) packages of \(5\) plates, in each case, buying as many single plates as are needed to bring the total up to \(95\).”

So what’s the advantage of the generating function approach? It comes in a couple of ways. First, it solves multiple problems at once: if we actually multiply out the generating function above, we will be able to read off not only how many ways there are of buying \(95\) plates, but also how many ways there are of buying every number of plates up to \(95\). (If we hadn’t cut the factors off as we did, we could also work out the answers for any number of plates higher than \(95\).) So by doing a bunch of multiplication once (and it’s easy to feed into a computer algebra system if you don’t want to do it by hand), we can simultaneously find out the answer to a lot of closely-related questions.

The other advantage is that the generating function approach can help us solve problems that we don’t see how to solve without it, such as finding an explicit formula for the \(n^{\text{th}}\) term of a recursively-defined sequence.

Here’s an example that involves working out the coefficient of a term in a generating function in two different ways.

Example \(\PageIndex{2}\)

Consider the generating function \(\left(\dfrac{1}{(1 − x)^4}\right) = (1 + x + x^2 + x^3 + . . .)^4\). As usual, we want to determine the coefficient of \(x^r\) in this product.

Solution

We must choose a power of \(x\) from each of the four factors, in such a way that the sum of the powers we choose must be \(n\). This is the same as choosing a total of \(r\) items, when the items come in four distinct types (recall, for example, Example 5.1.2). The types are represented by the factor the term is chosen from, and the exponent chosen from that factor is the number of items (\(x\)es) chosen of that type. So we know that the number of ways of doing this is \(\left( \binom{4}{r} \right)\)

We have another way of working this out. Our generating function is \((1 − x)^{−4}\), and the Generalised Binomial Theorem tells us that the coefficient of \((−x)^r\) in this is \(\binom{−4}{r}\), so the coefficient of \(x^r\) is

\((−1)^r (−1)^r \binom{r+3}{r} = \left( \binom{4}{r} \right) \)

We’ll use the above example to work out a counting question, but first we need an observation.

Proposition \(\PageIndex{1}\)

For any positive integer \(k\),

\[1 + x + x^2 + · · · + x^k = \dfrac{1-x^{k+1}}{1-x} \]

You can prove this by induction on \(k\) (this is one of the exercises below), or by multiplying through by \(1 − x\).

Example \(\PageIndex{3}\)

Trent is playing a dice game, using \(12\)-sided dice. How many ways are there for him to roll a total of \(24\) on his four dice?

Answer

Each die can roll any number between \(1\) and \(12\), and there are four dice, so the appropriate generating function is

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

Rolling an \(i\) on one of the dice corresponds to choosing \(x^i\) from the corresponding factor of this generating function. We are looking for the coefficient of \(x^{24}\), this will tell us the number of ways of rolling a total of \(24\).

It turns out that by manipulating the generating function, we can work this out a bit more easily than by multiplying this out. By taking a common factor of \(x\) out of each of the four factors, our generating function can be re-written as

\(x^4(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11})^4\)

and the coefficient of \(x^{24}\) in this, will be the same as the coefficient of \(x^{20}\) in

\((1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11})^4\)

Using Proposition 7.3.1, we see that this expression can be rewritten as

\( \left( \dfrac{1-x^{12}}{1-x} \right)^4 \)

Using the Binomial Theorem and substituting \(y = −x^{12}\), we see that

\( \begin{equation} \begin{split} (1 − x^{12})^4&= \binom{4}{0} (-x^{12})^0 + \binom{4}{1} (-x^{12})^1 + \binom{4}{2} (-x^{12})^2 + \binom{4}{3} (-x^{12})^3 + \binom{4}{4} (-x^{12})^4 \\ &= 1 − 4x^{12} + 12x^{24} − 4x^{36} + x^{48} \\ \end{split} \end{equation} \)

Most of these terms can be ignored, as they will not contribute to the coefficient of \(x^{20}\). Recall that the function we’re interested in is the product of this, with \((1 − x)^{−4}\), and there are only two ways of getting an \(x^{20}\) term from this product: by taking the constant term that we’ve just worked out, and multiplying it by the \(x^{20}\) term from \((1 − x)^{−4}\); or by taking the \(x^{12}\) term that we’ve just worked out, and multiplying it by the \(x^8\) term from \((1 − x)^{−4}\). In the previous example, we worked out that in \((1 − x)^{−4}\), the coefficient of \(x^{20}\) is \(\left( \binom{4}{20} \right)\), and the coefficient of \(x^8\) is \(\left( \binom{4}{8} \right)\).

Thus, the number of ways in which Trent can roll a total of \(24\) on his four dice is the coefficient of \(x^{24}\) in our generating function, which is

\(\left( \binom{4}{20} \right) - 4 \left( \binom{4}{8} \right) = 1771 - 660 = 1111 \)

Exercise \(\PageIndex{1}\)

1. Prove Proposition 7.3.1 by induction on \(k\).
2. Find the number of ways Trent can roll a total of \(16\) on his four dice.
3. If Trent’s four dice are \(10\)-sided dice instead of \(12\)-sided, how many ways can he roll a total of \(24\)?
4. If Trent rolls five regular (\(6\)-sided) dice, how many ways can he roll a total of \(11\)? What is the probability that he will roll a total of \(11\).