Sum decompositions

Task number: 4399

Count how many decompositions of \(n\) exist into an ordered sum of positive integers. For example, for \(n=3\) these are \(1+1+1\), \(1+2\), \(2+1\) and \(3\).
  • Answer

    There are \(2^{n-1}\) decompositions of \(n\).
  • Solution

    Let \(R_n\) denote the number of decompositions of the number \(n\). We manually calculate \(R_0\)=1 (empty decomposition), \(R_1=1\), \(R_2=2\), \(R_3=4\). This suggests that \(R_n=2^{n-1}\) could hold for \(n>0\). This is easy to prove by induction: when the decomposition starts with the number \(k\), the remaining terms form the decomposition of the number \(n-k\). So \(R_n=\sum\limits_{k=1}^n R_{n-k}\), so by induction hypothesis \(R_n =R_0 + \sum\limits_{k=1}^{n-1} R_{n-k} = 1 + \sum\limits_{k=1}^{n-1} R_{k} = 1 + \sum\limits_{k=1}^{n-1} 2^{k-1} =1+\sum\limits_{k=0}^{n-2} 2^k = 2^{n-1}\).

    Alternatively we can solve the problem by combinatorial reasoning. Each decomposition can be obtained from \(1+1+1+\ldots+1\) by joining some adjacent ones into groups. The breakdown into groups is clearly determined by which ones are at the end of the group. It may or may not end with the first \(n-1\) ones; always ends with the last one. Hence there are \(2^{n-1}\) options to terminate groups.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email