Enumerative Combinatorics: Activities and Exercises

1. Generating Functions for Integer Partitions.

We have seen that the generating function for integer partitions is

Here the symbol \(\prod\) means "take the product," just like \(\sum\) means "take the sum."

1. Fixing a particular integer \(n\text{,}\) we realized that we can find all of the integer partitions of \(n\) by using the generating function

   \begin{equation*} Q_n(x) = \prod_{k=1}^{n} \frac{1}{1-x^k}. \end{equation*}

   More generally, for any integer \(m\text{,}\) what kind of partitions of \(m\) does \(Q_n(x)\) count? Solution.

   The \(m\)th coefficient of \(Q_n(x)\) counts the number of partitions of \(m\) into parts of size at most \(n\text{.}\)

2. Let \(d_n\) be the number of integer partitions of \(n\) into distinct parts. Find a concise expression for the generating function \(D(x) = \sum_{n=0}^{\infty} d_n x^n.\) Solution.

   \begin{equation*} D(x) = \prod_{k=1}^{\infty} (1+x^k) \end{equation*}

3. What is the generating function partitions of \(n\) into odd parts? Solution.

   \begin{equation*} A(x) = \prod_{k=1}^{n} \frac{1}{1-x^{2k+1}}. \end{equation*}

4. What is the generating function of partitions of \(n\) into distinct odd parts? Solution.

   \begin{equation*} D(x) = \prod_{k=1}^{\infty} (1+x^{2k+1}) \end{equation*}

2. Product Formula for Exponential Generating Functions.

Suppose that we have tasks \(\cA\) and \(\cB\) where you can complete \(\cA\) on an \(n\)-set in \(a_n\) ways, and you can complete \(\cB\) on an \(n\)-set in \(b_n\) ways.

1. How many ways are there to:

   • Choose a \(k\)-set \(S \subset [n]\text{,}\)

   • Perform \(\cA\) on \(S\text{,}\) and then

   • Perform \(\cB\) on \(\overline{S} = [n] \backslash S\text{.}\)

   Solution.

   \begin{equation*} {n \choose k} a_k b_{n-k} \end{equation*}

2. Let \(\cC\) be the following task:

   • Choose a subset \(S \subset [n]\) (of any size \(k\text{,}\) where \(0 \leq k \leq n\text{,}\)

   • Perform \(\cA\) on \(S\text{,}\) and then

   • Perform \(\cB\) on \(\overline{S}\text{.}\)

   How many ways \(c_n\) are there to complete task \(\cC\) on \([n]\text{?}\) Be careful: parts (b) and (c) depend upon the size \(k\) of \(S\text{.}\) Solution.

   \begin{equation*} \sum_{k=0}^n {n \choose k} a_k b_{n-k} \end{equation*}

3. Consider the functions

   \begin{equation*} \begin{array}{ccc} A(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n & \mbox{and} & B(x) = \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n. \end{array} \end{equation*}

   Find the coefficient of \(x^n\) in the product \(A(x)B(x)\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} A(x) B(x) &=& \left( \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n \right) \left( \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n \right)\\ &=& \sum_{n=0}^{\infty} \left( \sum_{k=0}^n \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!} \right) x^n \\ &=& \sum_{n=0}^{\infty} \left( \sum_{k=0}^n {n \choose k} a_k b_{n-k} \right) \frac{ x^n}{n!} \\ \end{array} \end{equation*}

4. Let \(C(x)\) be the exponential generating function EGF for the task \(\cC\) in part (b). Use your answers from problems 2 and 3 to prove that \(C(x) = A(x) B(x)\text{,}\) where \(A(x)\) and \(B(x)\) are the EGFs for tasks \(\cA\) and \(\cB\text{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} C(x) &=& A(x) B(x) \\ &=& \left( \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} \right) \left( \sum_{n=0}^{\infty} b_n \frac{x^n}{n!} \right)\\ &=& \sum_{n=0}^{\infty} \left( \sum_{k=0}^n \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!} \right) x^n \\ &=& \sum_{n=0}^{\infty} \left( \sum_{k=0}^n {n \choose k} a_k b_{n-k} \right) \frac{ x^n}{n!} \\ \end{array} \end{equation*}

3. Painting Houses.

Suppose that we want to paint \(n\) distinct houses on a block. For simplicity, we use \([n]\) to label the houses. We paint each house with one different color, chosen from: red, orange, yellow, green, blue and purple.

1. Our first boss says that all houses of the same color must be adjacent, and we must use the colors from left-to-right following the rainbow ordering. How many ways can we paint the houses

   1. If we do not have to use all of the colors? Solution.

      \begin{equation*} { n +5 \choose 5} \end{equation*}

   2. If we must use each color at least once? Solution.

      \begin{equation*} { n-1 \choose 5} \end{equation*}

2. Our first boss gets fired for his lack of creativity. Our second boss only requires that the "warm" colors red, orange, yellow are separate from the "cool" colors green, blue, purple. He says we should start painting with warm colors, then switch to cool colors after some number of houses (possibly 0).

   1. What is the generating function \(F_1(x)\) for painting \(n\) houses with the warm colors red, orange and yellow? Solution.

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

   2. What is the generating function \(F_2(x)\) for painting \(n\) houses with the cool colors green, blue and purple? Solution.

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

   3. What is the generating function \(F(x)=F_1(x)F_2(x)\) for the number of ways to paint the houses to our boss's specifications? Solution.

      \begin{equation*} F_1(x) F_2(x) = \frac{1}{(1-3x)^2} \end{equation*}

   4. What is the formula \(f_n\) for the number of ways to paint \(n\) houses to our boss's specifications?? Solution.

      \begin{equation*} \begin{array}{rcl} F(x) \,= \, \sum_{n=0}^{\infty} f_n x^n & = & \frac{1}{(1-3x)^2} \\ &=& \sum_{n=1}^{\infty} n (3x)^{n-1} = \sum_{m=0}^{\infty} (m+1) 3^m x^{m}. \end{array} \end{equation*}

      So \(f_m = (m+1) 3^m\) for \(m \geq 0\text{.}\)

   5. Give a combinatorial argument for the answer you found in part (iv). Solution.

      • Next, we paint the warm houses in \(3^k\) ways

      • Finally, we paint the cool houses in \(3^{n-k}\) ways.

      The total number of ways is

      \begin{equation*} (n+1) 3^k \cdot 3^{n-k} = (n+1) 3^n. \end{equation*}

3. Our second boss quits to become a yoga instructor. Our third boss is tries to cut corners. Red and orange paint are cheap. He asks us to paint some subset of houses using the colors red and orange (these houses do NOT have to be consecutive). For the remaining houses, we are supposed to paint exactly one house in each of the remaining 4 colors, and leave the other houses unpainted.

   1. What is the exponential generating function \(G_1(x)\) for the number of ways to paint \(n\) houses using colors red and orange? Solution.

      \begin{equation*} G_1(x) = \sum_{n=0}^{\infty} 2^n \frac{x^n}{n!} = e^{2x} \end{equation*}

   2. What is the exponential generating function \(G_2(x)\) for the number of ways of painting 4 out of \(n\) houses, one yellow, one green, one blue, one purple. Solution.

      \begin{equation*} G_2(x) = \sum_{n=4}^{\infty} (n)_4 \frac{x^n}{n!} = \sum_{n=4}^{\infty} \frac{x^n}{(n-4)!} = x^4 \sum_{n=4}^{\infty} \frac{x^{n-4}}{(n-4)!} = x^4 \sum_{m=0}^{\infty} \frac{x^{m}}{m!} = x^4 e^x \end{equation*}

   3. What is the exponential generating function \(G(x)\) for the number of ways to paint the houses to our boss's specifications? Solution.

      \begin{equation*} x^4 e^{3x} \end{equation*}

   4. What is the formula \(g_n\) for the number of ways to paint \(n\) houses to our boss's specifications? Solution.

      \begin{equation*} \begin{array}{rcl} G(x) \, = \, \sum_{n=0}^{\infty} g_n \frac{ x^n}{n!} &=& x^4 e^{3x} \, = \, x^4 \sum_{n=0}^{\infty} 3^n \frac{ x^n}{n!} \, = \, \sum_{n=0}^{\infty} 3^n \frac{ x^{n+4}}{n!} \, = \, \sum_{n=0}^{\infty} 3^n \frac{ x^{n+4}}{(n+4)!} \\ &=& \sum_{m=4}^{\infty} 3^{m-4} \frac{ x^{m}}{(m-4)!} \, = \, \sum_{m=4}^{\infty} 3^{m-4} (m)_4 \frac{ x^{m}}{m!}. \end{array} \end{equation*}

      So we have \(g_m = 3^{m-4} (m)_4\text{.}\)

   5. Give a combinatorial argument for the answer you found in part (iv). Solution.

      • First, we choose one house to color yellow, one house to color green, one house to color blue, and one house to color purple. This can be done in \((n)_4\) ways.

      • The remaining \(n-4\) houses, can each be red, orange, or unpainted. The number of possibilities is \(3^{n-4}\text{.}\)

      The total number of ways is

      \begin{equation*} (n)_4 3^{n-4}. \end{equation*}

4. Our third boss gets fired for absconding with company money. Our fourth boss tells us to just paint the houses any way we want.

   1. How many ways are there to paint the houses, with no restrictions? Solution.

      \begin{equation*} 6^n \end{equation*}

   2. How many ways are there to paint the houses if we must use each color at least once? Solution.

      \begin{equation*} 6! S(n,6) \end{equation*}

4. Children Playing in the Park.

A group of (distinct) children are at the park. One nonempty subset decides to play ring-around-the-rosie, and they form a circle. The remaining children (if there are any who don't play) head to the snack bar and line up to get ice cream.

1. Let \(a_n\) denote the number of ways for \(n\) children to form a circle in order to play ring-around-the-rosie. We know that \(a_0=0\) because the set of children playing is nonempty. Find the exponential generating function

   \begin{equation*} A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = \sum_{n=1}^{\infty} a_n \frac{x^n}{n!}. \end{equation*}

   Solution.

   \begin{equation*} A(x) = \sum_{n=1}^{\infty} a_n \frac{x^n}{n!} = \sum_{n=1}^{\infty} (n-1)! \cdot \frac{x^n}{n!} = \sum_{1=0}^{\infty} \frac{x^n}{n} = \log \left( \frac{1}{1-x} \right) \end{equation*}

2. Let \(b_n\) denote the number of ways for \(n\) children to line up to get ice cream. Find the exponential generating function

   \begin{equation*} B(x) = \sum_{n=0}^{\infty} b_n \frac{x^n}{n!}. \end{equation*}

   Solution.

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

3. Let \(c_n\) denote the number of ways that \(n\) children can divide into two groups, one that plays ring-around-the-rosie and another that gets ice cream. We know that

   \begin{equation*} C(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!} = A(x)B(x). \end{equation*}

   Write down the exponential generating function \(C(x)\text{.}\) Solution.

   \begin{equation*} C(x) = A(x)B(x) = \frac{1}{1-x} \cdot \log \left( \frac{1}{1-x} \right) \end{equation*}

4. Use parts (a),(b),(c) to find a formula for \(c_n\text{.}\) (It will contain one summation sign.) Solution.

   \begin{equation*} \begin{array}{rcl} C(x) &=& A(x)B(x) \, = \, \left( \sum_{n=1}^{\infty} \frac{x^n}{n} \right) \left( \sum_{n=0}^{\infty} x^n \right) \\ &=& \sum_{n=0}^{\infty} \left( \sum_{k=1}^{n} \frac{1}{k} \right) x^n = \sum_{n=0}^{\infty} \left( n! \sum_{k=1}^{n} \frac{1}{k} \right) \frac{x^n}{n!} \\ \end{array} \end{equation*}

   Therefore

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

5. Give a direct combinatorial explanation for the formula in part (d). Solution.

   • Pick a \(k\) such that \(1 \leq k \leq n\text{.}\)

   • Line up all the children in a row. This can be done in \(n!\) ways.

   • The first \(k\) children form a circle. We must divide by \(k\) for symmetry since there are \(k\) different orderings of these children that result in the same circle.

   • The last \(n-k\) children head off for ice cream, keeping the same order.