初赛第七章 - 排列组合（2）

本文主要是介绍初赛第七章 - 排列组合（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1条件组合

1.1 鸽巢原理

鸽巢原理(Pigeonhole Principle),也称抽屉原理(Drawer Principle)或 Dirichlet 原理,是组合数学中一个重要且简单的原理。它的内容如下:

如果将 $n + 1$ 个物体放入 $n$ 个盒子中,那么至少有一个盒子包含不少于两个物体。

更一般地,如果将 $kn + 1$ 个物体放入 $n$ 个盒子中,那么至少有一个盒子包含不少于 $k + 1$ 个物体。

尽管这个原理看起来非常简单,但它在组合数学、数论、图论等领域有着广泛的应用。下面我们通过几个具体的例子来理解这个原理。

1.2 容斥原理

题目:一个班级有 $30$ 个学生,其中 $20$ 个学生会说英语, $15$ 个学生会说法语, $12$ 个学生会说西班牙语, $8$ 个学生会说英语和法语, $6$ 个学生会说英语和西班牙语, $5$ 个学生会说法语和西班牙语, $3$ 个学生会说这三种语言。请问班上至少会说一门外语的学生有多少人?

解答:

设 $E$ 表示会说英语的学生集合, $F$ 表示会说法语的学生集合, $S$ 表示会说西班牙语的学生集合。我们要求的是 $\cup F \cup S|$ 。

根据容斥原理,我们有:

$\cup F \cup S| = |E| + |F| + |S| - |E \cap F| - |E \cap S| - |F \cap S| + |E \cap F \cap S|$

代入已知条件:

$∣ E ∣ = 20$
$∣ F ∣ = 15$
$∣ S ∣ = 12$
$\cap F| = 8$
$\cap S| = 6$
$\cap S| = 5$
$\cap F \cap S| = 3$

计算得:

$\begin{aligned} |E \cup F \cup S| &= 20 + 15 + 12 - 8 - 6 - 5 + 3 \\ &= 31 \end{aligned}$

因此,班上至少会说一门外语的学生有 $31$ 人。

这个题目展示了容斥原理在解决实际问题时的应用。我们首先定义了三个集合 $E$ , $F$ , $S$ ,然后根据题目给出的条件,列出了这些集合的基数以及它们交集的基数。最后,我们运用容斥原理的公式,计算出了至少会说一门外语的学生人数。

1.3 概率

概率论是数学的一个重要分支,研究随机现象出现的可能性大小。它在众多领域(如统计学、物理学、工程学、金融学等)都有广泛的应用。在组合数学中,概率论与计数问题密切相关。

1.3.1 概率的定义

对于一个随机试验,我们用 $S$ 表示所有可能的结果组成的集合,称为样本空间。样本空间中的每个元素称为一个样本点,表示一个基本事件。

对于样本空间 $S$ 的任意一个子集 $A$ ,我们称 $A$ 为一个事件。如果事件 $A$ 中恰好包含 $k$ 个样本点,且样本空间 $S$ 中共有 $n$ 个样本点,每个样本点出现的可能性相同,则事件 $A$ 发生的概率为:

$\frac{k}{n}$

这就是古典概型的定义。它表示事件 $A$ 发生的可能性,是一个在 $0$ 到 $1$ 之间的实数。

### 1.3.2 概率的性质

概率有以下基本性质:

非负性:对于任意事件 $A$ ,有 $\geq 0$ 。
规范性:对于必然事件 $S$ ,有 $P (S) = 1$ 。
可列可加性:如果 $A_1, A_2, \ldots$ 是两两互不相容的事件,则 $P(\bigcup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty} P(A_i)$ 。

1.3.3 条件概率

对于两个事件 $A$ 和 $B$ ,事件 $B$ 发生的条件下事件 $A$ 发生的条件概率为:

$\frac{P(A \cap B)}{P(B)}$

这个公式表示,在事件 $B$ 已经发生的前提下,事件 $A$ 发生的概率。

1.3.4 全概率公式

如果事件 $A_1, A_2, \ldots, A_n$ 构成一个完备事件组(即它们两两互斥,且和为全事件),则对于任意事件 $B$ ,有:

$\sum_{i=1}^{n} P(A_i)P(B|A_i)$

这就是全概率公式。它表示,事件 $B$ 的概率可以通过考虑事件 $B$ 在每个 $A_i$ 发生条件下的条件概率求得。

1.3.5 贝叶斯公式

在全概率公式的基础上,我们可以得到贝叶斯公式:

$P(A_i|B) = \frac{P(A_i)P(B|A_i)}{\sum_{j=1}^{n} P(A_j)P(B|A_j)}$

这个公式表示,在事件 $B$ 发生的条件下,事件 $A_i$ 发生的概率。它提供了一种根据新的信息(事件 $B$ 的发生)来更新对事件 $A_i$ 发生可能性的认识的方法。

1.3.6 独立性

如果对于事件 $A$ 和 $B$ ,有 $\cap B) = P(A)P(B)$ ,则称事件 $A$ 和 $B$ 是独立的。

直观地说,两个事件独立意味着一个事件的发生不影响另一个事件发生的可能性。

1.3.7 概率在组合问题中的应用

在组合问题中,我们经常需要计算某些事件发生的概率。通常,我们可以按照以下步骤解决这类问题:

明确样本空间,即所有可能的结果。
确定感兴趣的事件。
计算事件中的样本点数量(通常使用组合计数技巧)。
计算样本空间中的样本点总数。
用事件中的样本点数量除以样本空间中的样本点总数,得到事件的概率。

下面是一个简单的例子:

问题:从一副 $52$ 张的扑克牌中随机抽 $2$ 张,求抽到的 $2$ 张牌点数和为 $10$ 的概率。

解答:

样本空间为所有 $2$ 张牌的组合,共有 $C_{52}^{2} = 1326$ 种可能。
感兴趣的事件是点数和为 $10$ 的 $2$ 张牌的组合。
点数和为 $10$ 的 $2$ 张牌有以下几种情况:
- $1$ 和 $9$ :共 $\times 4 = 16$ 种组合。
- $2$ 和 $8$ :共 $\times 4 = 16$ 种组合。
- $3$ 和 $7$ :共 $\times 4 = 16$ 种组合。
- $4$ 和 $6$ :共 $\times 4 = 16$ 种组合。
- $5$ 和 $5$ :共 $\binom{4}{2} = 6$ 种组合。
因此,点数和为 $10$ 的 $2$ 张牌共有 $16 + 16 + 16 + 16 + 6 = 70$ 种组合。
样本空间中共有 $1326$ 种 $2$ 张牌的组合。
因此,抽到点数和为 $10$ 的 $2$ 张牌的概率为:

$\frac{70}{1326} \approx 0.0528$