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.

In a certain problem, the solution states that number of solutions of $a+b+c+d=13$ is $\binom{16}{3}$, so I'm guessing that my following statement is true:

The number of solutions of $$ \sum_{i=1}^{k}x_i=n $$ where $x_i\in\mathbb{N}_0$ is $$ \binom{n+k-1}{k-1}. $$

How can it be proven? Or, if my conclusion is wrong, what's correct interpretation? I'm relatively new to combinatoricss.

share|improve this question
    
See math.stackexchange.com/questions/86820/… and the questions cited in comments there. –  Gerry Myerson Feb 6 '13 at 23:10

1 Answer 1

This is the Stars and Bars problem. We want to find the total number of natural number solutions for the following equation: $$\displaystyle \sum_{i=1}^{n} a_i = N, \text{ where } a_i \in \mathbb{Z}^+$$

The method is as follows:

Consider $N$ sticks.

$$\vert \vert \vert \vert \vert \vert \ldots \vert \vert \vert $$

We want to do partition these $N$ sticks into $n$ parts.

This can be done if we draw $n-1$ long vertical lines in between these $N$ sticks.

The number of gaps between these $N$ sticks is $N-1$.

So the total number of ways of drawing these $n-1$ long vertical lines in between these $N$ sticks is $C(N-1,n-1)$.

So the number of natural number solutions for $\displaystyle \sum_{i=1}^{n} a_i = N$ is $$\color{blue}{C(N-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) = N$$ i.e. $$\displaystyle \sum_{i=1}^{n} b_i = N + n$$

So the number of non-negative integer solutions to $\displaystyle \sum_{i=1}^{n} a_i = N$ is given by $$\color{blue}{C(N+n-1,n-1)}$$

share|improve this answer

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.