# Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin

The number of ways to put $n$ unlabeled balls in $k$ distinct bins is $$\binom{n+k-1}{k-1} .$$ Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a max of $m$ balls.

EDIT: What I've tried:

I got to the generating function $$(1-x^{m+1})^k(1-x)^{-k}$$ which ends up giving me $$\sum_{r(m+1)+r_2=n} \binom{k}{r}(-1)^{r_2}\binom{k+r_2-1}{r_2}$$

But when programing this:

def distribute_max(total,buckets,mmax):
ret = 0
for r in xrange(total//(mmax+1)+1):
r_2 = total - r*(mmax+1)
ret += choose(buckets,r) * (-1)**r_2 * choose(buckets + r_2 - 1,r_2)
return ret


I'm getting terribly wrong answers. Not sure which step I screwed up.

-
Have you tried it for $M=1$ and $M=2$? – Phira Dec 7 '11 at 23:11
For what it's worth, I have a complete derivation of the above problem here. – mayhewsw Oct 23 '14 at 18:40

As a check I did it with an inclusion-exclusion argument, getting $$\sum_i(-1)^i\binom{k}i\binom{n+k-1-i(m+1)}{k-1}\,.$$

Setting $r=i$ and $r_2=n-i(m+1)$ to match your notation, I make this $$\sum_r (-1)^r\binom{k}r\binom{k+r_2-1}{r_2}\,.$$ It appears that you’ve the wrong exponent on $-1$.

-
+1. Charalambides's Enumerative Combinatorics (Exercise 9.6, p. 360) gives the same expression. – Mike Spivey Dec 7 '11 at 23:39
@Brian What are the sum limits in your formula? The expression from book Enumerative Combinatorics (p. $360$) is $L(n,k,m)=\sum_{j=0}^k (-1)^j C_k^j C_{k+n-j(m+1)-1}^{k-1}$ according to your notation, where $C_k^j$ means the binomial coefficient. Unfortunately, $L(n,k,m)=0$ for any $n \leq k \cdot m$ (Mathematica' showed me that). Somewhere the mistake lives. Can you kindly help me with this problem? – Piotr Semenov Feb 3 '14 at 21:20
@PiotrSemenov: I had a slightly different way of getting to the problem, but I have sum limits on my sums. See it here. – mayhewsw Oct 23 '14 at 18:43
– joriki Oct 3 at 7:10

Let's denote the problem as $D(n,k,m)$, then when $mk-n \leq m$, the answer can be given as: $D(n,k,m)=\binom{km-n+k-1}{k-1}$, where $m \leq n$.

It can be easily verified using $D(5,2,3)=2$, or $D(6,3,3)=10$, etc..

Let me try to explain it in more details with my poor English (sorry for that).

Suppose we start from the state that all bins are filled with $m$ balls in each. Then the task for us is to eliminate $mk-n$ balls from these $k$ bins. To ditribute the $mk-n$ "elimination" into $k$ bins, we have $\binom{km-n+k-1}{k-1}$ different ways if $mk-n \leq m$, i.e. the number of elimination in each bin will not exceed $m$.

-
Why don't you write down the solution more explicitly? – Babai Mar 16 at 8:35