Prove that the number of different ways to write an integer X as a sum of positive integers is $2^z$, if the order matters.

Question

As an example for number 5, it is equal to $2^4$.

We can prove it by brute-forcing it, since it's a small number, as follows:

$1+1+1+1+1 $

$1+1+1+2 $

$1+1+2+1 $

$1+2+1+1 $

$2+1+1+1$

$1+1+3 $

$1+3+1$

$3+1+1$

$2+2+1$

$2+1+2$

$1+2+2$

$2+3$

$3+2$

$1+4$

$4+1$

$5$

What is a faster, more elegant way to do this?

Answer 1

Let $f(n)$ be the number you're looking for for a given $n$. Let's work by strong induction.

Consider $f(n+1)$. It could either have one term (which happens in one way) or more than one term. In this second case, the second term can be any number from $1$ through $n$. If the first term is $k$, then there are $f(n+1-k)$ ways to complete that sum. Adding all that together with our induction hypothesis that $f(k)=2^{k-1}$, we get

$$f(k+1)=1+2^0+2^1+...+2^{k-1}$$

which is obviously $f(k+1)=2^k$.

Answer 2

Let the number be $z + 1$. Jot down $1$ on your paper.

Now decide whether you want to add $1$ to the last number you already wrote down (i.e. make it $2$) or proceed to the next factor in the sum ($1+1$). You have two choices here.

Continue like this and make the decision to add one to the last number or proceed $z$ times. This leads to $2^z$ distinct configurations, depending on which series of two-option choices you made.

You still have to prove that you can achieve any desired factorization with this process, and that different choices made lead to different factorizations, but neither are particularly hard.

Answer 3

Write down $1+1+\cdots+1=X$. Now group runs of adjacent ones by going from left to right and for each $+$ sign you encounter deciding whether or not a group boundary occurs there. Parenthesize each group to get a partition of $X$ into a sum of nonnegative integers. Each possible choice of group boundaries corresponds to a distinct partition if order matters (prove this!) and there are $X-1$ decision points, therefore there are $2^{X-1}$ such partitions of $X$.