Chapter 14 Generating Functions for Integer Compositions
Exercises Practice Problems
1. Generating Function for Weak Compositions of Integers.
In this problem, we will use generating functions to prove that
Recall that a weak composition of \(n\) into \(k\) parts is an ordered list of nonnegative integers \((a_1, a_2, \ldots , a_k)\) such that \(\sum_{i=1}^k a_i =n\) and \(a_i \geq 0\) for \(1 \leq i \leq k\text{.}\)
There are 5 weak compositions of 4 into 2 parts. List them. Solution.
\begin{equation*} \begin{array}{ccccc} 4+0 & 3+1 & 2+2 & 1+3 & 0+4 \end{array} \end{equation*}Using balls in boxes, find a formula for the number of weak compositions of \(n\) into \(k\) parts. Solution.
We can model this problem using \(n\) identical balls, \(k\) distinct boxes, repetition allowed, boxes cannot be empty. Therefore the number of ways is
\begin{equation*} {n+k-1 \choose k-1} \end{equation*}What is the generating function \(F_1(x)\) for the number of weak compositions of \(n\) into 1 part? Solution.
\begin{equation*} F_1(x) = 1 + x + x^2 + x^3 + \cdots = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}. \end{equation*}Basically, there is one way to partition \(n\) into one part for every \(n \geq 0\text{.}\)
Use the product principle (for generating functions) to find the generating function \(F_2(x)\) for the number of weak compositions of \(n\) into 2 parts. Solution.
We need to choose the first part, and then choose the second part. The generating function takes care of all the algebra for us.
\begin{equation*} \begin{array}{rcl} F_2(x) &=&\underbrace{(1+x+x^2 + x^3 + \cdots)}_{\mbox{choose the first part}} \,\, \underbrace{(1+x+x^2 + x^3 + \cdots)}_{\mbox{choose the second part}} \\ &=& F_1(x) \cdot F_1(x) \,=\, \frac{1}{(1-x)^2}. \end{array} \end{equation*}Important! This is a conceptual question rather than a computation question. The function \(F_1(x)\) encodes all the information about choosing one part. We perform a two phase process: choose the first part and then choose the second part. This corresponds to multiplying generating functions. Algebra takes care of performing the right combinations for each problem size.
What is the generating function \(F_k(x)\) for the number of weak compositions of \(n\) into \(k\) parts? Solution.
\begin{equation*} F_k(x) = \underbrace{F_1(x) \cdot F_1(x) \cdots F_1(x)}_{k \mbox{ times}} = \frac{1}{(1-x)^k}. \end{equation*}-
Why does this prove that
\begin{equation*} \frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} {n+k-1 \choose k-1} x^n \end{equation*}holds? Solution.
Combining the results for parts (b) and (e), we have
\begin{equation*} \frac{1}{(1-x)^k} = F_k(x) = \sum_{n=0}^{\infty} f_n x^n = \sum_{n=0}^{\infty} {n+k-1 \choose k-1} x^n \end{equation*}
2. Generating Function for Compositions of Integers.
Recall that a (strong) composition of \(n\) into \(k\) parts is an ordered list of positve integers \((a_1, a_2, \ldots , a_k)\) such that \(\sum_{i=1}^k a_i =n\) and \(a_i \geq 1\) for \(1 \leq i \leq k\text{.}\) In this exercise, we will use generating functions to prove that the number of strong compositions of \(n\) into \(k\) parts is
(Note: \({n-1 \choose k-1}\) is defined to be \(0\) when \(n < k\) because it is impossible to pick more elements than we have. So technically, we don't need to point this out again.)
There are 10 compositions of 6 into 3 parts. List them. Solution.
\begin{equation*} \begin{array}{ccccc} 4+1+1 & 3+2+1 & 3+1+2 & 2+3+1 & 2+2+2 \\ 2+1+3 & 1+4+1 & 1+3+2 & 1+2+3 & 1+1+4 \end{array} \end{equation*}What is the generating function \(G_1(x)\) for the number of compositions of \(n\) into 1 part? Solution.
Unlike weak compositions, 0's are not allowed. So
\begin{equation*} G_1(x) = x+ x^2 + x^3 + x^4 + \cdots = x ( 1 + x + x^2 + x^3 +\cdots ) = \frac{x}{1-x}. \end{equation*}Use the product principle (for generating functions) to find the generating function \(G_2(x)\) for the number of compositions of \(n\) into 2 parts. Solution.
The argument is similar to Problem 4 about weak compositions.
\begin{equation*} \begin{array}{rcl} G_2(x) &=&\underbrace{(x+x^2 + x^3 + \cdots)}_{\mbox{choose the first part}} \,\, \underbrace{(x+x^2 + x^3 + \cdots)}_{\mbox{choose the second part}} \\ &=& G_1(x) \cdot G_1(x) \,=\, \frac{x^2}{(1-x)^2}. \end{array} \end{equation*}What is the generating function \(G_k(x)\) for the number of compositions of \(n\) into \(k\) parts? Solution.
\begin{equation*} G_k(x) = \underbrace{G_1(x) \cdot G_1(x) \cdots G_1(x)}_{k \mbox{ times}} = \frac{x^k}{(1-x)^k}. \end{equation*}Starting from the known power series for weak compositions \(F_k(x)\text{,}\) find the power series for compositions \(G_k(x)\text{.}\) Hint: re-index using \(m=n+k\text{.}\) Solution.
Using the result of Problem 6 on about weak compositions, we have
\begin{equation*} \begin{array}{rcl} G_k(x) &=& \frac{x^k}{(1-x)^k} \, = \, x^k \frac{1}{(1-x)^k} \\ &=& x^k \displaystyle{\sum_{n=0}^{\infty} {n+k-1 \choose k-1} x^n} \\ &=&\displaystyle{ \sum_{n=0}^{\infty} {n+k-1 \choose k-1} x^{n+k}} \\ &=& \displaystyle{\sum_{m=k}^{\infty} {m-1 \choose k-1} x^{m}}. \end{array} \end{equation*}This says that the number of compositions of \(m\) into \(k\) parts is 0 when \(m < k\) and is \({m-1 \choose k-1}\) when \(m \geq k\text{.}\) This matches our answer from the balls-and-boxes taxonomy.