Question

What is the generating function for the sequence\(\left\{ {{c_k}} \right\}\), where \({c_k}\) is the number of ways to make change for \(k\) dollars using \(1 bills, \)2 bills, \(5 bills, and \)10 bills?

Short answer

The total generating function\( = \frac{1}{{(1 - x)\left( {1 - {x^2}} \right)\left( {1 - {x^5}} \right)\left( {1 - {x^{10}}} \right)}}\).

Step-by-step solution

Use Generating Function:

Generating function for the sequence \({a_0},{a_1}, \ldots ,{a_k}, \ldots \) of real numbers is the infinite series;

\(G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\)

Extended binomial theorem

\({(1 + x)^u} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}u\\k\end{array}} \right)} {x^k}\)

$\(1\) bills can form any dollar amount and thus the generating function for the $\(1\) bills can contain all powers of\(x\):

\(1 + x + {x^2} + \ldots \)

$\(2\) bills can only form a dollar amount that is a multiple of 2 and thus the generating function for the $\(2\)bills can contain all powers of \(x\) that are multiples of 2:

\(1 + {x^2} + {x^4} + \ldots \)

$\(5\) bills can only form a dollar amount that is a multiple of 5 and thus the generating function for the $\(5\) bills can contain all powers of \(x\) that are multiples of 5:

\(1 + {x^5} + {x^{10}} + \ldots \)

$\(10\) bills can only form a dollar amount that is a multiple of 10 and thus the generating function for the $\(10\)bills can contain all powers of \(x\) that are multiples of 10:

\(1 + {x^{10}} + {x^{20}} + \ldots \)

The total generating function is the product of the generating functions for each type of bill:

\(\begin{array}{c}\left( {1 + x + {x^2} + \ldots } \right)\left( {1 + {x^2} + {x^4} + \ldots } \right)\left( {1 + {x^5} + {x^{10}} + \ldots } \right)\left( {1 + {x^{10}} + {x^{20}} + \ldots } \right)\\ = \left( {\sum\limits_{k = 0}^{ + \infty } {{x^k}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{x^{2k}}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{x^{5k}}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{x^{10k}}} } \right)\\ = \left( {\sum\limits_{k = 0}^{ + \infty } {{x^k}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{{\left( {{x^2}} \right)}^k}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{{\left( {{x^5}} \right)}^k}} } \right)\left( {\sum\limits_{k = 0}^{ + \infty } {{{\left( {{x^{10}}} \right)}^k}} } \right)\\ = \frac{1}{{1 - x}} \cdot \frac{1}{{1 - {x^2}}} \cdot \frac{1}{{1 - {x^5}}} \cdot \frac{1}{{1 - {x^{10}}}}\\ = \frac{1}{{(1 - x)\left( {1 - {x^2}} \right)\left( {1 - {x^5}} \right)\left( {1 - {x^{10}}} \right)}}\end{array}\)

Thus, the total generating function\( = \frac{1}{{(1 - x)\left( {1 - {x^2}} \right)\left( {1 - {x^5}} \right)\left( {1 - {x^{10}}} \right)}}\).