distinguible bolas distinguibles cuadros donde cada caja contiene al menos 2 bolas

Question

Considere la posibilidad de $m$ distinguibles bolas y $n$ distinguibles cajas donde $m > n$ (las cajas y bolas ya son distinguibles, dicen que vienen con preasignada distintas etiquetas).

De cuántas maneras existen para distribuir las bolas en las cajas de tal manera que cada caja contiene al menos $2$ pelotas?

Answer 1

Vamos a resolver el caso de las cajas indistinguibles y distinguibles los cuadros. La combinatoria de las especies en el primer caso es

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

que le da el EGF

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

La extracción de los coeficientes obtenemos

$$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\elegir k} (\exp(z)-1)^k (-1)^{n-k} z^{n-k} \\ = \frac{m.}{n!} \sum_{k=0}^n {n\elegir k} [z^{m+k-n}] (\exp(z)-1)^k (-1)^{n-k} \\ = \frac{m.}{n!} \sum_{k=0}^n {n\elegir k} (-1)^{n-k} \times \frac{k!}{(m+k-n)!} {m+k-n\llave k} \\ = {m\elegir n} \sum_{k=0}^n {n\elegir k} (-1)^{n-k} \times \frac{k! (m-n)!}{(m+k-n)!} {m+k-n\llave k} \\ = {m\elegir n} \sum_{k=0}^n {n\elegir k} (-1)^{n-k} \times {m+k-n\llave k} {m+k-n\elegir k}^{-1}.$$

Podemos verificar esto para algunos valores especiales como $m=2n$ donde obtenemos

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

cual es el valor correcto. También conseguimos

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

lo cual es correcto así. Un ejemplo más es

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

Finalmente observar que podemos obtener los valores de cajas distinguibles por multiplicando por $n!$ debido a que la especie se convierte ahora en el

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

Answer 2

Supongamos que la respuesta es $f(m,n)$.

Empezar con $f(0,0)=1$$f(m,0)=0$$m \gt 0$. Claramente $f(m,n)=0$ si $m \lt 2n$.

Ahora teniendo en cuenta el número de bolas $j$ en el primer cuadro, se tiene la expresión $$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)$$