Chapter 15 Products of Generating Functions II
Exercises Practice Problems
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."
-
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{.}\)
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*}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*}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.
-
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{.}\)
\begin{equation*} {n \choose k} a_k b_{n-k} \end{equation*} -
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*} -
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*} 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.
-
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
-
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).
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*}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*}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*}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{.}\)
Give a combinatorial argument for the answer you found in part (iv). Solution.
First, we split the houses into two categories: warm houses and cool houses. We have \(k\) warm houses followed by \(n-k\) cool houses, where \(0 \leq k \leq n\text{.}\) So we have \(n+1\) choices for \(k\text{.}\)
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*}
-
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.
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*}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*}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*}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{.}\)
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*}
-
Our third boss gets fired for absconding with company money. Our fourth boss tells us to just paint the houses any way we want.
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.
-
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*}\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*} -
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*}\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*} -
Let \(c_n\) denote the number of ways that \(n\) children can divide into two groups, one (nonempty) group that plays ring-around-the-rosie and another (possibly empty) group that lines up for 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*} 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*}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.
5. EGF for the Bell Numbers.
In this problem, you will create the exponential generating function for the number of surjections onto a set of size \(k\text{.}\) We will then use it to find the EGFs for the Stirling numbers \(S(n,k)\) and the Bell numbers \(B(n)\text{.}\)
Let \(t_n\) be the number of surjections from \([n]\) to \([1]\text{,}\) where \([1] = \{ 1 \}\) is the set of size 1. Find the formula for the EGF \(T(x) = \sum_{n=0}^{\infty} t_n \frac{x^n}{n!}.\) (And pay close attention to the value of \(t_0\text{.}\)). Solution.
We have \(t_0=0\) since there are no surjections from the empty set \(\emptyset\) to \([1]\text{.}\) For \(n \geq 1\text{,}\) there is one (surjective) function from \([n]\) to \([1]\text{.}\) So
\begin{equation*} T(x) = \sum_{n=1}{\infty} \frac{x^n}{n!} = e^x -1. \end{equation*}Explain why \(T(x)^2\) is the EGF for the number of surjections from \([n]\) to \([2]\text{.}\) Solution.
This follows from the Product Formula for EGFs. We split \([n]\) into a nonempty set \(S\) and its nonempty complement \(\overline{S}\text{.}\) (The sets are nonempty because \(t_0=0\text{.}\)) We then map \(S\) to element \(1\) and map \(\overline{S}\) to element \(2\text{.}\) And we have
\begin{equation*} T(x)^2 = (e^x-1)^2. \end{equation*}Find the formula for the EGF for the number of surjections from \([n]\) to \([k]\text{.}\) Solution.
By induction, the EGF is
\begin{equation*} T(x)^k = (e^x-1)^k. \end{equation*}-
Use your answer from part (c) to prove that the EGF for set partitions into exactly \(k\) parts is
\begin{equation*} S_k(x) = \frac{1}{k!} (e^x -1)^k. \end{equation*}The number of surjections from \([n]\) to \([k]\) is \(k! S(n,k)\text{.}\) So we must divide the EGF from part (c) by \(k!\) so that the coefficients of the EGF are the Stirling numbers \(S(n,k)\)
-
Next, we use the EGFs from part (d) to find the EGF for the Bell numbers. Set \(S_0(x) = 1\) to be the EGF for partitioning \([n]\) into zero parts (why?), explain why the EGF for the Bell numbers is
\begin{equation*} B(x) = \sum_{k=0}^{\infty} S_k(x). \end{equation*}Now substitute \(S_k(x) = \frac{1}{k!} (e^x -1)^k\) and simplify the expression for \(B(x)\) using the Bestiarum Generandi to find a truly marvelous generating function for the Bell numbers! Solution.
First off, \(S_0(x)=1\) because there is one way to "do nothing" when \(n=0\text{,}\) and otherwise, it is impossible to define a function from \([n]\) to \(\emptyset\text{.}\)
Now, we have
\begin{equation*} B(x) = S_0(x) + S_1(x) + S_2(x) + \cdots = \sum_{k=0}^{\infty} S_k(x) \end{equation*}because addition corresponds to "or." In this case we, either partition \([n]\) into 0 parts, or into 1 parts, or into 2 parts, etc. And now we simplify:
\begin{equation*} B(x) = \sum_{k=0}^{\infty} S_k(x) = \sum_{k=0}^{\infty} \frac{(e^x-1)^k}{k!} = e^{e^x-1}. \end{equation*}Wow!