$m$ bolas $n$ problema de probabilidad de las cajas

Question

Me encontré con este problema en mi clase de probabilidad, y no fuimos capaces de resolverlo, así que me gustaría saber la respuesta.

Si tiene $m$ bolas y $n$ cajas, con $n < m$ y se introducen las bolas en las cajas al azar, ¿cuál es la probabilidad de que todas las cajas tengan al menos una bola?

El problema no especifica si las bolas son distinguibles o no, así que puedes suponer cualquiera de las dos cosas, así que otra pregunta sería, si supones que son distinguibles ¿obtendrás la misma respuesta que suponiendo que no son distinguibles? (Esto sería genial porque creo que el caso no distinguible es más fácil).

Agradezco cualquier idea sobre el problema.

Answer 1

Esta respuesta considera que las bolas y las cajas son distinguibles, por lo que cada patrón tiene la misma probabilidad. Dudo que haya un experimento práctico para probar esto que no los distinga también.

El número de formas de poner $m$ bolas en $n$ cajas es $n^m$ ya que cada bola puede ir en cualquiera de las casillas.

El cálculo del número de formas de poner $m$ bolas en $n$ cajas en las que cada caja tiene al menos una bola es más complicado. Llamémoslo $A(m,n)$ . Si, al decidir qué hacer con la última bola, todas las demás casillas están llenas, entonces puede ir en cualquiera de las $n$ cajas; sin embargo, si uno de los $n$ cajas está vacía y las otras llenas, entonces debe ir en la vacía. Así que $$A(m,n) = n A(m-1,n) + n A(m-1,n-1)$$ y claramente $A(m,1) = 1$ (sólo hay un camino con una caja) y $A(m,n) = 0$ para $m<n$ . Resulta que $$A(m,n) = n! \, S_2 (m,n)$$ donde $S_2$ significa Números Stirling del segundo tipo ( OEIS A019538 ). $A(n,n)=n!$ como era de esperar.

Así que la probabilidad de que todas las cajas tengan al menos una bola es $$ \frac{n! \, S_2 (m,n)}{n^m}.$$

Por ejemplo, con 3 bolas y 2 cajas, esto da $\frac{2 \times 3}{8} = 3/4$ .

Answer 2

Sea S el número de formas de distribuir m bolas en n cajas sin ninguna restricción y T el número de formas de distribuir m bolas en n cajas con cada una de ellas con al menos una bola.

Si podemos calcular S y T, entonces la probabilidad de que todas las cajas tengan al menos una bola dentro es simplemente $\frac T S$ .

En primer lugar, contamos el número de formas de distribuir m bolas en n cajas sin ninguna restricción. En otras palabras, el número de soluciones a la ecuación:

$$x_1 + x_2 + x_3 + ... + x_n = m$$

Podemos calcularlo con: $S = {m+n-1 \choose n-1}$

En segundo lugar, contamos el número de formas de distribuir m bolas en n cajas, con la restricción de que todas las cajas tengan al menos 1 bola. En otras palabras, el número de soluciones a la ecuación:

$$x_1 + x_2 + x_3 + ... + x_n = m \textrm{ where } x_i >= 1 \textrm { for all } i = 1..n$$

Reformulemos esta segunda pregunta. Pongamos una sola bola en cada caja ( $x_i = y_i + 1$ ) y luego distribuir el otro $m-n$ bolas:

$$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) + ... + (y_n + 1) = m$$ $$y_1 + y_2 + y_3 + ... + y_n = m-n$$

Así que ahora, podemos calcular $T = {(m-n)+n-1 \choose n-1} = {m-1 \choose n-1}$

Por lo tanto, la probabilidad de que cada caja tenga al menos una bola es

$$ \frac T S = \frac {m-1 \choose n-1} {m+n-1 \choose n-1} = \frac {(m-1)!m!} {(m-n)!(m+n-1)!} $$