## PROBLEM 2. ORDERED PARTITIONS OF A NUMBER $n$

The number 3 can be expressed as the sum of one or more natural numbers in four ways, if the order of the terms is taken into account:

$$
3,1+2,2+1,1+1+1
$$

In how many ways can the number $n$ be expressed as a sum?
Solution. Consider a row of $n$ ones placed in a line. Any arrangement of $n-1$ or fewer dividing dashes in the gaps 8
between the ones corresponds to a partition of the number into summands and vice versa:

$$
\begin{gathered}
11|1| 11|1| 11 \ldots 111 \\
n=2+3+1+n-6 .
\end{gathered}
$$

Since we can either insert a dividing dash or not in each of the $n-1$ gaps, there are exactly $2^{n-1}$ ways to place the dividing dashes and the same number of expressions for the number $n$.