# Number of ways to place $N$ items in $K$ bins where each bin has at least $1$ item?

What is the combinatoric describing the number of ways to place $N$ items in $K$ bins where each bin has at least $1$ item? Is it just $N-1$ choose $K-1$?

• Yes, it is; see this article. – Brian M. Scott Mar 9 '13 at 23:44
• The answer depends on whether the items (and the bins) are distinguishable or not. – leonbloy Mar 9 '13 at 23:50
• @BrianM.Scott Is there any known article for efficiently generating all the solutions to the N-1 choose K-1 partitions? – Nakano Mar 10 '13 at 0:24
• I don’t know how efficient it is, but the first thing that occurs to me is a recursive algorithm that for $i=1$ to $N-K+1$ generates the solutions with $i$ items in the last bin. (Note that because of your mentioning the expression $\binom{N-1}{K-1}$, I’ve assumed that the bins are distinguishable and the items are not.) – Brian M. Scott Mar 10 '13 at 0:31
• @BrianM.Scott In my case I am trying to find the number of ways to split up a number N into three factors based on its prime factorization (e.g. 150 = 2*3*5*5) – Nakano Mar 10 '13 at 0:33

We know the number of nonnegative solutions to $x_1+x_2+\cdots+x_K=N$ is
$(N+K-1)!/N!(K-1)!$ If you want $x_i \geq 1$ for all i. Then we can set $x_i=y_i+1$, with $y_i \geq 0$
and count the number of nonnegative solutions to $(y_1+1)+(y_2+1)+\cdots+(y_K+1)=N$; that is,
$y_1+y_2+\cdots+y_K=N-K$. Thus, we get $(N-1)!/(K-1)!(N-K)!$ which is indeed N-1 choose K-1.