# Number of solutions for $x[1] + x[2] + \ldots + x[n] =k$

Omg this is driving me crazy seriously, it's a subproblem for a bigger problem, and i'm stuck on it.

Anyways i need the number of ways to pick $x[1]$ ammount of objects type $1$, $x[2]$ ammount of objects type $2$, $x[3]$ ammounts of objects type $3$ etc etc such that $$x[1] + x[2] + \ldots x[n] = k\;.$$ Order of the objects of course doesn't matter.

I know there is a simple formula for this something like $\binom{k + n}n$ or something like that i just can't find it anywhere on google.

-
Pls use titles that describe the problem –  leonbloy Jan 5 '13 at 18:35

This is a so-called stars-and-bars problem; the number that you want is

$$\binom{n+k-1}{n-1}=\binom{n+k-1}k\;.$$

The linked article has a reasonably good explanation of the reasoning behind the formula.

-
Thanks you're a lifesaver. –  mikey Jan 5 '13 at 18:36
@mikey: You’re welcome. –  Brian M. Scott Jan 5 '13 at 18:37

$\tbinom{k+n}{n}$ is close...but not quite right:

For any pair of natural numbers $n$ and $k$, the number of distinct n-tuples of non-negative integers whose sum is $k$ is given by the binomial coefficient:

$$\displaystyle\binom{n+k+1}{n - 1}= \binom{n + k - 1}{k},\quad \text{ where}\;\quad \binom{n+k-1}k\,=\,\frac{(n+k-1)\,!}{n\,!\,(k-1)\,!}\;$$

Your problem is a version of the classic "stars-and-bars problem" in combinatorics.

See Binomial Coefficient for more information on the very many ways the the binomial coefficient can be used, - when, why, and how it's appropriate for a problem like yours and many others!

-
This deserves a star! +1 –  Amzoti May 3 '13 at 2:18

The formula is:

$${n+k-1 \choose k}$$

Here's a proof:

Create a vector with $n$ ones and $k$ zeros, in no particular order. Each permutation of this vector is a solution to $x_1 + x_2 + x_3 + \cdots + x_k = n$. $x_1$ equals the number of ones to the left of the first zero, $x_2$ equals the number of ones between the first and second zeros, $x_3$ equals the number of ones between the second and third zeros, and so on, with the $x_i$ corresponding to the number of ones before the $(i-1)^{th}$ and $i^{th}$ zeros. There is a one-to-one correspondence between this permutation and $x_1 + x_2 + x_3 + \cdots + x_k = n$. There are $\dfrac{(n+k-1)!}{n!(k-1)!}$ permutations of such a vector, so hence the equation follows.

-