Number of ways to place $n$ balls in $k$ bins where just the first $r$ bins have less than $m$ balls How many ways are there to distribute $n$ balls into $k$ bins where the first $r$ bins have less than $m$ balls (each) and the rest of the bins have more than $m$ (each)?
Given this solution for every bin has at least m balls, would it be a good start to sum the combinations of ($0$ balls for the less than bins)$\cdot$($n$ balls for the rest where each has at least $r$ balls)+...+($r\cdot m$ balls for the less than bins)$\cdot$($n-r\cdot m$ balls for the rest where each has at least $r$ balls)?
Every contribution is highly appreciated.
 A: I assume that your balls are identical.


*

*You can firstly put $m + 1$ balls into each of the last $k-r$ bins, since they have to have at least $m + 1$ balls each. Now you have to distribute $N=n - (m + 1)(k - r)$ balls among k bins, so that first $r$ bins have less than $m$ balls each, but you don't need to worry about the rest of them. Needless to say that if $N<0$, you have no solutions.

*Now for each $i$ so that $0 \leq i \leq N$ let's compute the number of ways to distribute these balls, so that $i$ balls are in the last $k-r$ bins, and $N - i$ balls are in the first $r$ bins, and each of the first $r$ bins has less than $m$ balls. We should obviously consider only those $i$ for which $N-i \leq r(m - 1)$.
2.1 The number of ways to put $i$ balls into the last $k-r$ bins is obviously ${i + k - r - 1 \choose i}$ - see this.
2.2 The number of ways of putting $N - i$ balls into the first $r$ bins is trickier (given the constraint). Let's denote it by $M^r_{N-i}$. It equals the coefficient of $x^{N-i}$ in the polynomial $(x^1 + x^2 + ... + x^{m-1})^r$ (see, for example, this)
2.3 For each i, therefore, the total number of ways is $M^r_{N-i} \cdot {i + k - r - 1 \choose i}$
--
So, in a nutshell:


*

*Compute $N=n - (m + 1)(k - r)$. If $N<0$, no solutions.

*Compute $p = \max(0, N - r(m - 1))$

*The answer is $\sum_{i = p}^{N}{M^r_{N-i} \cdot {i + k - r - 1 \choose i}}$


I don't think closed-form solution exists. Time complexity is very high (super-exponential), so even if you code it, it will only work for small numbers.
