¿Número de formas de distribución de bolas de $N$ $M$ contenedores tal que al menos un bin tiene por lo menos $n$ bolas en ella?

Question

¿Cuál es el número de formas de distribución de los $N$ indistinguibles de las pelotas en $M$ papeleras de tal manera que al menos uno de bin tiene al menos $n$ bolas en ella?

---

Mi intento:

El número de maneras de colocar $N$ bolas en $M$ papeleras es $\binom{N+M-1}{N}$.

He intentado, por las estrellas y las barras, para calcular el número de formas de distribución de los $N$ indistinguibles de las pelotas en $M$ papeleras tal de que exactamente uno de bin tiene exactamente $n$ bolas de:

Si el primer o el último bin contiene el $n$ bolas, hemos utilizado una partición, por lo que hay $M-2$ a la izquierda. Esto le da a $2\binom{N-n+M-2}{N-n}$ maneras.

Si el segundo a $(M-1)$th bin contiene el $n$ bolas, hemos utilizado dos particiones, lo que da $(M-2)\binom{N-n+M-3}{N-n}$ maneras.

Por lo que el número total de formas de distribución de los $N$ indistinguibles de las pelotas en $M$ papeleras tal de que exactamente uno de bin tiene exactamente $n$ bolas en es $$2\binom{N-n+M-2}{N-n}+(M-2)\binom{N-n+M-3}{N-n}.$$

Es esto correcto? Parece un resultado extraño.

Entonces pensé que simplemente sumar esta expresión para$n$, al pasar de $n$$N$, es decir,

$$\sum_{k=n}^N 2\binom{N-k+M-2}{N-k}+(M-2)\binom{N-k+M-3}{N-k},$$

con el fin de obtener la expresión "al menos $n$ bolas," pero siento que esta sería largo de contar, de alguna manera.

Y luego está el tema de "al menos un bin," que yo soy más bien anulado por el.

Cualquier ayuda se agradece mucho!

Tenga en cuenta que estoy buscando una forma cerrada de la solución al problema en la caja amarilla. Gracias.

Answer 1

Esto es bastante feo problema; probablemente el enfoque más sencillo es el de calcular el número de distribuciones que tienen menos de $n$ bolas en cada bin y restar ese número de $\binom{N+M-1}N$. Por desgracia, no parece ser una forma cerrada para la filial problema. Por una combinación de estrellas y barras y la inclusión-exclusión se puede demostrar que hay

$$\sum_i(-1)^i\binom{M}i\binom{N+M-1-in}{M-1}$$

de estos 'malos' de las distribuciones.

Tenga en cuenta que el $i=0$ plazo es $\binom{N+M-1}{M-1}=\binom{N+M-1}N$; los demás términos de la inclusión-exclusión en el cálculo de deshacerse de las distribuciones que tienen más de $n$ bolas en algunos de reciclaje. Por lo tanto, la respuesta a tu pregunta en realidad es sólo la negativa de algunos de los términos con $i>0$, es decir,

$$\sum_{i=1}^M(-1)^{i+1}\binom{M}i\binom{N+M-1-in}{M-1}\;.$$

La inclusión-exclusión en el argumento en sí es bastante sencillo, puedo dar en detalle si lo desea, aunque no estoy seguro de lo útil que es el resultado.

En esta respuesta Marc van Leeuwen utiliza funciones de generación para lidiar con el problema más general en el que cada contenedor tiene su propio límite superior, pero él comienza con el caso más sencillo en el que todos los límites de la igualdad, como en tu pregunta.

Answer 2

Parece que no es correcto, ya que va a tener el doble cómputo para el caso de que la celda 1 celda y de 2 ambos tienen $n$ bolas.

Trate de usar la inclusión-exclusión principio.

Es fácil usando las propiedades de $p_i = \mathrm{The\space ith\space cell\space has\space at\space least\space n\space balls}$ para calcular el $E(0)$ el caso cuando no posee propiedad. Para $r$ propiedades diferentes a celebrar, queremos que $r$ de las células específicas que tendrá, al menos, $n$ bolas primero ponemos $n$ bolas en cada uno de ellos y a continuación el resto $N - rn$ nos separamos sin embargo queremos, por lo que tenemos: $$ w(p_{i_1},...,p_{i_r}) = {{N + M - rn - 1}\choose N - rn}$$ and with the number of ways to pick $r$ different properties and the fact that the properties are symmetric we get $$ w(r) = {M \choose r} \cdot {{N + M - rn - 1}\choose N - rn} $$

Ahora tenemos que $$E(0) = {{N+M-1}\choose{N}} - \sum_{r=1}^M (-1)^r\cdot w(r)$$

Después de calcular los $E(0)$ utiliza el hecho de que whats youre loking es el complemento de a$E(0)$, lo que le da a usted que el número deseado es: $${{N+M-1}\choose{N}} - E(0) = \sum_{r=1}^M (-1)^r\cdot w(r)$$