Number of ways of partitioning a sum into ordered non-negative summands Lets say that I have an a sum $S$ consisting of $n$ elements. Apparently, there are ${S+n-1} \choose {n-1}$ number of ways of partitioning that sum into $n-1$ ordered non-negative summands.
I don't fully understand why this is so. How could I best explain this to myself? Also, why is "ordered" mentioned here? What does it mean in this context?
Thanks!
 A: The word "ordered" in the question means that the solutions $(0,2,3)$ and $(0,3,2)$ for $a_1 + a_2 + a_3 = 5$ are different.
We want to find the total number of positive integer solutions for the following equation:
$\displaystyle \sum_{i=1}^{n} a_i = S$, where $a_i \in \mathbb{Z}^{+}$
The method is as follows:
Consider $S$ sticks.
$$| | | | | | | | ... | | |$$
We want to do partition these $S$ sticks into $n$ parts.
This can be done if we draw $n-1$ long vertical lines in between these $S$ sticks.
The number of gaps between these $S$ sticks is $S-1$.
So the total number of ways of drawing these $n-1$ long vertical lines in between these $S$ sticks is $C(S-1,n-1)$.
So the number of positive integer solutions for $\displaystyle \sum_{i=1}^{n} a_i = S$ is $C(S-1,n-1)$.
If we are interested in the number of non-negative integer solutions, all we need to do is replace $a_i = b_i - 1$ and count the number of natural number solutions for the resulting equation in $b_i$'s.
i.e. $\displaystyle \sum_{i=1}^{n} (b_i - 1) = S$ i.e. $\displaystyle \sum_{i=1}^{n} b_i = S + n$.
So the number of non-negative integer solutions to $\displaystyle \sum_{i=1}^{n} a_i = S$ is given by $C(S+n-1,n-1)$
