Skip to main content

Chapter 6 Compositions of Integers

Exercises Practice Problems

1. Compositions of \(n\).

Let \(n\) be a positive integer. A composition of \(n\) into \(k\) parts is an ordered sequence of positive numbers \(a_1, a_2, \ldots , a_k\) such that

\begin{equation*} \sum_{i=1}^{k} a_i = n. \end{equation*}

  1. There are 3 distinct compositions of 4 into 3 parts. List them all. Solution.

    \begin{equation*} \begin{array}{ccccc} 2+1+1 && 1+2+1 && 1+1+2 \end{array} \end{equation*}

  2. Which "balls in boxes" problem is equivalent to the composition of \(n\) into \(k\) parts? Explain. Solution.

    This is the same as placing \(n\) identical balls into \(k\) distinct boxes such that

    • Repetition is allowed (boxes can receive more than one ball)

    • Every box must get at least one ball

    The \(k\) boxes correspond to the \(k\) terms. The boxes are distinct because the order of the terms matters. We set \(a_i\) to be the number of balls in box \(i\text{.}\) Every \(a_i\) must be positive, so we require that every box gets at least one ball.

  3. What is the formula for the number of compositions of \(n\) into \(k\) parts? Solution.

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

  4. What is the formula for the number of compositions of \(n\) into any number of parts? Find a simple closed formula for this number. Solution.

    \begin{equation*} \sum_{k=1}^{n} {n-1 \choose k-1} = \sum_{i=0}^{n-1} { n-1 \choose i} = 2^{n-1} \end{equation*}

2. Weak Compositions of \(n\).

Let \(n\) be a positive integer. A weak composition of \(n\) into \(k\) parts is an ordered sequence of non-negative numbers \(a_1, a_2, \ldots , a_k\) such that

\begin{equation*} \sum_{i=1}^{k} a_i = n. \end{equation*}

  1. There are 15 distinct weak compositions of 4 into 3 parts. List them all. Solution.

    \begin{equation*} \begin{array}{ccccccccc} 4 + 0 + 0 && 2 + 2 + 0 && 1 + 3 + 0 && 1 + 0 + 3 && 0 + 2 + 2 \\ 3 + 1 + 0 && 2 + 1 + 1 && 1 + 2 + 1 && 0 + 4 + 0 && 0 + 1 + 3 \\ 3 + 0 + 1 && 2 + 0 + 2 && 1+ 1 + 2 && 0 + 3 + 1 && 0 + 0 + 4. \end{array} \end{equation*}

  2. Which "balls in boxes" problem is equivalent to the weak composition of \(n\) into \(k\) parts? Explain. Solution.

    This is the same as placing \(n\) identical balls into \(k\) distinct boxes such that

    • Repetition is allowed (boxes can receive more than one ball)

    • Boxes may be empty

    The reasoning is the same as for compositions. This time, boxes can be empty because we now allow \(a_i=0\text{.}\)

  3. What is the formula for the number of weak compositions of \(n\) into \(k\) parts? Solution.

    \begin{equation*} {n+k-1 \choose k-1} \end{equation*}

  4. Explain why the number of weak compositions of \(n\) into any number of parts is infinite. Solution.

    We do not specify the number of parts, which means that we can include an arbitrary number of zeros in the sum. This means that there are an infinite number of weak compositions of any integer \(n\text{.}\)