Sign up ×
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|cite|improve this question
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

2 Answers 2

up vote 12 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|cite|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 '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
See also Balls In Bins With Limited Capacities. – 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$.

share|cite|improve this answer
Why don't you write down the solution more explicitly? – Babai Mar 16 at 8:35

Your Answer


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.