随机排列置换问题
某玩家玩一个游戏：初始时，系统均匀随机生成 \(n\) 元全排列序列 \(s_n\)，然后该玩家对序列进行若干次如下操作：
- 选择 \(i, j \in [1, n]\)，将序列中第 \(i\) 个和第 \(j\) 个元素置换。
若该玩家能在至多 \(m\) 次操作后将序列变为唯一顺序序列 \((1,2,\dots ,n)\)，则称操作成功。求：
- 操作成功的概率 \(p_{n,m}\)
- \(p_{n,m}=1\) 时，直到操作成功，所需操作的期望次数 \(E_{n}\)。
解答
我们首先研究操作次数最少的策略。将 \(s_n\) 中每个元素作为索引，指向其应该所在的位置，如此可得到若干循环，又称轮换或圆排列。例如，\((2,3,1,5,4)\) 有这些循环：
- \(2 \to 3 \to 1 \to 2\)，长度为 \(3\)。
- \(5 \to 4 \to 5\)，长度为 \(2\)。
可见，不同循环之间的元素是分离的，彼此互不相关。
先证明一个引理：记每个循环的长度为 \(k\)，则为了让该循环中所有元素都回到其位置，恰好需要 \(k - 1\) 次交换。
证明：首先，所有元素的交换只需考虑在其所在的循环内部进行，因为跨循环元素的交换，最终所需操作数严格不少于在循环之内的交换。
我们用数学归纳法可以证明，在循环内的最少交换次数恰好是 \(k-1\)。证毕。
若序列 \(s_n\) 共有 \(c\) 个循环，其中第 \(i\) 个循环的长度为 \(k_i\)，那么最小交换次数为
\[ \sum_{i=1}^c (k_i - 1) = n - c. \]
于是，若 \(n - c \leq m\)，则操作必然成功。否则，\(c < n-m\) 时，操作有可能失败。
1
第一类斯特林数 \(S_1(n,m)\) 是将 \(n\) 个不同元素构成 \(m\) 个圆排列的方案数目，满足递推关系
\[ S_1(n,m) = S_1(n-1, m-1) + (n-1) S_1(n-1,m). \]
故
\[ P(c=k) = \frac{S_1(n,k)}{n!}. \]
于是，操作成功的概率为
\[ p_{n,m} = \frac{1}{n!} \sum_{k= \max(0,n-m)}^n S_1(n,k). \]
2
最小交换次数为 \(n-c\)，故
\[ E_n = E(n-c) = n - E(c). \]
使用期望定义
\[ E(c) = \sum_{k=0}^n kP(c=k) \]
计算 \(E(c)\) 过于复杂，不过我们用指示变量法可以很快做出漂亮的解。
考虑 \(s_n\) 中，第 \(i\) 个循环的最小元素为 \(e_i\)，记序列中的第 $j $ 个元素 \(j \in [1,n]\)，指示变量
\[ X_j = \begin{cases} 1, j \text{是某个} e_i \\ 0, \text{otherwise} \end{cases} \]
那么
\[ c = \sum_{j=1}^n X_j. \]
注意到，\(j\) 成为某个循环的最小元素，当且仅当 \(j\) 的位置出现在所有比它小的元素 \(1, 2, \dots, j - 1\) 之后。于是
\[ E(X_j) = \frac{1}{j}, \]
故
\[ E_n = n - H_n. \]
其中 \(H_n\) 为调和级数的第 \(n\) 项。这个结果有一种简洁美。
PS：综合考虑，我们可以得到一个第一类斯特林数的性质
\[ \sum_{k=0}^n kS_1(n,k) = n! \cdot H_n. \]
它的概率意义为，随机排列中，循环数的期望为 \(H_n\)。