Probabilidad de que una permutación aleatoria no fije ningún elemento para grandes $n$

Question

Este es un problema que ha estado rondando mi grupo de amigos. He resuelto este problema, y estoy interesado en una generalización del mismo.

Este es el problema original: Elija un elemento de $\sigma\in S_n$ uniformidad al azar, y que $X(n)$ sea la variable aleatoria que es el número de puntos fijos de $\sigma$ . Calcula

$$\lim_{n\to\infty}P(X(n)=0)$$

Aquí está la extensión: Supongamos que en lugar de $S_n$ estamos interesados en una clase de subgrupos, $\{H_n:n\in I\subseteq\mathbb{N}\}$ . Podemos entonces preguntarnos: ¿cuál es la probabilidad de que el límite produzca $$\lim_{n\to\infty}\frac{\mu(H_n)}{|H_n|}$$

donde $\mu(G)$ es el mayor número tal que cada elemento de $G$ fija $\mu(G)$ o más elementos de $[n]$ cuando se ve como un subconjunto de $S_n$ . La noción que intento formalizar aquí es "el menor número de puntos fijos que se alcanza realmente", ya que para muchos grupos, cada elemento tiene un punto fijo.

Esta parece ser la generalización correcta del problema, aunque otras generalizaciones son bienvenidas. Lo pregunto sobre todo por curiosidad para ver qué se puede probar. Resultados sobre grupos transitivos, subgrupos doblemente transitivos, $D_{2n}$ o cualquier otra clase de grupos razonablemente interesantes sería emocionante para mí.

Este enlace parece relevante, pero no tengo claro que este problema se pueda resolver simplemente sumando números de Recontre. Este El post de MSE también parece relevante, pero no lo suficiente como para resolver el problema por sí solo.

Answer 1

Es bastante conocido que hay $$ D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!} $$ derangos (permutaciones sin puntos fijos) en $S_n$ por lo que la probabilidad límite para el primer problema es $\color{red}{\large\frac{1}{e}}$ . También es la probabilidad límite para el segundo caso (aleatorio incluso permutación), ya que la diferencia entre los números de derivaciones pares e Impares viene dada por el determinante de un $n\times n$ matriz $M_n$ con elementos cero en la diagonal y elementos iguales a $1$ fuera de la diagonal. $M_n$ es la diferencia entre un rango- $1$ matriz (que tiene valores propios $n,0,0,\ldots$ ) y la matriz identidad, por lo que la diferencia entre las derivaciones pares e Impares es $n-1$ en valor absoluto y la probabilidad límite es la misma en ambos casos.