计数技术与概率

组合、变换和排列是概率研究中最常用的计数技术，因为它们在等概率结果的实验中提供了很大的方便。这些实验中最具代表性的例子来自赌博游戏。它们通常涉及一个样本空间 \Omega = \{\omega_1, \omega_2, \cdots, \omega_N\} 上的非确定性过程。这些实验有一个共同的特点，即形式为 \{\omega_i\}\in\mathcal{A}_\Omega 的所有事件，其中 i\in\{1,2,\cdots, n\}，具有相同的发生概率。

基于 相对频率极限的概率测量，我们可以将事件的概率建立为基数的商。正如我们所见，这通过以下关系实现：

P(E) = \displaystyle \lim_{N\to\infty}g_N(E) = \lim_{N\to\infty}\frac{f_N(E)}{N}= \frac{\# E}{\# \Omega}

这里符号“#”表示集合的基数。这就是所谓的有利事件与可能事件的公式。

在这些情况下，概率计算归结为计算样本空间和待测事件的基数。因此，首先复习一些计数技术将非常有用。

计数技术的获取

为了引入组合、变换和排列，我们将设计一些具有等概率结果的实验，并从中进行推论，得出这些计数技术。

假设我们有一台“完美的随机机器”，它由一个黑匣子、一块记忆板、一个动作按钮和一个重置按钮组成。机器具有以下属性：

1. 机器只有一个可配置的参数：其样本空间的基数 \Omega_N = \{\omega_1,\cdots,\omega_N\}
2. 按下动作按钮时，它将在屏幕上显示 \Omega_N 中的一个元素
3. 当显示一个结果时，它会被存储在记忆板中，在那里时按下动作按钮将不会再次显示相同的结果。
4. 如果机器已经显示了所有可能的结果，它将冻结并不再显示任何内容。
5. 重置按钮会清除记忆板和屏幕上的显示内容。

使用这台机器，我们将设计一些实验并分析它们的样本空间。

实验1（AORm）：执行——按顺序记录——重置，重复m次

将机器配置为 \#\Omega = N 并重复 m\leq N 次以下步骤：

1. 按下动作按钮
2. 将结果按顺序记录在列表中
3. 重置

完成后，我们将获得一个包含 m 个 \Omega_N = \{\omega_1,\cdots,\omega_N\} 元素的有序列表。此列表可以解释为 \Omega_N 的一个 m 元组。换句话说，此实验的样本空间 \Omega_{AORm} 将为：

\Omega_{AORm}=\Omega_N \times \cdots \times \Omega_N = \Omega_N^m

因此，我们将得到 \#\Omega_{AORm}=\#\Omega_N^m = N^m。

实验2（AOk）：执行——按顺序记录，重复k次

再次将机器配置为 \#\Omega = N 并重复 k 次 (k\leq N) 以下步骤：

1. 按下动作按钮。
2. 将结果按顺序记录在列表中。

完成后，我们将获得一个包含 k 个 \Omega_N = \{\omega_1,\cdots,\omega_N\} 元素的有序列表，但其中的任何元素都不会与其前面的元素重复。

由于机器本质上不会偏向任何可能的结果（因为它是完美随机的），可以假设在第一次按下动作按钮时发生了事件 \{\omega_1\}，因此下一次动作的样本空间应为 \Omega_N\setminus\{\omega_1\}。类似地，可以假设第二次按下动作按钮时发生了事件 \{\omega_2\}，因此下一次动作的样本空间应为 (\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}。如果继续这种方式，当我们进行第 k 次动作时，其样本空间将为：

(\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\}

因此，此实验的可能结果样本空间将为：

\Omega_{AOk}= \Omega \times (\Omega_N\setminus\{\omega_1\}) \times ((\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}) \times \cdots \times ((\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\})

因此，如果计算此集合的基数，我们将得到：

\#\Omega_{AOk}= N \cdot (N-1) \cdot (N-2) \cdots [N-(k-1)]=\displaystyle \frac{N!}{(N-k)!}

根据这一结果，我们得出以下定义：

实验3（ADk）：执行——无序记录，重复k次

此实验与前一个完全相同，只不过现在不记录 \Omega_N 元素出现的顺序。换句话说，两个包含相同元素但顺序不同的 k 元组现在被视为同一个。因此，利用从实验 AOk 获得的每个 k 元组可以以 (k)_k=k! 种不同的方式写出，将得到此实验样本空间的基数为：

\#\Omega_{ADk} = \displaystyle \frac{\#\Omega_{AOk}}{(k)_k} = \frac{(N)_k}{k!} = \frac{N!}{k!(N-k)!}

根据此结果，可以得出以下定义：

通过排列、变换和组合的计数技术，我们现在可以测量各种集合的大小。