Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
This question is equivalent to the question here: math.stackexchange.com/questions/41610/… –  JavaMan May 30 '11 at 20:13
    
Also, see en.wikipedia.org/wiki/Stars_and_bars_(probability) –  JavaMan May 30 '11 at 20:14

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
Thanks, this did it for me. –  Pele May 30 '11 at 21:09
    
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! –  Hai Phan May 17 '13 at 18:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.