Como ha señalado André Nicolas, se trata del clásico problema del recuento de las derivaciones. He aquí una posible solución.
Dejemos que $A_N$ sea el número de formas de asignar el $N$ bolas a la $N$ cajas de manera que ninguna de las bolas vuelva a la caja de la que salió. Escribamos $i \to j$ si la pelota $i$ entra en la caja $j$ . En primer lugar, para algunos $j \in 2, \ldots, N$ tenemos $1 \to j$ . Esto puede hacerse en $N - 1$ formas. Ahora distinguimos dos casos.
-
Si $j \to 1$ entonces tenemos $N - 2$ bolas $2, \ldots, j-1, j+1, \ldots, N$ izquierda, y exactamente el $N - 2$ cajas $2, \ldots, j-1, j+1, \ldots, N$ de la que proceden. Así que las bolas restantes se pueden asignar en $A_{N - 2}$ formas.
-
Si $j \not\to 1$ Entonces nos quedamos con $N - 1$ bolas $2, \ldots, j-1, j, j+1, \ldots, N$ que no pueden ir en las cajas $2, \ldots, j-1, 1, j+1, \ldots, N$ respectivamente. Por lo tanto, las bolas restantes se pueden asignar en $A_{N-1}$ formas.
Dado que hay $N-1$ formas de elegir $j$ obtenemos la relación de recurrencia
$$A_N = (N-1) A_{N-2} + (N-1) A_{N-1}$$
Esta es exactamente la misma relación de recurrencia que la relación de recurrencia de la función factorial $N! = N \cdot (N-1) \cdot \ldots \cdot 2 \cdot 1$ . Sin embargo, para la función factorial tenemos $0! = 1$ y $1! = 1$ mientras que nosotros tenemos $A_0 = 1$ y $A_1 = 0$ . Por lo tanto, si reescribimos (*) a una relación de recurrencia más simple, obtenemos
$$A_N = N \cdot A_{N-1} + (-1)^N$$
(mientras que la función factorial tiene simplemente $N! = N (N-1)!$ ). Esto se puede reducir (**) a otras formas, como
$$A_N = N! \cdot \sum_{i = 0}^N \frac{(-1)^i}{i!}$$
Por último, le interesa la probabilidad de que todas las bolas se asignen a casillas distintas. Esto es exactamente
$$p_N = \frac{A_N}{(N-1)^N}$$
Se podría utilizar, por ejemplo, Stirling en el factorial en $A_N$ para conseguir
$$N! = N \cdot (N-1)! \approx N \frac{(N - 1)^{N - 1}}{e^{N - 1}} \sqrt{2 \pi (N - 1)}$$
Entonces, para la proporción que quieres, obtienes
$$p_N = \frac{A_N}{(N-1)^N} \approx \frac{N}{(N - 1)^N} \cdot \frac{(N - 1)^{N - 1}}{e^{N - 1}} \sqrt{2 \pi (N - 1)} \cdot \sum_{i = 0}^N \frac{(-1)^i}{i!}$$ $$= \frac{\sqrt{2 \pi N}}{e^{N - 1}} \sqrt{\frac{N}{N - 1}} \sum_{i = 0}^N \frac{(-1)^i}{i!}$$
Para los grandes $N$ la suma converge a $e^{-1}$ , mientras que $N/(N-1) \approx 1$ , lo que da una probabilidad de
$$p_N \approx \frac{\sqrt{2 \pi N}}{e^N}$$
(*) Esto puede hacerse utilizando la inducción en $N$ . El paso de la inducción:
$$A_N = (N-1) A_{N-1} + (N-1) A_{N-2} = N A_{N-1} - A_{N-1} + (N-1) A_{N-2}$$ $$ = N A_{N-1} - \left((N-1) A_{N-2} + (-1)^{N-1}\right) + (N-1) A_{N-2} = N A_{N-1} + (-1)^N$$
(**) Esto puede hacerse utilizando la inducción en $N$ . El paso de la inducción:
$$A_N = N \cdot A_{N-1} + (-1)^N = N \cdot (N-1)! \cdot \left(\sum_{i = 0}^{N-1} \frac{(-1)^i}{i!}\right) + N! \frac{(-1)^N}{N!}$$ $$ = N! \cdot \left(\sum_{i = 0}^{N - 1} \frac{(-1)^i}{i!} + \frac{(-1)^N}{N!}\right) = N! \cdot \sum_{i = 0}^{N} \frac{(-1)^i}{i!}$$
