Skip to main content

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

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

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{.}\)

  1. There are 5 weak compositions of 4 into 2 parts. List them.

  2. Using balls in boxes, find a formula for the number of weak compositions of \(n\) into \(k\) parts.

  3. What is the generating function \(F_1(x)\) for the number of weak compositions of \(n\) into 1 part?

  4. 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.

  5. What is the generating function \(F_k(x)\) for the number of weak compositions of \(n\) into \(k\) parts?

  6. 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?

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

\begin{equation*} \displaystyle{{n-1 \choose k-1}} \mbox{ when } n \geq k, \mbox{ and } 0 \mbox{ when } n < k. \end{equation*}

(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.)

  1. There are 10 compositions of 6 into 3 parts. List them.

  2. What is the generating function \(G_1(x)\) for the number of compositions of \(n\) into 1 part?

  3. 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.

  4. What is the generating function \(G_k(x)\) for the number of compositions of \(n\) into \(k\) parts?

  5. 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{.}\)