Distintas bolas y urnas distícitas con restricción máxima

Question

Estoy buscando un poco de ayuda con una expresión general. Estoy tratando de poner$k$ bolas distintas en$n$ urnas distintas, pero cada urna solo puede contener hasta$c$ bolas, con$cn \geq k$.

Sé que hay$n^k$ permutaciones, pero ¿cómo hago cumplir la restricción?

Answer 1

La cantidad de formas de poner$k$ bolas en$n$ bins donde cada contenedor solo puede contener hasta$c$ bolas es el coeficiente de$z^k$ en$n^{\text{th}}$ power de la función de generación ordinaria$1+x+\dots+x^c$, es decir,$$[z^k]\left(\sum_{i=0}^c z^i\right)^n.$ $ La serie geométrica finita es equivalente a$\frac{1-z^{c+1}}{1-z}$. Expandiendo el numerador con el teorema binomial, esto es equivalente a$$[z^k]\frac{\sum_{i=0}^n\binom ni(-1)^i z^{i(c+1)}}{(1-z)^n}.$ $ La función generadora para el denominador es$\sum_{i\ge0}\binom{n-1+i}{n-1}z^i$. Al multiplicarlos, se obtiene una fórmula explícita para el recuento deseado, es decir,$$\sum_{i=0}^n \binom ni(-1)^i\binom{n-1+k-i(c+1)}{n-1}.$ $

Answer 2

Supongo por "distintas" significa distinguir.

En ese caso, es el resultado deseado si se permitieron que los contenedores vacíos

$\text{balls}! \left[z^{\text{balls}}\right] \left(\sum _{k=0}^{\text{capacity}} \frac{z^k}{k!}\right){}^{\text{bins}}$

y si no se permitieron que ningún contenedores vacíos

$\text{balls}! \left[z^{\text{balls}}\right] \left(\sum _{k=1}^{\text{capacity}} \frac{z^k}{k!}\right){}^{\text{bins}}$

En ambos, $\left[z^{\text{balls}}\right]$ es la extracción del coeficiente, por ejemplo, el coeficiente de $z$ % exponente $balls$en los siguientes factores.