Question

Use generating functions to find the number of ways to make change for \(100 using

a) \)10, \(20, and \)50 bills.

b) \(5, \)10, \(20, and \)50 bills.

c) \(5, \)10, \(20, and \)50 bills if at least one bill of each denomination is used.

d) \(5, \)10, and $20 bills if at least one and no more than four of each denomination is used.

Short answer

The answer to each sub-part is given below:

(a) 10

(b) 49

(c) 2

(d) 4

Step-by-step solution

Use Generating Function:

Generating function for the sequence${\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{k}}\mathbf{,}\mathbf{\dots }$of real numbers is the infinite series;

$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathit{x}\mathbf{+}{\mathit{a}}_{\mathbf{2}}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}\mathbf{+}\mathbf{\dots }\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}$

Extended binomial theorem:

${\mathbf{(}\mathbf{1}\mathbf{+}\mathbf{x}\mathbf{)}}^{\mathbf{u}}\mathbf{=}\mathbf{\sum }\mathbf{}\mathbf{}_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\mathbf{\left(}\begin{array}{c}\mathbf{u}\\ \mathbf{k}\end{array}\mathbf{\right)}{\mathit{x}}^{\mathbf{k}}$

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

$1+x^{10}+x^{20}+\dots$

$\$20$can form any dollar amount that is a multiple of 20 and thus the generating function for the dimes can contain all powers of x that are multiples of 20:

$1+x^{20}+x^{40}+\dots$

$\$50$can form any dollar amount that is a multiple of 50 and thus the generating function for the dimes can contain all powers of x that are multiples of $\$50:$

$1+x^{50}+x^{100}+\dots$

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

The coefficient of $x^{100}$(100 cents or 1 dollar), thus we only require the sums up to the terms $x^{100}$(in the non-finite sums). Expand the sum:

$$\begin{gathered} \left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^5{x}^{20k}\right)\left(\sum _{k=0}^2{x}^{50k}\right) \\ =1+x^{10}+2x^{20}+2x^{30}+3x^{40}+5x^{50}+5x^{60}+6x^{70}+7x^{80}+8x^{90}+10x^{100} \\ +10x^{110}+11x^{120}+11x^{130}+12x^{140}+12x^{150}+12x^{160}+11x^{170}+11x^{180}+10x^{190} \\ +10x^{200}+8x^{210}+7x^{220}+6x^{230}+5x^{240}+4x^{250}+3x^{260}+2x^{270}+2x^{280}+x^{290}+x^{300} \end{gathered}$$

Thus, the coefficient of $x^{100}$is$a_{100}=10$.

The generating function for the dimes can contain all powers of x that are multiples of 5:

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

$1+x^5+x^{10}+\dots$

$10 can form any dollar amount that is a multiple of 10 and thus the generating function for the dimes can contain all powers of x that are multiples of 10:

$1+x^{10}+x^{20}+\dots$

$\$20$can form any dollar amount that is a multiple of 20 and thus the generating function for the dimes can contain all powers of x that are multiples of 20:

$1+x^{20}+x^{40}+\dots$

$50 can form any dollar amount that is a multiple of 50 and thus the generating function for the dimes can contain all powers of x that are multiples of 50.

$1+x^{50}+x^{100}+\dots$

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

$$\begin{gathered} \left(1+x^5+x^{10}+\dots \right)\left(1+x^{10}+x^{20}+\dots \right)\left(1+x^{20}+x^{40}+\dots \right)\left(1+x^{50}+x^{100}+\dots \right) \\ =\left(\sum _{k=0}^{+\infty }{x}^{5k}\right)\left(\sum _{k=0}^{+\infty }{x}^{10k}\right)\left(\sum _{k=0}^{+\infty }{x}^{20k}\right)\left(\sum _{k=0}^{+\infty }{x}^{50k}\right) \end{gathered}$$

We are interested in the coefficient of $x^{100}$(100 dollars), thus we only require the sums up to the terms $x^{100}$. Use technology to expand the sum.

$$\begin{gathered} \left(\sum _{k=0}^{20}{x}^{5k}\right)\left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^5{x}^{20k}\right)\left(\sum _{k=0}^2{x}^{50k}\right)=1+x^5+2x^{10}+2x^{15}+4x^{20}+4x^{25}+\dots \\ +39x^{95}+49x^{100}+48x^{105}+58x^{110}+\dots \end{gathered}$$

Thus, the coefficient of $x^{100}$is$a_{100}=49$.

The generating function for the dimes can contain all powers of $x$ that are multiples of 5.

$5 can form any dollar amount that is a multiple of 5.

At least one bill is used, thus the power cannot be 0.

$x^5+x^{10}+x^{15}+\dots$

$10 can form any dollar amount that is a multiple of 10 and thus the generating function for the dimes can contain all powers of x that are multiples of 10.

At least one bill is used, thus the power cannot be 0.

$x^{10}+x^{20}+x^{30}+\dots$

$20 can form any dollar amount that is a multiple of 20 and thus the generating function for the dimes can contain all powers of x that are multiples of 20.

At least one bill is used, thus the power cannot be 0.

$x^{20}+x^{40}+x^{60}+\dots$

$50 can form any dollar amount that is a multiple of 50 and thus the generating function for the dimes can contain all powers of x that are multiples of 50.

At least one bill is used, thus the power cannot be 0.

$x^{50}+x^{100}+x^{150}+\dots$

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

$$\begin{gathered} \left(x^5+x^{10}+x^{15}+\dots \right)\left(x^{10}+x^{20}+x^{30}+\dots \right)\left(x^{20}+x^{40}+x^{60}+\dots \right)\left(x^{50}+x^{100}+x^{150}+\dots \right) \\ =\left(\sum _{k=1}^{+\infty }{x}^{5k}\right)\left(\sum _{k=1}^{+\infty }{x}^{10k}\right)\left(\sum _{k=1}^{+\infty }{x}^{20k}\right)\left(\sum _{k=1}^{+\infty }{x}^{50k}\right) \\ =x^5{x}^{10}{x}^{20}{x}^{50}\left(\sum _{k=0}^{+\infty }{x}^{5k}\right)\left(\sum _{k=0}^{+\infty }{x}^{10k}\right)\left(\sum _{k=0}^{+\infty }{x}^{20k}\right)\left(\sum _{k=0}^{+\infty }{x}^{50k}\right) \\ =x^{85}\left(\sum _{k=0}^{+\infty }{x}^{5k}\right)\left(\sum _{k=0}^{+\infty }{x}^{10k}\right)\left(\sum _{k=0}^{+\infty }{x}^{20k}\right)\left(\sum _{k=0}^{+\infty }{x}^{50k}\right) \end{gathered}$$

The coefficient of $x^{100}$(100 dollars), thus we only require the sums up to the terms$x^{100}$. Expand the sum:

$x^{85}\left(\sum _{k=0}^{20}{x}^{5k}\right)\left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^5{x}^{20k}\right)\left(\sum _{k=1}^2{x}^{50k}\right)=x^{85}+x^{90}+2x^{95}+2x^{100}+4x^{105}+4x^{110}+\dots$

Thus, the coefficient of $x^{100}$is$a_{100}=2$.

The generating function for the dimes can contain all powers of x that are multiples of 5.

$5 can form any dollar amount that is a multiple of 5. At least one bill is used, thus the power cannot be 0.

At most 4 bills are used, thus the powers cannot be more than$4·5=20$.$x^5+x^{10}+x^{15}+x^{20}$

$10 can form any dollar amount that is a multiple of 10 and thus the generating function for the dimes can contain all powers of x that are multiples of 10.

At least one bill is used, thus the power cannot be 0. At most 4 bills are used, thus the powers cannot be more than$4·20=80$.

$x^{10}+x^{20}+x^{30}+x^{40}$

$20 can form any dollar amount that is a multiple of 20 and thus the generating function for the dimes can contain all powers of x that are multiples of 20.

At least one bill is used, thus the power cannot be 0. At most 4 bills are used, thus the powers cannot be more than$4·20=80$.

$x^{20}+x^{40}+x^{60}+x^{80}$

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

$$\begin{gathered} \left(x^5+x^{10}+x^{15}+x^{20}\right)\left(x^{10}+x^{20}+x^{30}+x^{40}\right)\left(x^{20}+x^{40}+x^{60}+x^{80}\right) \\ =\left(\sum _{k=1}^4{x}^{5k}\right)\left(\sum _{k=1}^4{x}^{10k}\right)\left(\sum _{k=1}^4{x}^{20k}\right) \\ =x^5{x}^{10}{x}^{20}\left(\sum _{k=0}^3{x}^{5k}\right)\left(\sum _{k=0}^3{x}^{10k}\right)\left(\sum _{k=0}^3{x}^{20k}\right) \end{gathered}$$

Expand the sum:

$$\begin{gathered} x^{35}\left(\sum _{k=0}^3{x}^{5k}\right)\left(\sum _{k=0}^3{x}^{10k}\right)\left(\sum _{k=0}^3{x}^{20k}\right)=x^{35}+x^{40}+2x^{45}+2x^{50}+3x^{55}+3x^{60}+4x^{65} \\ +4x^{70}+4x^{75}+4x^{80}+4x^{85}+4x^{90}+4x^{95}+4x^{100} \\ +4x^{105}+4x^{110}+3x^{115}+3x^{120}+2x^{125}+2x^{130}+x^{135}+x^{140} \end{gathered}$$

Thus, the coefficient of $x^{100}$is$a_{100}=4$.