¿cuál es la probabilidad de que un determinado permutación tiene exactamente k puntos fijos.

Question

Dada una permutación aleatoria de $\sigma \in S_n$ a partir de [n] $\to$ [n] en un uniforme de probabilidad espacio, ¿cuál es la probabilidad de que $\sigma $ tiene exactamente k de punto fijo para un determinado k entre a$1$$n$.

significa: ¿cuál es la probabilidad para que $\exists x_1 ,...,x_k \in [n] : \sigma (x_i) = x_i $ $\ i\in$ {1,...,k} y para cada $y \notin$ {$x_1 , ... , x_k$} llegamos $\sigma(y) \neq y$.

Vi que $\lim_{n \to \infty } prob(A_0) = e^{-1}$ mediante la Inclusión–exclusión en el principio y creo que para un determinado k : $\lim_{n \to \infty} prob(A_k) = \frac{e^{-1}}{k!}$ pero no estoy seguro de cómo mostrarlo.

*$A_k$ representa para el evento "k".

Answer 1

Hay $\binom{n}{k}$ posibilidades de la $k$ puntos fijos.

En caso de establecerse, a continuación, hay $!(n-k)$ alteraciones de los otros puntos.

Que da $\binom{n}{k}\left[!(n-k)\right]$ permutaciones con exactamente $k$ fijo de puntos sobre un total de $n!$ permutaciones.

También tenemos la fórmula: $$!(n-k)=(n-k)!\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$ and we end up with probability: $$\frac1{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$

Answer 2

1. Número de dearrangements de $k$-elementos que se $$!k = k!\sum\limits_{m=0}^{k}\frac{(-1)^m}{m!}$$
2. En la n-conjunto de elementos que se pueden seleccionar $(n-k)$ elementos para dearrange ellos (el resto de $k$ puntos son fijos) en $\binom{n}{k}$ formas

Así $$A_k^n = \binom{n}{k}(n-k)!\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}$$ Y la probabilidad es $$P(A_k^n) = \frac{\binom{n}{k}(n-k)!\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}}{n!}=\frac{\frac{n!}{k!}\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}}{n!}=\frac{1}{k!}\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}$$