I apologize if this question does not make sense.

I have $k$ bins and $n$ balls. $m$ represents the size of the smallest bin in terms of how many balls it contains.

For example if I have five bins and balls distributed as such: 2,3,5,2,4: $m$ here is 2.

So based on having $n$ balls and $k$ bins with a minimum bin size of $m$, how many ways are there to arrange this?

  • $\begingroup$ BTW, in your title, "at least one bin of minimum m balls" should be "every bin having a minimum of m balls". $\endgroup$ – ShreevatsaR Oct 14 '12 at 19:15
  • $\begingroup$ @ShreevatsaR But that is not what I am asking, technically. I am saying that m is the size of the smallest bin in the arrangement. $\endgroup$ – MyNameIsKhan Oct 14 '12 at 19:21
  • $\begingroup$ Ah ok, do you mean "at least one bin has exactly m balls, and this is the minimum"? $\endgroup$ – ShreevatsaR Oct 14 '12 at 19:23
  • $\begingroup$ @ShreevatsaR Correct $\endgroup$ – MyNameIsKhan Oct 14 '12 at 19:23

I assume from your example that the balls are indistinguishable, but the bins are not.

Let us first answer the question for "every bin has at least $m$ balls": Since each of the $k$ bins must have at least $m$ balls, we can remove $m$ balls from each bin: after removing these $mk$ balls, what we are left with is a distribution of $n - mk$ balls into $k$ bins, with any sort of distribution allowed. (Equivalently, we want the number of integer solutions to $y_1 + \dots y_k = n$ where each $y \ge m$; we can set $x_i = y_i - m$ and ask for nonnegative solutions to $x_1 + \dots + x_k = n - mk$ instead.)

The number of ways of distributing $(n-mk)$ balls into $k$ bins, or the number of nonnegative integer solutions to $x_1 + \dots + x_k = n - mk$, is $$\binom{n-mk+k-1}{k-1}$$ (see "stars and bars"), so that is the answer to our question (every bin having at least $m$ balls).

Now to your question, that the minimum number of balls among all bins is exactly $m$ (rather than at least $m$). This precisely means that:

  • every bin has at least $m$ balls
  • not every bin has at least $m+1$ balls

So we just subtract the number of solutions where every bin has at least $m + 1$ balls as above, getting the answer:

$$\binom{n-mk+k-1}{k-1} - \binom{n-mk-1}{k-1}$$

  • $\begingroup$ Sorry to Shreevatsa for my seeming similar answer, but I was still typing... Note that the OP wants to have $m$ actually be the minimum, so that there's a bit extra to do... $\endgroup$ – coffeemath Oct 14 '12 at 19:19
  • $\begingroup$ @ShreevatsaR: I think it's sufficiently clear from the question, especially in conjunction with the title, that your second interpretation is the intended one. $\endgroup$ – joriki Oct 14 '12 at 19:20
  • $\begingroup$ @coffeemath: Thanks to you and joriki and the OP for making that clear; fixed now. $\endgroup$ – ShreevatsaR Oct 14 '12 at 19:27

Let there be $x_i$ balls in bin $i$ where $i=1...k$. The total number of balls being $n$ means that


Since each $x_i>=m$ you may define $y_i=x_i-m$ and have $y_i>=0$, and also

[1] $y_1+y_2+...+y_k=n-mk.$

Now you want at least one of these $y_k$ to be $0$, which complicates the count. That is, there is a standard formula for the number of solutions to [1] if you just require nonnegative $y_i$, but requiring at least one of them to be zero may be harder.

Maybe an approch based on the fact that "at least one being 0" is the complement of "all being at least 1" will help.


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.