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.

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

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

  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.

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.

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

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

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