Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Have you tried it for $M=1$ and $M=2$? –  Phira Dec 7 '11 at 23:11

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
+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 at 21:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.