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$?

  • $\begingroup$ Yes, it is; see this article. $\endgroup$ – Brian M. Scott Mar 9 '13 at 23:44
  • $\begingroup$ The answer depends on whether the items (and the bins) are distinguishable or not. $\endgroup$ – leonbloy Mar 9 '13 at 23:50
  • $\begingroup$ @BrianM.Scott Is there any known article for efficiently generating all the solutions to the N-1 choose K-1 partitions? $\endgroup$ – Nakano Mar 10 '13 at 0:24
  • $\begingroup$ 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.) $\endgroup$ – Brian M. Scott Mar 10 '13 at 0:31
  • $\begingroup$ @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) $\endgroup$ – 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.


Your Answer

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

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