Enumerative Combinatorics: Activities and Exercises

1. OGFs for Pocket Change.

1. For \(n \geq 0\text{,}\) let \(a_n\) be the number of ways to pay \(n\) cents using nickels. Write out the first 6 nonzero terms of the generating function

   \begin{equation*} A(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots \end{equation*}

   Solution.

   \begin{equation*} 1 + x^5 + x^{10} + x^{15} + x^{20} + x^{25} + \cdots \end{equation*}

2. For \(n \geq 0\text{,}\) let \(b_n\) be the number of ways to pay \(n\) cents using dimes. Write out the first 6 nonzero terms of the generating function

   \begin{equation*} B(x) = b_0 + b_1 x + b_2 x^2 + b_3x^3 + \cdots \end{equation*}

   Solution.

   \begin{equation*} 1 + x^{10} + x^{20} + x^{30} + x^{40} + x^{50} + \cdots \end{equation*}

3. For \(n \geq 0\text{,}\) let \(c_n\) be the number of ways to pay \(n\) cents using quarters. Write out the first 6 nonzero terms of the generating function

   \begin{equation*} C(x) = c_0 + c_1 x + c_2 x^2 + c_3x^3 + \cdots \end{equation*}

   Solution.

   \begin{equation*} 1 + x^{25} + x^{50} + x^{75} + x^{100} + x^{125} + \cdots \end{equation*}

4. You should recognize \(A(x), B(x), C(x)\) as variants of a well known Taylor series. What are these functions? What restrictions must we place on \(x\text{?}\) Solution.

   \begin{equation*} \begin{array}{ccc} \displaystyle{A(x)= \frac{1}{1-x^5}} & \displaystyle{B(x)= \frac{1}{1-x^{10}}} & \displaystyle{A(x)= \frac{1}{1-x^{25}}} \end{array} \end{equation*}

   provided that \(x\) satisifies: \underline{\phantom{asdfasdfasdf}\(-1 < x < 1\)\phantom{asdfasdfasdf}}

5. Using the product and addition principles, we can show that the function \(D(x)= A(x)B(x)C(x)\) is the generating function for the number of ways to pay \(n\) cents using nickels, dimes, and/or quarters. Use your answer in question 4 to find the formula for \(D(x)\text{.}\) (The same restrictions on \(x\) apply here.) Solution.

   \begin{equation*} D(x) = \frac{1}{1-x^{5}} \cdot \frac{1}{1-x^{10}} \cdot \frac{1}{1-x^{25}} = \frac{1}{(1-x^{5})(1-x^{10})(1-x^{25})} \end{equation*}

6. The Taylor series for \(D(x)\) starts as

   \begin{equation*} D(x) = 1 + x^5 + 2x^{10} + 3 x^{20} + 4x^{25} + 5x^{30} + 6x^{35} + 7 x^{40} + 8x^{45} + \cdots \end{equation*}

   Verify this gives the right answer for \(n=35\) by listing the number of ways to pay \(35\) cents using nickels, dimes and/or quarters. Solution.

   Here are the six ways to pay \(35\) cents using these coins:

   \begin{equation*} \begin{array}{ccc} Q + D & Q + 2N & 3D + N \\ 2D + 3N & D+5N & 7N \end{array} \end{equation*}

2. Solving a Recurrence with OGFs.

Solve the recurrence relation

where \(h_0=1\) and \(h_1=2\text{.}\)

1. Let \(H(x)\) be the generating function for this series. Find a simple closed formula for \(H(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcll} h_n &=& 5 h_{n-1} - 6h_{n-2} & \mbox{for } n \geq 2 \\ h_n x^n &=& 5 h_{n-1} x^n - 6h_{n-2} x^n & \mbox{for } n \geq 2 \\ \displaystyle{\sum_{n=2}^{\infty} h_n x^n} &=& \displaystyle{ \sum_{n=2}^{\infty} 5 h_{n-1} x^n - \sum_{n=2}^{\infty} 6h_{n-2} x^n} & (\mbox{sum starts at } n=2) \\ \displaystyle{ \sum_{n=2}^{\infty} h_n x^n }&=& \displaystyle{ 5 x \sum_{n=2}^{\infty} 5 h_{n-1} x^{n-1} -6x^2 \sum_{n=2}^{\infty} h_{n-2} x^{n-2} }& (\mbox{powers match coefficient indices}) \\ \displaystyle{ \sum_{n=2}^{\infty} h_n x^n }&=& \displaystyle{ 5 x \sum_{i=1}^{\infty} 5 h_{i} x^{i} -6x^2 \sum_{j=0}^{\infty} h_{j} x^{j} }& (\mbox{re-index second two summations}) \\ H(x) - h_0 - h_1x &=& \displaystyle{ 5 x ( H(x) - h_0) -6x^2 H(x)} & (\mbox{replace summations with } H(x)) \\ H(x) - 5H(x) + 6x^2 H(x) &=& h_0 + h_1x -5 h_0 x & (\mbox{collect like terms}) \\ H(x) (1 - 5x +6x^2) &=& 1 -3 x & (h_0=1 \mbox{ and } h_1=2) \\ H(x)&=& \displaystyle{\frac{1 -3 x}{1 - 5x +6x^2 }} & (\mbox{bingo!}) \\ H(x)&=&\displaystyle{ \frac{1}{ 1 - 2x } } & (\mbox{simplify}) \\ \end{array} \end{equation*}

2. Use the Taylor series for the function in part (a) to find a simple closed formula for \(h_n\text{.}\) Solution.

   \begin{equation*} H(x) = \frac{1}{1-2x} = \sum_{n=0}^{\infty} (2x)^n = \sum_{n=0}^{\infty} 2^n x^n. \end{equation*}

   Therefore \(h_n=2^n\text{.}\)

3. Now solve the same recurrence where \(h_0=1\) and \(h_1=-2\text{.}\) You will need to use partial fractions. Solution.

   The first 7 lines are the same, so we have

   \begin{equation*} H(x)= \frac{h_0 + (h_1- 5h_0)x}{1 - 5x +6x^2 } = \frac{1 -7x}{ (1-2x)(1-3x)}. \end{equation*}

   We use partial fractions to solve

   \begin{equation*} \frac{1 -7x}{ (1-2x)(1-3x)} = \frac{a}{ 1-2x} + \frac{b}{ 1-3x}, \end{equation*}

   giving equations \(a+b = 1\) and \(-3a-2b=-7\text{.}\) Solving gives \(a=5\) and \(b=-4\text{,}\) so

   \begin{equation*} H(x) = \frac{5}{ 1-2x} - \frac{4}{ 1-3x}= 5 \sum_{n=0}^{\infty} (2x)^n -4 \sum_{n=0}^{\infty} (3x)^n \end{equation*}

   and therefore \(h_n = 5 \cdot 2^n - 4 \cdot 3^n.\)

3. Solving Another Recurrence.

Consider the recurrence relation \[ a_n = 4 a_{n-1} -1 \mbox{ for } n \geq 1 \] where \(a_0=3\)

1. Let \(A(x)\) be the OGF for this series. Find a simple closed formula for \(A(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} a_n &=& 4 a_{n-1} -1 \mbox{ for } n \geq 1 \\ a_n x^n &=& (4 a_{n-1} -1)x^n \mbox{ for } n \geq 1 \\ \sum_{n=1}^{\infty} a_n x^n &=& \sum_{n=1}^{\infty} 4a_{n-1} x^n - \sum_{n=1}^{\infty} x^n \\ \sum_{n=1}^{\infty} a_n x^n &=& 4x \sum_{n=1}^{\infty} a_{n-1} x^{n-1} - x \sum_{n=1}^{\infty} x^{n-1} \\ A(x) - a_0 &=& 4x A(x) - \frac{x}{1-x} \\ A(x) (1 - 4x) &=& a_0 - \frac{x}{1-x} \\ A(x) (1 - 4x) &=& 3 - \frac{x}{1-x} \\ A(x) (1 - 4x) &=& \frac{3-4x}{1-x} \\ A(x) &=& \frac{3-4x}{(1 - 4x)(1-x)} \\ \end{array} \end{equation*}

2. Use the Taylor series for the functions in part (a) to find a simple closed formula for \(a_n\text{.}\) Solution.

   We use partial fractions:

   \begin{equation*} \frac{3-4x}{(1 - 4x)(1-x)} = \frac{b}{1-4x} + \frac{c}{1-x} \end{equation*}

   which gives \(b+c =3\) and \(-b-4c=-4\text{.}\) Solving, we find that \(b=8/3\) and \(c=1/3\text{.}\) So

   \begin{equation*} A(x) = \frac{8}{3} \cdot \frac{1}{1-4x} + \frac{1}{3} \cdot \frac{1}{1-x} = \frac{8}{3} \sum_{n=0}^{\infty} 4^n x^n + \frac{1}{3} \sum_{n=0}^{\infty} x^n \end{equation*}

   and therefore

   \begin{equation*} a_n = \frac{8}{3} \cdot 4^n + \frac{1}{3} = \frac{2 \cdot 4^{n+1} + 1}{3}. \end{equation*}

4. Yet Another Recurrence Relation.

Solve the recurrence relation

where \(b_0=1\) and \(b_1=3\text{.}\)

1. Let \(B(x)\) be the generating function for this series. Find a simple closed formula for \(B(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} b_n &=& 3 b_{n-1} -2 b_{n-2} \mbox{ for } n \geq 2 \\ b_n x^n &=& (3 b_{n-1} -2 b_{n-2})x^n \mbox{ for } n \geq 2 \\ \sum_{n=2}^{\infty} b_n x^n &=& \sum_{n=2}^{\infty} 3 b_{n-1} x^n - \sum_{n=2}^{\infty} 2 b_{n-2} x^n \\ \sum_{n=2}^{\infty} b_n x^n &=& 3x \sum_{n=2}^{\infty} b_{n-1} x^{n-1} - 2x^2 \sum_{n=2}^{\infty} x^{n-2} \\ B(x) - b_0 - b_1 x &=& 3x ( B(x) - b_0) - 2x^2 B(x) \\ B(x) ( 1 -3x + 2x^2) &=& b_0 + b_1x - 3b_0 x \\ B(x) ( 1 -2x)(1-x) &=& 1 + 3x - 3 x \\ B(x) &=& \frac{1}{ (1-2x)(1-x)} \\ \end{array} \end{equation*}

2. Use the Taylor series for the functions in part (a) to find a simple closed formula for \(b_n\text{.}\) Solution.

   We use partial fractions:

   \begin{equation*} \frac{1}{(1 - 2x)(1-x)} = \frac{c}{1-2x} + \frac{d}{1-x} \end{equation*}

   which gives \(c+d =1\) and \(c+2d=0\text{.}\) Solving, we find that \(c=2\) and \(d=-1\text{.}\) So

   \begin{equation*} B(x) = \frac{2}{1-2x} - \frac{1}{1-x} = 2 \sum_{n=0}^{\infty} 2^n x^n - \sum_{n=0}^{\infty} x^n \end{equation*}

   and therefore

   \begin{equation*} b_n = 2 \cdot 2^n - 1 = 2^{n+1} -1. \end{equation*}

5. Solving a Recurrence with EGFs.

Solve the recurrence relation

where \(c_0=1\) and \(c_1=4\text{.}\)

1. Let \(C(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!}\) be the exponential generating function (EGF) for this series. Find a simple closed formula for \(C(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} c_n &=& 2 n c_{n-1} + 8 n (n-1) c_{n-2} \mbox{ for } n \geq 2 \\ c_n \frac{x^n}{n!} &=& (2 n c_{n-1} + 8 n (n-1) c_{n-2} )\frac{x^n}{n!}\mbox{ for } n \geq 2 \\ \sum_{n=2}^{\infty} c_n \frac{x^n}{n!} &=& \sum_{n=2}^{\infty} (2 n c_{n-1} + 8 n (n-1) c_{n-2} )\frac{x^n}{n!} \\ \sum_{n=2}^{\infty} c_n \frac{x^n}{n!} &=&2 \sum_{n=2}^{\infty} n c_{n-1} \frac{x^n}{n!} + 8 \sum_{n=2}^{\infty} n (n-1) c_{n-2} \frac{x^n}{n!} \\ \sum_{n=2}^{\infty} c_n \frac{x^n}{n!} &=&2x \sum_{n=2}^{\infty} c_{n-1} \frac{x^{n-1}}{(n-1)!} + 8x^2 \sum_{n=2}^{\infty} n (n-1) c_{n-2} \frac{x^{n-2}}{(n-2)!} \\ C(x) - c_0 - c_1 \frac{x}{1!} &=& 2x (C(x) - c_0) - 8x^2 C(x) \\ C(x) ( 1 -2x - 8x^2) &=& c_0 + c_1 x - 2c_0 x \\ C(x) ( 1 -4x)(1+2x) &=& 1 + 4 x - 2 x \\ C(x) &=& \frac{1 + 2 x }{ ( 1 -4x)(1+2x)} \\ C(x) &=& \frac{1}{ 1 -4x} \\ \end{array} \end{equation*}

2. Use the Taylor series for the functions in part (a) to find a simple closed formula for \(c_n\text{.}\) Remember that \(C(x)\) is an EGF, so you will have to multiply the \(n\)th term by \(\frac{n!}{n!}\) and rearrange to get the right answer. Solution.

   \begin{equation*} C(x) = \sum_{n=0}^{\infty} 4^n x^n = \sum_{n=0}^{\infty} (4^n n! ) \frac{x^n}{n!} \end{equation*}

   so \(c_n = 4^n n!\text{.}\)

6. Solving Another Recurrence with EGFs.

Consider the recurrence relation

where \(d_0=1\text{.}\)

1. Let \(D(x) = \sum_{n=0}^{\infty} d_n \frac{x^n}{n!}\) be the exponential generating function (EGF) for this series. Find a simple closed formula for \(D(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} d_n &=& n d_{n-1} + 1 \mbox{ for } n \geq 1 \\ d_n \frac{x^n}{n!} &=& ( n d_{n-1} + 1 )\frac{x^n}{n!}\mbox{ for } n \geq 2 \\ \sum_{n=1}^{\infty} d_n \frac{x^n}{n!} &=& \sum_{n=1}^{\infty} (n d_{n-1} + 1 )\frac{x^n}{n!} \\ \sum_{n=1}^{\infty} d_n \frac{x^n}{n!} &=& \sum_{n=1}^{\infty} n d_{n-1} \frac{x^n}{n!} + \sum_{n=1}^{\infty} \frac{x^n}{n!} \\ \sum_{n=1}^{\infty} d_n \frac{x^n}{n!} &=& x \sum_{n=1}^{\infty} d_{n-1} \frac{x^{n-1}}{(n-1)!} + \sum_{n=1}^{\infty} \frac{x^n}{n!} \\ D(x) -1 &=& x D(x) + e^x -1 \\ D(x) (1 - x) &=& e^x \\ D(x) &=& \frac{e^x}{1-x} \end{array} \end{equation*}

2. Can you figure out how to use your answer in part (a) to find a simple closed formula for \(d_n\text{?}\) You will need to think about what happens when you multiply two power series together. Solution.

   We have

   \begin{equation*} D(x) = \frac{e^x}{1-x} = \left( \sum_{n=0}^{\infty} \frac{x^n}{n!} \right) \left( \sum_{n=0}^{\infty} x^n \right). \end{equation*}

   If we multiply out, we find that the coefficient of \(x^n\) is

   \begin{equation*} \sum_{k=0}^n \frac{1}{k!} \end{equation*}

   and therefore

   \begin{equation*} D(x) = \sum_{n=0}^{\infty} \left( n! \sum_{k=0}^n \frac{1}{k!} \right) \frac{x^n}{n!}. \end{equation*}

   So our formula is

   \begin{equation*} d_n = n! \sum_{k=0}^n \frac{1}{k!} = \sum_{k=0}^n (n)_k. \end{equation*}