第二章

$$\displaystyle{ { n \choose k } = { n \choose n - k } = \frac{ {n !} }{ {k !} {\left( n - k \right) !} } }$$

随机排列数组

void shuffle(int* a, int n) {
    for (int i = 0; i < n; ++i) {
      swap(a[i], a[rand(i, n)]);
    }
}

• 每次 for 循环之前，每个可能的 $\displaystyle{ i }$ 排列，数组包含这个 $\displaystyle{ i }$ 排列的概率是 $\displaystyle{ \frac{ {\left( n - i \right) !} }{ {n !} } }$
• 终止时 $\displaystyle{ i = n }$，对于任何排列，出现概率为 $\displaystyle{ \frac{ 1 }{ {n !} } }$

如果将随机的范围为 $\displaystyle{ \left[ 0 , n \right) }$，数列应该不是随机的

$$\displaystyle{ \begin{aligned}B _{ K } & = \bigcap _{ i = 1 } ^{ K } A _{ i } \\ P \left( B _{ k } \right) & = P \left( A _{ k } \cap B _{ k - 1 } \right) = P \left( B _{ k - 1 } \right) P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = P \left( B _{ k - 2 } \right) P \left( A _{ k - 1 } \mid B _{ k - 2 } \right) P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = P \left( B _{ 1 } \right) P \left( A _{ 1 } \mid B _{ 1 } \right) \ldots P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = 1 \cdot \frac{ n - 1 }{ n } \cdot \frac{ n - 2 }{ n } \cdot \ldots \cdot \frac{ n - k + 1 }{ n } \\ & = \left( 1 - \frac{ 1 }{ n } \right) \left( 1 - \frac{ 2 }{ n } \right) \ldots \left( 1 - \frac{ k - 1 }{ n } \right) \\ & \leqslant \exp \left( - \frac{ 1 }{ n } - \frac{ 2 }{ n } - \ldots - \frac{ k - 1 }{ n } \right) \\ & = \exp \left( - \frac{ k \left( k - 1 \right) }{ 2 n } \right) \leqslant \frac{ 1 }{ 2 }\end{aligned} }$$