1
$\begingroup$

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!

  • 0
    Also, see http://en.wikipedia.org/wiki/Stars_and_bars_(probability)2011-05-30

1 Answers 1

7

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

  • 0
    Nice answer. I also wonder what the result is for the case that the order does not matter. i.e the problem putting S balls into n boxes. The boxes and balls are not labeled. What if a box can take zero ball. And if it must have at least one ball. Do we just take the result above and divide by n!2013-05-17