Supongamos el caso no trivial $k < l \cdot m$ . Cada contenedor puede recibir un máximo de $l$ bolas. Necesito distribuir $k$ bolas sobre $n$ contenedores para que algunos $m < n$ de los contenedores están ocupados (no necesariamente en su totalidad) y otros $(n-m)$ permanecen vacíos. ¿Cuántas formas existen de hacer esa distribución?
Respuesta
¿Demasiados anuncios?
En primer lugar, puede seleccionar las ubicaciones no vacías en $\binom{m}{n}$ maneras. Así que el problema que queda es averiguar cómo distribuir $k$ bolas entre $m$ contenedores ganan ninguno consiguiendo más de $l$ .
Por estrellas y barras hay $\binom{k - 1}{m - 1}$ maneras de distribuir $k$ bolas en $m$ papeleras sin ninguna vacía. Pero esto no tiene en cuenta los casos en los que algunas papeleras tienen más de $l$ bolas. Esto, a su vez, puede ser manejado por el principio de inclusión y exclusión considerando los diferentes conjuntos como las soluciones que violan 1, 2, ... de las restricciones. Digamos que el primer conjunto tiene más de $l$ bolas. Añadir $l$ bolas a la primera papelera, todavía hay que distribuir $k - l$ bolas entre todos $m$ cubos (llenando en exceso el cubo número 1) para que ningún cubo esté vacío, lo que puede hacerse en $\binom{k - l - 1}{m - 1}$ maneras. Pero el contenedor que viola la restricción puede ser seleccionado en $\binom{m}{1}$ maneras. En total, añadiendo el factor dado al principio: $$ \binom{n}{m} \sum_{j \ge 0} (-1)^j \binom{m}{j} \binom{k - j l - 1}{m - 1} $$
