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. 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?

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$.
