# 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

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$.