18
$\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, 2011 at 23:11
  • $\begingroup$ @mayhewsw the link appears to be broken. $\endgroup$
    – naktinis
    Oct 1, 2018 at 12:04
  • $\begingroup$ Thanks @naktinis. Fixed link: complete derivation here. $\endgroup$
    – mayhewsw
    Oct 2, 2018 at 13:22

3 Answers 3

16
$\begingroup$

As a check I did it with an inclusion-exclusion argument, getting

$$\sum_{i=0}^{\left\lfloor\frac{n}{m+1}\right\rfloor}(-1)^i\binom{k}i\binom{n+k-1-i(m+1)}{k-1}\,.\tag{1}$$

The nature of the inclusion-exclusion argument is such that $\binom{k}i\binom{n+k-1-i(m+1)}{k-1}$ is the number of ways to distribute the $n$ balls so that at least $i$ of the $k$ bins have more than $m$ balls. In that case some $i$ bins contain altogether at least $i(m+1)$ balls, so clearly we must have $i(m+1)\le n$, i.e., $i\le\left\lfloor\frac{n}{m+1}\right\rfloor$ (since $i$ is an integer).

Clearly it is also the case that $i$ cannot exceed $k$, but we don’t take explicit note of that in the upper limit of the summation $(1)$, because any term with $i>k$ has a factor $\binom{k}i=0$ anyway. One could make this explicit by writing the upper limit as $\min\left\{k,\left\lfloor\frac{n}{m+1}\right\rfloor\right\}$, but it is not necessary to do so.

Setting $r=i$ and $r_2=n-i(m+1)$ to match your notation, I make this

$$\sum_{r=0}^{\left\lfloor\frac{n}{m+1}\right\rfloor}(-1)^r\binom{k}r\binom{k+r_2-1}{r_2}\,.$$

It appears that you’ve the wrong exponent on $-1$.

$\endgroup$
11
  • 2
    $\begingroup$ +1. Charalambides's Enumerative Combinatorics (Exercise 9.6, p. 360) gives the same expression. $\endgroup$ Dec 7, 2011 at 23:39
  • 4
    $\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$ Feb 3, 2014 at 21:20
  • 3
    $\begingroup$ See also Balls In Bins With Limited Capacities. $\endgroup$
    – joriki
    Oct 3, 2015 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$ Mar 6, 2019 at 9:55
  • 1
    $\begingroup$ @QuantumMechanic: I thought about it but decided that I preferred the simpler expression. I also like to reinforce the fact that $\binom{n}k$ makes sense for all non-negative integers $k$, since students often seem predisposed to assume that $k$ must satisfy $0\le k\le n$. $\endgroup$ Jan 21 at 23:06
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, 2015 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$ May 16, 2017 at 4:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .