let's say I have k empty slots and N different sources to fill these spots.

A source can put as many elements in the slots as possible (from 0 to k), and all slots have to filled

How many different possibilities are there of filling all the slots? For instance such a combination would be : for k = 5, N = 3, 3 comes from source 1, 2 from source 2, 0 from source 3. The problem is simple for N=1,2,3 but I can't find a simple formula to express this number.

Is it a very well known formula that I'm missing? thanks

  • 3
    $\begingroup$ If I understand you correctly then sources "have a name" but slots doesn't "have a name". This problem is equivalent to the problem of counting the number of non-negative integer solutions to the equation $x_1+x_2+\cdots+x_N=k$. I don't remember the name of this problem but its' solution is $\binom{N+k-1}{k}$. $\endgroup$ – Ido Feb 28 '13 at 15:40
  • $\begingroup$ Look at Wikipedia under "Stars and Bars." Add something like combinatorics to the search term so it will not tell you about flags. $\endgroup$ – André Nicolas Feb 28 '13 at 17:12
  • $\begingroup$ Since I have the URL on speed-dial, so to speak: stars-and-bars. $\endgroup$ – Brian M. Scott Feb 28 '13 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.