16
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Have you tried it for $M=1$ and $M=2$? $\endgroup$ – Phira Dec 7 '11 at 23:11
  • $\begingroup$ @mayhewsw the link appears to be broken. $\endgroup$ – naktinis Oct 1 '18 at 12:04
  • $\begingroup$ Thanks @naktinis. Fixed link: complete derivation here. $\endgroup$ – mayhewsw Oct 2 '18 at 13:22
15
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ +1. Charalambides's Enumerative Combinatorics (Exercise 9.6, p. 360) gives the same expression. $\endgroup$ – Mike Spivey Dec 7 '11 at 23:39
  • 3
    $\begingroup$ @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? $\endgroup$ – Piotr Semenov Feb 3 '14 at 21:20
  • 2
    $\begingroup$ See also Balls In Bins With Limited Capacities. $\endgroup$ – joriki Oct 3 '15 at 7:10
  • 1
    $\begingroup$ It seems to me that in order to make this work without failing one should have $0\le k\le \frac n{m+1}$. $\endgroup$ – Miles Eagle Mar 6 '19 at 9:55
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Why don't you write down the solution more explicitly? $\endgroup$ – Babai Mar 16 '15 at 8:35
1
$\begingroup$

The number of ways to put $n$ balls in $k$ boxes with in each box a maximum of $m$ balls is the coefficient of $[q^n]$ in the $\text{QBinomial}(k+m,k,q)$.

For example, the number of different ways to put $n = 5$ balls in $k = 4$ boxes with in each box no more than $m = 3$ balls is given by
$$ \text{QBinomial}(7,4,q) = (q^6+q^5+q^4+q^3+q^2+q+1)(q^2-q+1)(q^4+q^3+q^2+q+1) = q^{12}+q^{11}+2q^{10}+3q^9+4q^8+4q^7+5q^6+4q^5+4q^4+3q^3+2q^2+q+1. $$ The coefficient of $q^5$ is $4$. Hence there are four ways. These four ways are $(2,3)$, $(1,1,3)$, $(1,2,2)$, $(1,1,1,2)$.

$\endgroup$
1
  • $\begingroup$ The boxes are distinct, so there are 40 ways for the n=5,k=4,m=3 example. In particular, 12 each for (2,3), (1,1,3) and (1,2,2), and 4 for (1,1,1,2). The code in the question, with the correction from the accepted answer, gives 40. $\endgroup$ – Evgeni Sergeev May 16 '17 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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