Si n personas entran a un salón a través de cualquiera de los n-puertas, ¿cuál es la probabilidad de que al menos una de las puertas no se utilizan?

Question

El problema es que tengo 2 en conflicto soluciones.

Solución 1:

Desde allí es $n$ de la gente que cada uno elija cualquiera de $n$ puertas, el número total de maneras en las $n$ de la gente entrar en la sala de es $n^n$. (correcto?)

luego he usado, $P($, una de las puertas no elegidas$)=1-P($todas las puertas escogido$)$

que (yo) implica un 1 a 1 adecuación de las personas a las puertas, lo cual sólo puede ocurrir en $n!$ formas (equivalente al número de arreglos de $n$ objetos).

es decir. $P($todas las puertas escogido$)=\dfrac{n!}{n^n}$

por lo que la probabilidad es $1-\dfrac{n!}{n^n}$

Solución 2:

Considerar todos los casos en que, al menos, $1$ puerta no se utiliza:

Si $n$ a las personas a entrar a través de $1$ puerta no es $1^n=1$ arreglos

Si $n$ a las personas a entrar a través de $2$ puertas del es $2^n$ arreglos

Si $n$ a las personas a entrar a través de $3$ puertas del es $3^n$ arreglos

...

Si $n-1$ a las personas a entrar a través de $n-1$ puertas del es $(n-1)^n$ arreglos

(Nota: $n$ no puede entrar a través de todos los $n$ puertas o requiere la condición no se cumple)

En esta formulación la necesaria probabilidad está dada por $\dfrac{1^n+2^n+3^n+...+(n-1)^n}{n^n}$

Así que la solución (si) es la correcta?

Answer 1

Hay, como usted dice, $n^n$ formas para $n$ a las personas a entrar en la sala, y $n!$ de esas formas que uso todos los $n$ puertas, por lo que el número de maneras que dejar al menos una de las puertas sin usar es $n^n-n!$. Si todos los $n^n$ posibilidades son igualmente probables, la probabilidad de que al menos una de las puertas que quedan sin usar es de hecho $1-\dfrac{n!}{n^n}$.

El problema también puede ser trabajado por la inclusión-exclusión, que es una versión correcta de lo que estaban tratando de hacer con su segunda solución. Para cada una de las $n$ puertas hay $(n-1)^n$ formas de la $n$ a las personas a entrar en la sala sin el uso de esa puerta, por lo que en una primera aproximación no se $n(n-1)^n$ maneras para que al menos una puerta a quedar sin usar. Sin embargo, de alguna manera que las hojas de dos puertas sin usar son contados dos veces, así que tenemos que restar el extra de contar. Hay $\binom{n}2$ pares de puertas, y hay $(n-2)^n$ formas para un determinado par de divisas a ser utilizados, así tenemos que restar $\binom{n}2(n-2)^n$, al pasar $$n(n-1)^n-\binom{n}2(n-2)^n$$ as a second approximation. This requires further correction for the ways that leave three doors unused, and so on all the way to those that leave $n-1$ de las puertas sin usar. El resultado final es

$$\sum_{k=1}^{n-1}(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=1}^{n-1}(-1)^{n-1-k}\binom{n}kk^n\;.$$

Answer 2

La primera solución es correcta. Contando incluso las formas en que $n$ a las personas a entrar a través de dos puertas no es tan simple como su Solución de $2$ indica. El $2$ puertas puede ser elegido en $\binom{n}{2}$ maneras. Ahora, permita que cada persona elija uno de estos dos puertas. Esto se puede hacer en $2^n$ maneras. Pero $2$ de estas maneras de involucrar a todo el mundo la elección de la misma puerta. Así que terminamos con $$\binom{n}{2}\left(2^n-2 \right)$$ maneras. Para $k$ puertas, nos metemos en la misma manera que$\binom{n}{k}$$k^n$, pero la eliminación de los casos en menos de $k$ puertas eran en realidad elegido se complica.