5
$\begingroup$

Consider $m$ distinguishable balls and $n$ distinguishable boxes where $m > n$ (the boxes and balls are already distinguishable, say they come with preassigned distinct labels).

How many ways are there to distribute the balls into boxes such that each box contains at least $2$ balls?

$\endgroup$
  • $\begingroup$ This is related question handling specific case $m=8$ and $n=3$. The special case on its own is allready quite complicated, and I do not have much hope for a general solution :(. Let's hope I am wrong in this. Apart from this: $m\geq2n$ is of course needed to have at least one solution. $\endgroup$ – drhab Oct 11 '16 at 7:52
2
$\begingroup$

We solve the case of indistinguishable boxes and distinguishable boxes. The combinatorial species in the first case is

$$\mathfrak{P}_{=n}(\mathfrak{P}_{\ge 2}(\mathcal{Z}))$$

which gives the EGF

$$G(z) = \frac{(\exp(z)-z-1)^n}{n!}.$$

Extracting coefficients we get

$$m! [z^m] G(z) = m! [z^m] \frac{(\exp(z)-z-1)^n}{n!} \\ = \frac{m!}{n!} [z^m] \sum_{k=0}^n {n\choose k} (\exp(z)-1)^k (-1)^{n-k} z^{n-k} \\ = \frac{m!}{n!} \sum_{k=0}^n {n\choose k} [z^{m+k-n}] (\exp(z)-1)^k (-1)^{n-k} \\ = \frac{m!}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} \times \frac{k!}{(m+k-n)!} {m+k-n\brace k} \\ = {m\choose n} \sum_{k=0}^n {n\choose k} (-1)^{n-k} \times \frac{k! (m-n)!}{(m+k-n)!} {m+k-n\brace k} \\ = {m\choose n} \sum_{k=0}^n {n\choose k} (-1)^{n-k} \times {m+k-n\brace k} {m+k-n\choose k}^{-1}.$$

We can verify this for some special values like $m=2n$ where we obtain

$$(2n)! [z^{2n}] \frac{(\exp(z)-z-1)^n}{n!} \\ = (2n)! \frac{1}{n!} \frac{1}{2^n} = \frac{1}{n!} {2n\choose 2,2,2,\ldots,2}$$

which is the correct value. We also get

$$(2n+1)! [z^{2n+1}] \frac{(\exp(z)-z-1)^n}{n!} = (2n+1)! \frac{1}{n!} {n\choose 1} \frac{1}{6} \frac{1}{2^{n-1}} \\ = \frac{1}{(n-1)!} {2n+1\choose 2,2,2,\ldots,2,3}$$

which is correct as well. One more example is

$$(2n+2)! [z^{2n+2}] \frac{(\exp(z)-z-1)^n}{n!} \\ = (2n+2)! \frac{1}{n!} \left({n\choose 1} \frac{1}{24} \frac{1}{2^{n-1}} + {n\choose 2} \frac{1}{6^2} \frac{1}{2^{n-2}}\right) \\= \frac{1}{(n-1)!} {2n+2\choose 2,2,2,\ldots,2,4} + \frac{1}{2} \frac{1}{(n-2)!} {2n+2\choose 2,2,2,\ldots 2,3,3}.$$

Finally observe that we get the values for distinguishable boxes by multiplying by $n!$ because the species now becomes

$$\mathfrak{S}_{=n}(\mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

$\endgroup$
  • $\begingroup$ Nice answer! (+1) $\endgroup$ – Markus Scheuer Oct 12 '16 at 5:25
1
$\begingroup$

Let's suppose the answer is $f(m,n)$.

Start with $f(0,0)=1$ and $f(m,0)=0$ for $m \gt 0$. Clearly $f(m,n)=0$ if $m \lt 2n$.

Now by considering the number of balls $j$ in the first box, you have the expression $$f(m,n) = \sum_{j=2}^{m-2n+2} {m \choose j} f(m-j,n-1)$$

I think this gives the following values for small $m$ and $n$

 [m,n] [,1]  [,2]     [,3]       [,4]        [,5]         [,6]         [,7]        [,8]
 [1,]    0     0        0          0           0            0            0           0
 [2,]    1     0        0          0           0            0            0           0
 [3,]    1     0        0          0           0            0            0           0
 [4,]    1     6        0          0           0            0            0           0
 [5,]    1    20        0          0           0            0            0           0
 [6,]    1    50       90          0           0            0            0           0
 [7,]    1   112      630          0           0            0            0           0
 [8,]    1   238     2940       2520           0            0            0           0
 [9,]    1   492    11508      30240           0            0            0           0
[10,]    1  1002    40950     226800      113400            0            0           0
[11,]    1  2024   137610    1367520     2079000            0            0           0
[12,]    1  4070   445896    7271880    22869000      7484400            0           0
[13,]    1  8164  1410552   35692800   196396200    194594400            0           0
[14,]    1 16354  4390386  165957792  1454653200   2951348400    681080400           0
[15,]    1 32736 13514046  742822080  9771762000  34205371200  23837814000           0
[16,]    1 65502 41278068 3234711480 61305644400 336151015200 476756280000 81729648000

Having done the calculations, it is then possible to look the values up to see if anybody else has done something similar. It turns out this is OEIS A200091, which gives alternative formulae and generating functions. In particular it gives the equivalent of $$f(m,n) = n\,f(m-1,n) + (m-1)\,n\,f(m-2,n-1)$$

$\endgroup$

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.