How many ways can a natural number n be expressed as a sum of one or more positive integers, taking order into account?

Q: The number 4 can be expressed as a sum of one or more positive integers, taking order into account, in 8 ways: \begin{array}{l} 4&=1+3&=3+1&=2+2&=1+1+2\\ &=1+2+1&=2+1+1&=1+1+1+1. \end{array} In general, given $\mathbb n$ $\in$ $\mathbb N$, how many ways can $\mathbf n$ be so expressed?

Query: I managed to solve it via a combinatoric proof, but the solution provided is as such: \begin{align} &~~Idea: n= x_1 + x_2 +...+x_k, k \in \mathbb N, x_k \gt 0.\\ &\implies x_1 - 1 + x_2 - 1 +...+ x_k -1 = n - k\\ &\implies x_1* + x_2* + ... + x_k* = n-k \qquad-(*) \end{align} Since $H^n_r$ = \begin{pmatrix} r+n-1 \\ r \end{pmatrix}, we have $H^k_{n-k}$ = \begin{pmatrix} n-k+k-1 \\ n-k \end{pmatrix} And the answer is as such: $$\sum_{k=1}^n H^k_{n-k} =$$ $$\sum_{k=1}^n \begin{pmatrix} n-1 \\ n-k \end{pmatrix} = 2^{n-1}$$. I have no idea why $H^n_r$ is applied and also why $$\sum_{k=1}^n H^k_{n-k}$$ is used to derive the desired result $$2^{n-1}$$. Some explanation on this will be deeply appreciated.

Solution 1:

One way to see why the answer is $2^{n-1}$ directly is to write $n$ as a sum of $1$s:

$$ n = \underbrace{1 + 1 + 1 + ... + 1}_{n \textrm{ times}}. $$

Of course, this expresses $n$ as a sum of $1$s, but we want all expressions of $n$ as a sum of (ordered) positive numbers.  To do so, for each '$+$' in the expression above, we can choose whether or not to split the sum there to form a new summand. For example, suppose $n = 8$.  Then we start with

$$ 8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. $$

Now suppose we choose to split the sum at the 2nd, 3rd and 5th plus signs, highlighted below.

$$ 8 = 1 + 1 \color{red}{+} 1 \color{red}{+} 1 + 1 \color{red}{+} 1 + 1 + 1. $$

We now add up the $1$'s between the chosen plusses to form the summands,

$$ 8 = (1+1) \color{red}{+} 1 \color{red}{+} (1+1) \color{red}{+} (1+1+1) = 2 \color{red}{+} 1 \color{red}{+} 2 \color{red}{+} 3,$$

giving an expression of $8$ as a sum of positive integers.

In general, this clearly bijects to all expressions of $n$ as an ordered sum of positive integers. Since there are $n-1$ plus signs between the $n$ $1$s, there are $2^{n-1}$ ways of choosing where to split the sum, and hence $2^{n-1}$ possible sums.

Solution 2:

What you are looking for is compositions of $n$

Take a string of $1's,\;$ e.g.$\; \large 1{\boxed.} 1\boxed. 1\boxed. 1$

In the $\;(n-1)\;$ boxes, either put a $+\;$ or a comma.

$1,\;\;1+1+1$ e.g. would represent $1+3$

Since you have $2$ choices for each box, # of compositions = $2^{n-1}$

Solution 3:

Since your title carefully distinguishes between natural numbers (which include $0$) and positive integers (which do not, at least not for the English sense of "positive"), I think a formula should be given that gives the proper value (namely $0$, since at least one summand was required) for $n=0$, and $2^{n-1}$ does not do that. A correct formula would be $\lfloor2^{n-1}\rfloor$, or you could just give the value as $$ \begin{cases}0&\text{if $n=0$,}\\2^{n-1}&\text{if $n>0$.}\end{cases} $$ The proof can be simply by induction, where we need $n=0$ and $n=1$ as starting cases to capture the exceptional behaviour at $n=0$ (both starting cases are obvious). If we assume for $n>0$ proved that there $2^{n-1}$ compositions of $n$, then from each of them we can get two different compositions of $n+1$: one by increasing the final term by one, and another by adding a new term $1$ and the end. It is clear that the first method, applied to all compositions of $n$ gives all compositions of $n+1$ that do not have $1$ as final term, and the other method gives all compositions of $n+1$ that do have $1$ as final term. Together that gives all compositions of $n+1$, and each of them in just one manner; their number is then $2^{n-1}\times2=2^n$, as was to be proved.

Note that the inductive step cannot be applied to the case $n=0$, as there is no final term to modify there; this explains the exception at the start of the sequence.