只看关键元素的相对次序

解题套路

1. 认关键元素。 问一句「哪几个元素的先后决定了所求」，把它们挑出来（记作 $k$ 个）， 其余元素与结果无关——它们插在哪都不改变答案。
2. 把无关元素删掉。 剩下 $k$ 个元素的相对次序，$k!$ 种等可能。
3. 把所求翻译成位次。 「谁排在最前」「$A$ 在 $B$ 之前」「$A$ 之前有几个 $B$」都是位次的函数， 于是概率变成数次序，期望变成一个小加法。

第 2 步是这条套路的全部力气所在，它的理由是一句可数的话：$n$ 个元素的 $n!$ 个排列，按 「指定的 $k$ 个元素的相对次序」分类恰好分成 $k!$ 类，每类都有 $\dfrac{n!}{k!}$ 个 （类内把这 $k$ 个元素在它们占的那 $k$ 个位置上重排，就是两类之间的一一对应）。 每类一样大 $\Rightarrow$ 每种相对次序的概率都是 $\dfrac{1}{k!}$。

三个现成的结论

• $k=2$：「$A$ 排在 $B$ 之前」的概率恒是 $\dfrac12$，与总共有多少个元素无关。
• 「$A$ 是这 $k$ 个里最先出现的那个」概率是 $\dfrac1k$。
• 「一直抽到 $A$ 才停，$A$ 之前抽到了几个 $B$ 类元素」——设 $B$ 类有 $n$ 个，则这个个数 $=A$ 在这 $n+1$ 个元素里的位次 $-1$，故它在 $\{0,1,\dots,n\}$ 上均匀分布， 每个值的概率是 $\dfrac{1}{n+1}$，期望是 $\dfrac{n}{2}$。

为什么比逐次乘条件概率省

逐次算要按「第几次停」分类，每一类写一条乘法链；而无关元素会把类数翻上去——它们可以插在 停止之前的任意位置，每插一处就多一条序列。相对次序法把无关元素一次性删干净，剩下的只有 $k!$ 种次序，且个个等可能，连乘法都不用。

顺带，它给出的是整个分布而不是某一个概率，所以「求 $P$」与「求 $E$」两个问法一起收。

边界

• 只对不放回成立。 不放回抽取才等价于「先随机排成一列，再从左往右读」；有放回时 同一个元素可以反复出现，根本没有「相对次序」这回事，结论全部失效。
• 无关元素必须真的无关。 若规则对它也有反应（比如「抽到它也停」），它就是关键元素，不能删。 删之前把「它的位置完全不影响所求」这句话验一遍。
• 关键元素之间要地位对称。 等可能靠的是排列的对称性；若某些元素被赋予不同的抽取权重 （不是均匀随机排列），$k!$ 种次序就不再等可能。