# Numbers of solutions of $\sum_{i=1}^{k}x_i=n$ in $\mathbb{N}_0$

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.

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

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

-