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.

Possible Duplicate:
Unique ways to keep N balls into K Boxes?

Number of ways to put N items into K bins with at least 1 per bin?

I know that normally you can do N + K + 1 choose K - 1 or something like that, but that allows for bins where nothing is placed inside. What about when there must be at least 1 item per bin?

share|improve this question

marked as duplicate by Cameron Buie, Gerry Myerson, Marvis, J. M., Zev Chonoles Jul 12 '12 at 3:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
Are the items indistinguishable and the boxes distinguishable? Are they both indistinguishable? Both distinguishable? –  Arturo Magidin Jul 10 '12 at 23:53
    
@ArturoMagidin: I'm not sure... 7 and 3 yield 4, so I think order does not matter on both counts (all indistinguishable) –  MyNameIsKhan Jul 11 '12 at 0:56
add comment

2 Answers

It's actually $\binom {n+k-1}{k-1}$ for the first problem.

If you want to ensure that every bin has at least one element, then take $n-k$ items and put them in $k$ bins as in the first prpblem, then add one item to each bin.

share|improve this answer
    
So n-k+1 choose k+1 –  MyNameIsKhan Jul 10 '12 at 21:43
add comment

I am assuming that the $N$ items are identical. Line up the $N$ items in a row, with a little gap between the items. Choose $K-1$ of the gaps to put separators into. Put all the items from the left end to the first separator into Bin $1$, everything from the first separator to the second into Bin $2$, and so on.

Every choice of where to put the separators gives you a distribution into bins, with at least one per bin. And every distribution into bins with at least one per bin tells you where to put the separators.

So there are $\binom{N-1}{K-1}$ ways to do the job.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.