Question

Use generating functions (and a computer algebra package, if available) to find the number of ways to make change for $1 using

a) dimes and quarters.

b) nickels, dimes, and quarters.

c) pennies, dimes, and quarters.

d) pennies, nickels, dimes, and quarters.

Short answer

The answer for each sub-part is given below:

(a) 3

(b) 29

(c) 26

(d) 242

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}}$

Dimes (10-cent) can form any cent 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$

Quarters (25-cent) can form any cent amount that is a multiple of 25 and thus the generating function for the quarters can contain all powers of x that are multiples of 25:

$1+x^{25}+x^{50}+\dots$width="113">1+x25+x50+…

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

$$\begin{gathered} \left(1+x^{10}+x^{20}+\dots \right)\left(1+x^{25}+x^{50}+\dots \right)=\left(\sum _{k=0}^{+\infty }{x}^{10k}\right)\left(\sum _{k=0}^{+\infty }{x}^{25k}\right) \\ =\left(\sum _{k=0}^{+\infty }{\left(x^{10}\right)}^k\right)\left(\sum _{k=0}^{+\infty }{\left(x^{25}\right)}^k\right) \\ =\frac{1}{1-x^{10}}·\frac{1}{1-x^{25}} \\ =\frac{1}{\left(1-x^{10}\right)\left(1-x^{25}\right)} \end{gathered}$$

Use Extended binomial theorem:

$$\begin{gathered} \frac{1}{\left(1-x^{10}\right)\left(1-x^{25}\right)}={\left(1+\left(-x^{10}\right)\right)}^{-1}·{\left(1+\left(-x^{25}\right)\right)}^{-1} \\ =\sum _{p=0}^{+\infty }\left(\begin{array}{c}-1\\ p\\ \end{array}\right){\left(-x^{10}\right)}^p·\sum _{m=0}^{+\infty }\left(\begin{array}{c}-1\\ m\\ \end{array}\right){\left(-x^{25}\right)}^m \\ =\sum _{p=0}^{+\infty }\left(\begin{array}{c}-1\\ p\\ \end{array}\right){(-1)}^p{x}^{10p}·\sum _{m=0}^{+\infty }\left(\begin{array}{c}-1\\ m\\ \end{array}\right){(-1)}^m{x}^{25m} \\ =\sum _{p=0}^{+\infty }{b}_p{x}^{10p}·\sum _{m=0}^{+\infty }{c}_m{x}^{25m} \end{gathered}$$

Let $b_p=\left(\begin{array}{c}-1\\ p\\ \end{array}\right){(-1)}^p$and $c_m=\left(\begin{array}{c}-1\\ m\\ \end{array}\right){(-1)}^m$

The coefficient of $x^{100}$(100 cents or 1 dollar), which is obtained if $10p+25m=100.$

$$\begin{gathered} p=10,m=0 \\ p=5,m=2 \\ p=0,m=4 \end{gathered}$$

The coefficient of $x^{100}$is the sum of the coefficients for each possible combination of m and k:

$$\begin{gathered} a_{100}=b_{10}{c}_0+b_5{c}_2+b_0{c}_4 \\ =\left(\begin{array}{c}-1\\ 10\\ \end{array}\right){(-1)}^{10}\left(\begin{array}{c}-1\\ 0\\ \end{array}\right){(-1)}^0+\left(\begin{array}{c}-1\\ 5\\ \end{array}\right){(-1)}^5\left(\begin{array}{c}-1\\ 2\\ \end{array}\right){(-1)}^2+\left(\begin{array}{c}-1\\ 0\\ \end{array}\right){(-1)}^0\left(\begin{array}{c}-1\\ 4\\ \end{array}\right){(-1)}^4 \\ =1+1+1 \\ =3 \end{gathered}$$

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

Nickels (5-cent) can form any cent amount that is a multiple of 5.

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

Dimes (10-cent) can form any cent 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$

Quarters (25-cent) can form any cent amount that is a multiple of 25 and thus the generating function for the quarters can contain all powers of x that are multiples of 25:

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

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

$\left(1+x^5+x^{10}+\dots \right)\left(1+x^{10}+x^{20}+\dots \right)\left(1+x^{25}+x^{50}+\dots \right)$

We are interested in the coefficient of $x^{100}$(100 cents or 1 dollar), thus we only require the sums up to the terms$x^{100}$. Expand the sum,

$$\begin{gathered} \left(1+x^5+x^{10}+\dots +x^{100}\right)\left(1+x^{10}+x^{20}+\dots +x^{100}\right)\left(1+x^{25}+x^{50}+x^{75}+x^{100}\right) \\ =\left(\sum _{k=0}^{20}{x}^{5k}\right)\left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^4{x}^{25k}\right) \\ =1+x^5+2x^{10}+2x^{15}+3x^{20}+4x^{25}+6x^{35}+7x^{40}+8x^{45}+10x^{50} \\ +11x^{55}+13x^{60}+14x^{65}+16x^{70}+18x^{75}+20x^{80}+22x^{85}+24x^{90} \\ +26x^{95}+29x^{100}+\dots \end{gathered}$$

Thus, the coefficient of $x^{100}$is 29.

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

Pennies (1-cent) can form any cent amount that is a multiple of 1 and thus;

$1+x^1+x^2+\dots$

Dimes (10-cent) can form any cent 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$

Quarters (25-cent) can form any cent amount that is a multiple of 25 and thus the generating function for the quarters can contain all powers of x that are multiples of 25:

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

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

$\left(1+x^1+x^2+\dots \right)\left(1+x^{10}+x^{20}+\dots \right)\left(1+x^{25}+x^{50}+\dots \right)$

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

$$\begin{gathered} \left(1+x^1+x^2+\dots +x^{100}\right)\left(1+x^{10}+x^{20}+\dots +x^{100}\right)\left(1+x^{25}+x^{50}+x^{75}+x^{100}\right) \\ =\left(\sum _{k=0}^{100}{x}^k\right)\left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^4{x}^{25k}\right) \\ =1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+\dots . \\ +26x^{97}+26x^8+26x^{99}+26x^{100}+28x^{101}+28x^{102}+\dots . \end{gathered}$$

Thus, the coefficient of $x^{100}$is 26.

The generating function for the nickels can contain all powers of $x$ that are multiples of 1:

Pennies (1 -cent) can form any cent amount that is a multiple of 1.

$1+x^1+x^2+\dots$

Nickels (5 -cent) can form any cent amount that is a multiple of 5 and thus the generating function for the nickels can contain all powers of x that are multiples of 10:

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

Dimes (10-cent) can form any cent 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$

Quarters (25-cent) can form any cent amount that is a multiple of 25 and thus the generating function for the quarters can contain all powers of x that are multiples of 25:

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

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

$\left(1+x^1+x^2+\dots \right)\left(1+x^5+x^{10}+\dots \right)\left(1+x^{10}+x^{20}+\dots \right)\left(1+x^{25}+x^{50}+\dots \right)$

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

$$\begin{gathered} \left(1+x^1+x^2+\dots +x^{100}\right)\left(1+x^5+x^{10}+\dots +x^{100}\right)\left(1+x^{10}+x^{20}+\dots +x^{100}\right)\left(1+x^{25}+x^{50}+x^{75}+x^{100}\right) \\ =\left(\sum _{k=0}^{100}{x}^k\right)\left(\sum _{k=0}^{20}{x}^{5k}\right)\left(\sum _{k=0}^{10}{x}^{10k}\right)\left(\sum _{k=0}^4{x}^{25k}\right) \\ =1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+\dots \\ +213x^{97}+213x^8+213x^{99}+242x^{100}+241x^{101}+241x^{102}+\dots \end{gathered}$$

Thus, the coefficient of $x^{100}$ is 242.