Question

Explain how generating functions can be used to find the number of ways in which postage of $r$ cents can be pasted on an envelope using 3-cent, 4-cent, and 20-cent stamps.

a) Assume that the order the stamps are pasted on does not matter.

b) Assume that the stamps are pasted in a row and the order in which they are pasted on matters.

c) Use your answer to part (a) to determine the number of ways 46 cents of postage can be pasted on an envelope using 3 -cent, 4-cent, and 20-cent stamps when the order the stamps are pasted on does not matter. (Use of a computer algebra program is advised.)

d) Use your answer to part (b) to determine the number of ways 46 cents of postage can be pasted in a row on an envelope using 3-cent, 4 -cent, and 20 -cent stamps when the order in which the stamps are pasted on matters.

Short answer

(a)The total generating function is $\frac{1}{\left(1-x^3\right)\left(1-x^4\right)\left(1-x^{20}\right)}$.

(b) The total generating function is$\frac{1}{1-x^3-x^4-x^{20}}$.

(c) There are 7 possible ways.

(d) The coefficient of $x^{46}$ is 3224.

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{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\left(\begin{array}{c}u\\ k\end{array}\right){\mathit{x}}^{\mathbf{k}}$

3 -cent can form any cent amount that is a multiple of 3 and thus the generating function for the 3 -cent stamps can contain all powers of $x$that are multiples of 3:

$1+x^3+x^6+\dots$

4-cent can form any cent amount that is a multiple of 4 and thus the generating function for the 4-cent stamps can contain all powers of $x$that are multiples of 4:

$1+x^4+x^8+\dots$

20-cent can form any cent amount that is a multiple of 20 and thus the generating function for the 20-cent stamps can contain all powers of$x$that are multiples of 20: $1+x^{20}+x^{40}+\dots$

The generating function is the product of the series for each variable:

$$\begin{gathered} \left(1+x^3+x^6+\dots \right)\left(1+x^4+x^8+\dots \right)\left(1+x^{20}+x^{40}+\dots \right) \\ =\left(\sum _{k=0}^{+\infty }{x}^{3k}\right)\left(\sum _{k=0}^{+\infty }{x}^{4k}\right)\left(\sum _{k=0}^{+\infty }{x}^{20k}\right) \\ =\left(\sum _{k=0}^{+\infty }{\left(x^3\right)}^k\right)\left(\sum _{k=0}^{+\infty }{\left(x^4\right)}^k\right)\left(\sum _{k=0}^{+\infty }{\left(x^{20}\right)}^k\right) \\ =\frac{1}{1-x^3}·\frac{1}{1-x^4}·\frac{1}{1-x^{20}} \\ =\frac{1}{\left(1-x^3\right)\left(1-x^4\right)\left(1-x^{20}\right)} \end{gathered}$$

b).

The expression is given by:

$x^3+x^4+x^{20}$

If we then make $\mathrm{n}$draws of stamps, then the generating function of the $\mathrm{n}$draws is the product of the generating functions for each draw:

${\left(x^3+x^4+x^{20}\right)}^n$

The total generating function is then the sum over all possible draws:

c).

Use Extended binomial theorem:

$$\begin{gathered} \frac{1}{\left(1-x^3\right)\left(1-x^4\right)\left(1-x^{20}\right)}={\left(1+\left(-x^3\right)\right)}^{-1}·{\left(1+\left(-x^4\right)\right)}^{-1}·{\left(1+\left(-x^{20}\right)\right)}^{-1} \\ =\sum _{p=0}^{+\infty }\left(\begin{array}{c}-1\\ p\end{array}\right){\left(-x^3\right)}^p.\sum _{m=0}^{+\infty }\left(\begin{array}{c}-1\\ m\end{array}\right){\left(-x^4\right)}^m.\sum _{k=0}^{+\infty }{\left(-x^{20}\right)}^k \\ =\sum _{p=0}^{+\infty }\left(\begin{array}{c}-1\\ p\end{array}\right){\left(-1\right)}^p{x}^{3p}.\sum _{m=0}^{+\infty }\left(\begin{array}{c}-1\\ m\end{array}\right){\left(-1\right)}^m{x}^{4m}.\sum _{k=0}^{+\infty }\left(\begin{array}{c}-1\\ k\end{array}\right){\left(-1\right)}^k{x}^{20k} \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$ and $d_k=\left(\begin{array}{c}-1\\ k\end{array}\right){(-1)}^k$

$=\sum _{p=0}^{+\infty }{b}_p{x}^{3p}·\sum _{m=0}^{+\infty }{c}_m{x}^{4m}·\sum _{k=0}^{+\infty }{d}_k{x}^{20k}$

The coefficient of $x^{46}(46$a cent), which is obtained if $3p+4m+20k=46$

$$\begin{gathered} k=2,m=0,p=2 \\ k=1,m=2,p=6 \\ k=1,m=5,p=2 \\ k=0,m=10,p=2 \\ k=0,m=7,p=6 \\ k=0,m=4,p=10 \\ k=0,m=1,p=14 \end{gathered}$$

The coefficient of x46 is then the sum of the coefficients for each possible combination of m and k:

$a_{46}=b_2{c}_0{d}_2+b_1{c}_2{d}_6+b_1{c}_5{d}_2+b_0{c}_{10}{d}_2+b_0{c}_7{d}_6+b_0{c}_4{d}_{10}+b_0{c}_1{d}_{14}$

$=\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\\ 2\end{array}\right){(-1)}^2+$$\left(\begin{array}{c}-1\\ 1\end{array}\right){(-1)}^1$$\left(\begin{array}{c}-1\\ 2\end{array}\right){(-1)}^2$$\left(\begin{array}{c}-1\\ 6\end{array}\right){(-1)}^6$

$+\left(\begin{array}{c}-1\\ 1\end{array}\right){(-1)}^1$$\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\\ 10\end{array}\right){(-1)}^{10}$$\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\\ 7\end{array}\right){(-1)}^7$$\left(\begin{array}{c}-1\\ 6\end{array}\right){(-1)}^6+\left(\begin{array}{c}-1\\ 0\end{array}\right){(-1)}^0$$\left(\begin{array}{c}-1\\ 4\end{array}\right){(-1)}^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\\ 1\end{array}\right){(-1)}^1$$\left(\begin{array}{c}-1\\ 14\end{array}\right){(-1)}^{14}$

$$\begin{gathered} =1+1+1+1+1+1+1 \\ =7 \end{gathered}$$

d).

Calculate all possible combinations that result in a term containing x46 in the first 15 terms of the sum.

Since $\frac{46}{3}\approx 15.333$

Expand the sum:

$\sum _{n=0}^{15}{\left(x^3+x^4+x^{20}\right)}^k=x^3+x^4+x^6+2x^7+x^8+x^9+3x^{10}+3x^{11}+2x^{12}+4x^{13}+6x^{14}$

$$\begin{gathered} +5x^{15}+6x^{16}+10x^{17}+11x^{18}+11x^{19}+17x^{20}+21x^{21}+22x^{22}+29x^{23} \\ +39x^{24}+43x^{25}+52x^{26}+70x^{27}+83x^{28}+96x^{29}+125x^{30}+156x^{31} \\ +181x^{32}+225x^{33}+287x^{34}+342x^{35}+412x^{36}+552x^{37}+640x^{38} \\ +765x^{39}+951x^{40}+1183x^{41}+1427x^{42}+1745x^{43}+2173x^{44} \\ +2653x^{45}+3224x^{46}+\dots \end{gathered}$$

Thus, the coefficient of $x^{46}$ is 3224.