不动点极限 II

Fixed Point Limit II

个人笔记

令 $F_n$ 表示随机置换 $f:S_n\to S_n$ 的不动点（fixed points）数量，其中 $S_n=\{1,2,\dots,n\}$ 。

求

\lim_{n\to\infty}\mathbb{P}[F_n=5].

已知答案形如 $\frac{c}{e}$ （ $e$ 为自然常数），求 $c$ 。

Let $F_n$ be the number of fixed points of a random permutation $f: S_n \rightarrow S_n$ , where $S_n = \{1,2,\dots,n\}$ . Find

\lim_{n \rightarrow \infty}\mathbb{P}[F_n = 5]

The answer is in the form

\frac{c}{e}

where $e$ is Euler's constant and $c$ is a constant. Find $c$ .

解析

经典结论：随机置换的不动点数 $F_n$ 在 $n\to\infty$ 时分布收敛到 $\mathrm{Poisson}(1)$ 。

因此

\lim_{n\to\infty}\mathbb{P}[F_n=5]=e^{-1}\frac{1^5}{5!}=\frac{1}{5!\,e}.

所以 $c=\boxed{\frac{1}{120}}$ 。

Classic conclusion: The fixed point number of random substitutions $F_n$ converges to $\mathrm{Poisson}(1)$ at $n\to\infty$ .

Therefore,

\lim_{n\to\infty}\mathbb{P}[F_n=5]=e^{-1}\frac{1^5}{5!}=\frac{1}{5!\,e}.

So $c=\boxed{\frac{1}{120}}$ .