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.

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.

share|improve this question
1  
Pls use titles that describe the problem –  leonbloy Jan 5 '13 at 18:35

3 Answers 3

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.

share|improve this answer
    
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

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.

share|improve this answer

$\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!

share|improve this answer
    
This deserves a star! +1 –  Amzoti May 3 '13 at 2:18

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.