\documentclass[UTF8,11pt,a4paper,fontset=none]{ctexart}

\usepackage[margin=25mm]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{fontspec}
\usepackage[hidelinks]{hyperref}

\setmainfont{Latin Modern Roman}
\setCJKmainfont[AutoFakeSlant=0.2]{Noto Serif CJK SC}
\setCJKsansfont{Noto Sans CJK SC}
\setCJKmonofont{Noto Sans Mono CJK SC}
\pagestyle{plain}
\setlength{\parindent}{2em}
\setlength{\parskip}{0.45em}
\setlength{\jot}{7pt}

\theoremstyle{definition}
\newtheorem{theorem}{定理}

\title{\textbf{随机排列的不动点}\\
  \large 期望与概率分布}
\author{}
\date{}

\hypersetup{
  pdftitle={随机排列的不动点——修订中文本},
  pdfsubject={关于错排与不动点的自足数学报告}
}

\begin{document}

\newcommand{\EditionName}{中文修订版}
\newcommand{\EditionSummary}{%
  本版以修订英文本为基础，用规范的中文重新撰写，并采用相同的定义、结论与证明．}
\input{cover-page-zh}

\maketitle
\vspace{-2em}

\begin{abstract}
从 \(n\) 个元素的所有排列中等概率地任取一个排列，令 \(X\) 表示其中不动点的
个数．本文先直接证明：对任意正整数 \(n\)，都有 \(\mathbb{E}[X]=1\)；再用
容斥原理逐步推导错排公式，进而求出 \(X\) 的精确概率分布．这一结果也可用于
描述如下情形：将 \(n\) 个互不相同的选项随机填入 \(n\) 个互不相同的空格时，
填对的平均个数为 \(1\)．
\end{abstract}

\section{问题设定}

对正整数 \(n\)，记
\[
  [n]=\{1,2,\ldots,n\}\text{．}
\]
从对称群 \(S_n\) 的 \(n!\) 个元素中等概率地选取一个排列
\(\sigma:[n]\to[n]\)．若 \(r\in[n]\) 满足 \(\sigma(r)=r\)，则称 \(r\) 为
\(\sigma\) 的一个\textbf{不动点}．定义
\[
  X=\bigl|\{r\in[n]:\sigma(r)=r\}\bigr|\text{．}
\]
我们的首要问题是求 \(X\) 的期望；随后还将求出它的完整概率质量函数，作为
更强的结论．

\section{不动点个数的期望}

\begin{theorem}
对任意 \(n\geq 1\)，
\[
  \mathbb{E}[X]=1\text{．}
\]
\end{theorem}

\begin{proof}
对每个 \(r\in[n]\)，定义示性随机变量
\[
  I_r=
  \begin{cases}
    1, & \sigma(r)=r,\\
    0, & \sigma(r)\ne r\text{．}
  \end{cases}
\]
于是 \(X=\sum_{r=1}^{n}I_r\)．在全部 \(n!\) 个排列中，固定某个给定位置
\(r\) 的排列恰有 \((n-1)!\) 个，故
\[
  \Pr(\sigma(r)=r)=\frac{(n-1)!}{n!}=\frac{1}{n},
  \qquad
  \mathbb{E}[I_r]=\frac{1}{n}\text{．}
\]
由期望的线性性质，
\[
  \mathbb{E}[X]
    =\sum_{r=1}^{n}\mathbb{E}[I_r]
    =n\cdot\frac{1}{n}
    =1\text{．}
\]
这一论证不要求各示性随机变量彼此独立．
\end{proof}

\textbf{等价的双重计数观点．}
考虑所有满足 \(\sigma(r)=r\) 的有序对
\((\sigma,r)\in S_n\times[n]\)．给定 \(r\) 后，固定 \(r\) 的排列恰有
\((n-1)!\) 个，因此这种有序对共有 \(n(n-1)!=n!\) 个．再除以排列总数
\(n!\)，便再次得到：每个排列平均有一个不动点．

\section{错排与精确分布}

上述期望证明不需要知道 \(X\) 的概率分布．若要进一步求出每个
\(\Pr(X=k)\)，则须先计算没有任何不动点的排列数．

\subsection{错排计数}

没有任何不动点的排列称为\textbf{错排}．用 \(D_m\) 表示 \(m\) 个元素的错排
数，并约定 \(D_0=1\)．

\begin{theorem}[错排公式]
对任意整数 \(m\geq 0\)，
\[
  D_m=m!\sum_{j=0}^{m}\frac{(-1)^j}{j!}\text{．}
\]
因此，从 \(m\) 个元素的所有排列中等概率地任取一个，得到错排的概率为
\[
  \frac{D_m}{m!}=\sum_{j=0}^{m}\frac{(-1)^j}{j!}\text{．}
\]
\end{theorem}

\begin{proof}
当 \(m=0\) 时，唯一的空排列就是错排，公式给出 \(D_0=1\)．以下设
\(m\geq1\)，并以全部 \(m!\) 个排列组成的集合 \(S_m\) 为全集．对每个
\(r\in[m]\)，令
\[
  A_r=\{\sigma\in S_m:\sigma(r)=r\}\text{，}
\]
即 \(A_r\) 是所有固定 \(r\) 的排列组成的集合．一个排列是错排，当且仅当
它不属于 \(A_1,\ldots,A_m\) 中的任何一个，因此
\[
  D_m=\left|\bigcap_{r=1}^{m}\overline{A_r}\right|\text{．}
\]

容斥原理先计入全部 \(m!\) 个排列，再减去固定每个指定元素的排列；同时固定
两个指定元素的排列在上一步被重复减去，故须加回，依此交替进行：
\begin{align*}
  D_m
    ={}&|S_m|-\sum_{r=1}^{m}|A_r|
       +\sum_{1\leq r<s\leq m}|A_r\cap A_s|-\cdots\\
       &\quad+(-1)^m|A_1\cap\cdots\cap A_m|\text{．}
\end{align*}
为了计算各项，选取子集 \(J\subseteq[m]\)，并设 \(|J|=j\)．若要求
\(J\) 中的每个元素都保持不动，则剩下的 \(m-j\) 个元素可以任意排列，故
\[
  \left|\bigcap_{r\in J}A_r\right|=(m-j)!\text{．}
\]
当 \(J=\varnothing\) 时，上式中的交集约定为全集 \(S_m\)，因而这里也包含
\(j=0\) 的情形．
这样的集合 \(J\) 共有 \(\binom{m}{j}\) 个．按 \(j\) 合并容斥式中的各项，
便得到
\begin{align*}
  D_m
    &=\sum_{j=0}^{m}(-1)^j\binom{m}{j}(m-j)!\\
    &=m!\sum_{j=0}^{m}\frac{(-1)^j}{j!}\text{．}
\end{align*}

最后还可以直接验证，这个交错和恰好只留下错排．若一个排列有
\(q\geq1\) 个不动点，那么在指定 \(j\) 个不动点的各项中，它共出现
\(\binom{q}{j}\) 次，因而它在整个交错和中的净系数为
\[
  \sum_{j=0}^{q}(-1)^j\binom{q}{j}=(1-1)^q=0\text{．}
\]
错排没有不动点，即 \(q=0\)，所以恰好被计数一次．这也直接说明了容斥原理
在此处为何有效．

再除以排列总数 \(m!\)，即得所述概率公式．
\end{proof}

例如，
\[
  D_3
    =3!-\binom{3}{1}2!+\binom{3}{2}1!-\binom{3}{3}0!
    =6-6+3-1
    =2\text{．}
\]
用单行记法表示，这两个错排是 \([2,3,1]\) 与 \([3,1,2]\)．

当 \(m\geq 2\) 时，\(j=0\) 与 \(j=1\) 两项相互抵消，因此上述概率也可写成
\[
  \sum_{j=2}^{m}\frac{(-1)^j}{j!}\text{．}
\]
这正是复刻英文本所采用的形式．

\subsection{不动点个数的分布}

\begin{theorem}
对 \(k=0,1,\ldots,n\)，
\[
  \Pr(X=k)
    =\frac{\binom{n}{k}D_{n-k}}{n!}
    =\frac{1}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}\text{．}
\]
\end{theorem}

\begin{proof}
先选出恰好保持不动的 \(k\) 个位置，共有 \(\binom{n}{k}\) 种选法；其余
\(n-k\) 个位置必须构成错排，共有 \(D_{n-k}\) 种．因此，恰有 \(k\) 个
不动点的排列数为 \(\binom{n}{k}D_{n-k}\)．除以排列总数 \(n!\)，并代入
错排公式，得到
\begin{align*}
  \Pr(X=k)
    &=\frac{\binom{n}{k}D_{n-k}}{n!}\\
    &=\frac{1}{k!}
      \sum_{j=0}^{n-k}\frac{(-1)^j}{j!}\text{．}
\end{align*}
\end{proof}

这一统一公式也包含两个边界情形：
\[
  \Pr(X=n)=\frac{1}{n!},
  \qquad
  \Pr(X=n-1)=0\text{．}
\]
第二个等式成立，是因为一个排列不可能只移动一个元素而固定其余所有元素．

\section{结论}

直接使用示性随机变量即可看出：均匀随机排列平均有一个不动点．进一步计数
还可得到其精确分布
\[
  \Pr(X=k)=\frac{\binom{n}{k}D_{n-k}}{n!},
\]
其中错排数 \(D_{n-k}\) 由容斥原理求得．因此，将 \(n\) 个互不相同的答案
等概率地随机填入 \(n\) 个互不相同的空格时，平均会填对一个．这里的“一个”
是期望值；在某次具体尝试中，可能一个也没填对，也可能填对一个或多个．

\end{document}
