Mathacadabra
Home > Discussions > Combinatorics
Note: this page uses MathJax for formatting, so may take a few seconds to load.


Adventures with Generating Functions II

Note: This is the second article of a planned 5-part series. The first article: Adventures with Generating Functions I: An Infinite Sum.

Second Adventure: How Many Ways Are There to Make a Million Dollars?

There are \[ 88{,}265{,}881{,}340{,}710{,}786{,}348{,}934{,}950{,}201{,}250{,}975{,}072{,}332{,}541{,}120{,}001 \] ways to make one million dollars using any combination of pennies, nickels, dimes, quarters, half-dollars, one-dollar bills, five-dollar bills, ten-dollar bills, twenty-dollar bills, fifty-dollar bills, and hundred-dollar bills.

Let's start by looking at a simpler problem, the number of ways to make one dollar using any combination of coins. We have an unlimited supply of currency in each denomination and the order of the units used is unimportant. For example, one way to make a dollar is $50+25+10+10+1+1+1+1+1$, and this is considered the same as $1+1+1+1+1+10+10+25+50$.

George Pólya showed how to solve this problem in his book How to Solve It. Let $p$, $n$, $d$, $q$, $h$, and $w$ stand for the number of pennies, nickels, dimes, quarters, half-dollars, and whole dollars, respectively. For each denomination $x$ and positive integer $k$, let $x_k$ be the number of ways to make the amount $k$ using no denomination higher than $x$. The following recurrence relations hold: \begin{align*} p_k&=1\\ n_k&=p_{k}+n_{k-5}\\ d_k&=n_{k}+d_{k-10}\\ q_k&=d_{k}+q_{k-25}\\ h_k&=q_{k}+h_{k-50}\\ w_k&=h_{k}+w_{k-100}, \end{align*} where we set $x_k=0$ for $k<0$. It's easy to complete the following table by hand and find that the number of ways to make one dollar is $w_{100}=293$ (this includes using a dollar itself). \begin{array}{c|cccccc} k & p_k & n_k & d_k & q_k & h_k & w_k\\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 5 & 1 & 2 & 2 & 2 & 2 & 2\\ 10 & 1 & 3 & 4 & 4 & 4 & 4\\ 15 & 1 & 4 & 6 & 6 & 6 & 6\\ 20 & 1 & 5 & 9 & 9 & 9 & 9\\ 25 & 1 & 6 & 12 & 13 & 13 & 13\\ 30 & 1 & 7 & 16 & 18 & 18 & 18\\ 35 & 1 & 8 & 20 & 24 & 24 & 24\\ 40 & 1 & 9 & 25 & 31 & 31 & 31\\ 45 & 1 & 10 & 30 & 39 & 39 & 39\\ 50 & 1 & 11 & 36 & 49 & 50 & 50\\ 55 & 1 & 12 & 42 & 60 & 62 & 62\\ 60 & 1 & 13 & 49 & 73 & 77 & 77\\ 65 & 1 & 14 & 56 & 87 & 93 & 93\\ 70 & 1 & 15 & 64 & 103 & 112 & 112\\ 75 & 1 & 16 & 72 & 121 & 134 & 134\\ 80 & 1 & 17 & 81 & 141 & 159 & 159\\ 85 & 1 & 18 & 90 & 163 & 187 & 187\\ 90 & 1 & 19 & 100 & 187 & 218 & 218\\ 95 & 1 & 20 & 110 & 213 & 252 & 252\\ 100 & 1 & 21 & 121 & 242 & 292 & 293 \end{array}

We can also solve the problem using generating functions.

The generating function of the sequence $\{a_k\}$, where $a_k$ is the number of ways to make the amount $k$ using pennies, nickels, dimes, quarters, half-dollars, and whole dollars, is \[ \sum_{k=0}^{\infty}a_k x^k = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+\cdots, \] where the coefficient of $x^k$ in this ``infinite polynomial'' is $a_k$. The generating function has a representation as a rational function, namely, \[ \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100})}. \] To see how this works, consider this function as a product of geometric series: \[ (1+x+x^2+x^3+\cdots)(1+x^5+x^{2 \cdot 5}+ x^{3 \cdot 5}+\cdots)\ldots(1+x^{100}+x^{2 \cdot 100}+ x^{3 \cdot 100}+\cdots). \] Taking a single monomial from each sum in parentheses corresponds to one way of making an amount equal to the sum of the exponents in the chosen monomials. For example, choosing the sixth term in the first group, the third term in the second group, the second term in the third group, and the first term in each of the other groups results in the monomial $x^{5 \cdot 1 + 2 \cdot 5 + 1 \cdot 10}$, which corresponds to one way of making 25 cents, namely, five pennies, two nickels, and one dime.

A computer algebra system tells us that the coefficient of $x^{100}$ in our rational generating function is 293. Actually (as shown in Ivan Niven's book The Mathematics of Choice), we only need to compute the coefficient of $x^{100}$ in the polynomial product \begin{align*} &(1+x+x^2+\cdots+x^{100})(1+x^5+x^{10}+\cdots+x^{100})(1+x^{10}+x^{20}+\cdots+x^{100})\\ \cdot&(1+x^{25}+x^{50}+x^{75}+x^{100})(1+x^{50}+x^{100})(1+x^{100}), \end{align*} and we can do this by hand.

We can get more information from the generating function. The denominator of the rational function is a polynomial of degree 191; therefore $\{w_k\}$ satisfies a linear recurrence relation with constant coefficients of order 191. Also, we can modify the generating function to show all the relevant combinations: \[ \frac{1}{(1-px)(1-nx^5)(1-dx^{10})(1-qx^{25})(1-hx^{50})(1-wx^{100})}. \] The coefficient of, say, $x^{100}$, includes terms $p^{100}$, $p^{95}n$, and $p^{90}n^2$, etc., indicating that $100$ can be made with $100$ pennies, $95$ pennies and a nickel, $90$ pennies and two nickels, etc.

Similarly, we can find the number of ways to make 100 dollars (10000 cents) by using the generating function \[ \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100}) (1-x^{500})(1-x^{1000})(1-x^{2000})(1-x^{5000})(1-x^{10000})}. \] The coefficient of $x^{10000}$ in the expansion is $1{,}424{,}039{,}612{,}939$.

Now we will find the number of ways to make a million dollars with the denominations mentioned at the beginning of this discussion. We use generating functions in a modified way as indicated in the book Concrete Mathematics, by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.

The number of pennies used to make a whole dollar amount must be a multiple of $5$, so let's think of $5$ cents as the smallest unit of currency. Let $c_k$ be the number of ways to make $5k$ cents using the given denominations. The generating function for $\{c_k\}$ is \[ \frac{1}{(1-x)(1-x)(1-x^{2})(1-x^{5})(1-x^{10})(1-x^{20}) (1-x^{100})(1-x^{200})(1-x^{400})(1-x^{1000})(1-x^{2000})}. \]

Since 1 million is $20{,}000{,}000$ of our basic units, we must find $c_{20,000,000}$. To do this, we express each factor in the denominator as $(1-x^{2000})$ with a compensating factor (a geometric series) in the numerator. The new numerator is \begin{align*} &(1+x+\cdots+x^{1999})^2(1 + x^2 + x^4 + \cdots + x^{1998})(1+x^5+\cdots+x^{1995}) (1+x^{10}+\cdots+x^{1990})\\ & \cdot (1+x^{20}+\cdots+x^{1980})(1+x^{100}+\cdots+x^{1900})(1+x^{200}+\cdots+x^{1800})(1+x^{400}+\cdots+x^{1600})(1+x^{1000}), \end{align*} and a computer algebra system can multiply this quickly. The new denominator is $(1-x^{2000})^{11}$, and we can expand its reciprocal as a binomial series: \[ (1-x^{2000})^{-11} = \sum _{j=0}^{\infty} \binom{j+10}{10}x^{2000j}. \]

We complete our calculation by multiplying this binomial series with contributing terms in the numerator to obtain the coefficient of $x^{20,000,000}$. In the numerator, the only powers of $x$ that matter are multiples of $2000$. If $\alpha_i$ is the coefficient of $x^i$, then the relevant coefficients are \begin{align*} \alpha_0 &= 1\\ \alpha_{2000} &= 1424039612928 \\ \alpha_{4000} &= 212561825179035\\ \alpha_{6000} &= 3224717280609587 \\ \alpha_{8000} &= 11601166434205649\\ \alpha_{10000} &= 12519790995056639\\ \alpha_{12000} &= 4102067385934937\\ \alpha_{14000} &= 334900882733305 \\ \alpha_{16000} &=3371148659578.\\ \alpha_{18000} &= 8008341. \end{align*} Hence \begin{align*} c_{20,000,000}&=\sum_{j=0}^9 \alpha_{2000j} \binom{10000+10-j}{10}\\ &=88265881340710786348934950201250975072332541120001\\ &\approx 9 \times 10^{49}. \end{align*}

The next article in the series: Adventures with Generating Functions III: Integer Triangles.

References
  1. R. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science: Second Edition, Addison-Wesley Professional, 1994.
  2. I. Niven , Mathematics of Choice: How to Count Without Counting, Mathematical Association of America, 1975.
  3. G. Pólya , How to Solve It: A New Aspect of Mathematical Method, Princeton University Press , 2004.