Number of ways of distributing $N$ balls into $M$ bins such that at least one bin has at least $n$ balls in it? 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.
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&gt;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.
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)$$