6
$\begingroup$

What is the number of ways of distributing $N$ indistinguishable balls into $M$ bins such that at least one bin has at least $n$ balls in it?


My attempt:

The number of ways of of placing $N$ balls into $M$ bins is $\binom{N+M-1}{N}$.

I tried, by stars and bars, to calculate the number of ways of distributing $N$ indistinguishable balls into $M$ bins such that exactly one bin has exactly $n$ balls in it:

If the first or last bin contains the $n$ balls, we have used one partition, so there are $M-2$ left. This gives $2\binom{N-n+M-2}{N-n}$ ways.

If the second to $(M-1)$th bin contains the $n$ balls, we have used two partitions, which gives $(M-2)\binom{N-n+M-3}{N-n}$ ways.

So the total number of ways of distributing $N$ indistinguishable balls into $M$ bins such that exactly one bin has exactly $n$ balls in it is $$2\binom{N-n+M-2}{N-n}+(M-2)\binom{N-n+M-3}{N-n}.$$

Is this correct? It seems like a strange result.

Then I thought about simply summing this expression for $n$ going from $n$ to $N$, i.e.,

$$\sum_{k=n}^N 2\binom{N-k+M-2}{N-k}+(M-2)\binom{N-k+M-3}{N-k},$$

in order to obtain the expression for "at least $n$ balls," but I feel like this would be over-counting somehow.

And then there is the issue of "at least one bin," which I am rather blunted by.

Any help is much appreciated!

Note that I'm looking for a closed form solution to the problem in the yellow box. Thanks.

$\endgroup$
1
$\begingroup$

This is a fairly ugly problem; probably the most straightforward approach is the calculate the number of distributions that have fewer than $n$ balls in each bin and subtract that number from $\binom{N+M-1}N$. Unfortunately, there does not seem to be a closed form for the subsidiary problem. By a combination of stars and bars and inclusion-exclusion one can show that there are

$$\sum_i(-1)^i\binom{M}i\binom{N+M-1-in}{M-1}$$

of these ‘bad’ distributions.

Note that the $i=0$ term is $\binom{N+M-1}{M-1}=\binom{N+M-1}N$; the other terms from the inclusion-exclusion calculation get rid of the distributions that have more than $n$ balls in some bin. Thus, the answer to your question is actually just the negative of the some of the terms with $i>0$, i.e.,

$$\sum_{i=1}^M(-1)^{i+1}\binom{M}i\binom{N+M-1-in}{M-1}\;.$$

The inclusion-exclusion argument itself is pretty straightforward; I can give it in detail if you wish, though I’m not sure how useful the result is.

In this answer Marc van Leeuwen uses generating functions to deal with the more general problem in which each bin has its own upper limit, but he starts with the simpler case in which all of the limits equal, as in your question.

$\endgroup$
  • $\begingroup$ Thank you very much for your time! $\endgroup$ – Bobson Dugnutt Sep 7 '16 at 7:12
  • $\begingroup$ @Lovsovs: You’re very welcome! $\endgroup$ – Brian M. Scott Sep 7 '16 at 7:15
  • $\begingroup$ Hmm, there is something I don't understand: When I (in Mathematica) plot the ratio "the sum you found"/$\binom{N+M-1}{M-1}$ I always get $1$, even though I would expect to get something less than. What is going on you think? $\endgroup$ – Bobson Dugnutt Sep 7 '16 at 7:36
  • $\begingroup$ The bad distributions can be counted as the coefficient of $x^N$ in the expansion $(1+x+x^2+\cdots+x^{n-1})^M = (1-x^n)^M(1-x)^{-M}$ $\endgroup$ – user348749 Sep 7 '16 at 7:42
  • $\begingroup$ @Lovsovs: I don’t know; I’d have to play with it. I did just now spot and fix a small error, where I had $n+1$ instead of $n$, but if you were looking at a variety of values of $N,M$, and $n$, the error shouldn’t have made much difference in the overall pattern. It’s almost four in the morning here, and I’m about to head for bed, but I’ll take a look tomorrow. $\endgroup$ – Brian M. Scott Sep 7 '16 at 7:44
-1
$\begingroup$

Seems that it's not correct, since you going to have double counting for the case where cell 1 and cell 2 both have $n$ balls.

Try use inclusion-exclusion principle.

It's easy using the properties $p_i = \mathrm{The\space ith\space cell\space has\space at\space least\space n\space balls}$ to calculate $E(0)$ the case when no property holds. For $r$ different properties to hold, we want that $r$ specific cells will have at least $n$ balls we first put $n$ balls in each of them and then the rest $N - rn$ we split however we want, so we get: $$ w(p_{i_1},...,p_{i_r}) = {{N + M - rn - 1}\choose N - rn}$$ and with the number of ways to pick $r$ different properties and the fact that the properties are symmetric we get $$ w(r) = {M \choose r} \cdot {{N + M - rn - 1}\choose N - rn} $$

Now we have that $$E(0) = {{N+M-1}\choose{N}} - \sum_{r=1}^M (-1)^r\cdot w(r)$$

After calculating $E(0)$ use the fact that whats youre loking for is the complement of $E(0)$ which gives you that the desired number is: $${{N+M-1}\choose{N}} - E(0) = \sum_{r=1}^M (-1)^r\cdot w(r)$$

$\endgroup$
  • $\begingroup$ Thanks for the answer. I haven't had any experience with IE-principle, so it would be a great help if you could demonstrate how to use it on this problem. $\endgroup$ – Bobson Dugnutt Sep 6 '16 at 12:05
  • $\begingroup$ I edited my answer... try reading en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle if you still cant understand... $\endgroup$ – Snufsan Sep 6 '16 at 12:17
  • $\begingroup$ 1) Doesn't $r$ running from $1$ to $M$ (giving $N+M-Mn-1$ in the end) potentially give negative values in the binom-coeff.? For instance, what if $N=M$? 2) Should the final expression then be summed (as in the question) to answer the question in the yellow box? $\endgroup$ – Bobson Dugnutt Sep 6 '16 at 13:16
  • $\begingroup$ if the one of the terms is negative in the binomial coefficient then we usually define that in that case the coefficient is 0 $\endgroup$ – Snufsan Sep 6 '16 at 15:15

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.