La probabilidad y el Grupo Simétrico

Question

Deje $p_{n,k}$ la probabilidad de que una permutación aleatoria de $S_n$, el grupo simétrico de orden $n!$, tiene exactamente $k$ puntos fijos. Estoy tratando de calcular $\lim _{n\to \infty}p_{n,k}$. Después de jugar un poco con ella, estoy relativamente seguro de que el límite es $\frac{1}{k!}$, aunque todavía tengo que venir para arriba con una prueba.

Esto es lo que he intentado hasta ahora. Si $a_{n,k}$ es el número de elementos de a $S_n$ $k$ puntos fijos, entonces tenemos que

$$a_{n,k}=\binom{n}{k}a_{n-k,0}$$

Es decir, no se $\binom{n}{k}$ formas de elegir los $k$ puntos fijos, y después de los que son elegidos, hay $a_{n-k,0}$ a permutar el resto de $n-k$ elementos con $0$ puntos fijos. Después de la computación $a_{n,0}$ a mano para valores pequeños de a $n$, yo era capaz de buscar la fórmula de recursión $a_n=na_{n-1}+(-1)^n$ a partir de oeis.org. El uso de este, yo era capaz de llegar con mi "adivinar" de $\frac{1}{k!}$, pero esta dirección no parece ser que me lleva hacia la búsqueda de una prueba.

Alguna idea de cómo proceder? Grupo de teoría no es mi punto fuerte, así que no me sorprendería si hay un resultado que hace que este problema sea casi trivial. Un puntero a cualquier resultado sería excelente.

Answer 1

El número de puntos fijos es de aproximadamente de Poisson, por lo que la probabilidad correcta es $e^{-1}/k!$. Usted debe ser capaz de derivar esto mediante una adecuada inclusión-exclusión de la fórmula.

Ir primero por todos los $k$-conjuntos y la suma de las probabilidades de tener un punto fijo - en el límite de esta parte contribuye $1/k!$. Cada $(k+1)$-set fue contada $k+1$ veces en lugar de $0$, por lo que eliminar $k+1$ veces la contribución de todos los $(k+1)$-establece - en esta parte contribuye $(k+1) \cdot -1/(k+1)! = -1/k!$ en el límite. Cada $(k+2)$es ahora contaba $\binom{k+2}{2} - (k+2)\cdot (k+1) = -\binom{k+2}{2}$ veces en lugar de $0$, por lo que añadir $\binom{k+2}{2}$ veces la contribución de todos los $(k+2)$-establece - en esta parte contribuye $\binom{k+2}{2} \cdot 1/(k+2)! = 1/2k!$ en el límite. Continuar con el patrón, obtenemos $$\frac{1}{k!} \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \cdots \right) = \frac{e^{-1}}{k!}.$$ Voy a dejar de trabajar en los detalles.

Answer 2

Aquí un punto de vista distinto que continúa a lo largo de las líneas que ya se va. El uso de una fórmula diferente para $a_{n,0}$ de la OEIS; el uso de $$a_{n,0} = n! \sum_{j=0}^n \frac{(-1)^j}{j!}.$$ Esta es una conocida fórmula para $a_{n,0}$ (la alteración de los números) y puede ser demostrado mediante la inclusión-exclusión. (Añadido: también puede que desee ver en la prueba y el argumento general dada por Qiaochu de Yuanes en su respuesta a una pregunta similar.)

Como $n \to \infty$, la suma en la expresión de $a_{n,0}$ enfoques $e^{-1}$. Con esto y su expresión $a_{n,k} = \binom{n}{k} a_{n-k,0}$, que está casi a la respuesta correcta de $e^{-1}/k!$ dado por Yuval Filmus.