### MIT高级算法8：基本计数、鸽巢原理与排列
#### 一、计数的基本方法：匹配法
在离散数学中，计数是一个核心主题。它涉及到各种各样的问题，例如一棵树有多少叶子、一个图有多少种最小着色方案、具有特定顶点集合的树的数量、一副五十二张牌的扑克中有多少种五张牌的手牌组合、一个锦标赛中选手的一致排名数量、以及根据男孩和女孩的偏好有多少种稳定的婚姻配对等等。
一种有效的计数方法是将待计数的事物与我们已知如何计数的事物进行匹配。例如，在学期初我们通过将幂集中的元素与长度为n的2^n个二进制字符串精确匹配来计算了一个包含n个元素的集合的幂集大小。这种匹配不一定是双射（即一一对应），也能够提供有价值的信息。
作为示例，假设我们要确定在6.042教室中典型的某一天内手表的数量。我们可以将手表与教室里的人进行关联；具体来说，对于每个人最多有一只手表（至少在这里我们做这样的假设）。我们知道参加6.042课程的学生人数大约是146人。此外，还有三位讲师和八位助教，他们通常是教室中唯一的非学生群体。因此，我们可以推断出，在一个典型的日子中，6.042教室里的手表数量最多不超过157块。
虽然这种论证非常简单，但它的力量不容小觑。我们将看到如何利用这类简单的论证来证明其他方法难以得出的结果。
#### 二、匹配作为双射、单射与满射
更精确地说，“匹配”是指在我们想要计数的事物与被计数的事物之间找到双射、单射或满射。下面的定理正式地证明了这种计数方式的有效性：
**定理2.1**：设A和B为有限集合，f是从A到B的一个函数。如果：
1. f是一个双射，则|A| = |B|；
2. f是一个单射，则|A| ≤ |B|；
3. f是一个满射，则|A| ≥ |B|。
这个定理是如此基础以至于很难找到更简单的公理来证明它。事实上，目前我们还无法证明这个定理，因为我们还没有定义什么是双射、单射和满射以及它们与集合基数之间的关系。
接下来，我们将探讨几种具体的计数技巧，并通过几个实例来加深理解。
#### 三、鸽巢原理的应用
鸽巢原理是一个直观的原理，它指出如果有更多的鸽子而巢的数量不足，那么至少有一个巢将包含多于一只的鸽子。这一原理可以用来解决许多计数问题。
例如，考虑这样一个问题：在一个由10个人组成的房间中，至少有两个人的生日是在同一个月。这里，我们可以将“鸽子”看作人的生日，而“巢”则代表月份。因为一年有12个月，而房间中有10个人，根据鸽巢原理，至少有两个人的生日在同一月。
#### 四、排列与组合
排列与组合是计数中两个重要的概念。排列是指从n个不同元素中取出r个元素，按照一定的顺序排列成序列的方法总数。而组合则是指从n个不同元素中取出r个元素，不考虑顺序的不同取法总数。
对于排列，其公式为：
\[P(n,r) = \frac{n!}{(n-r)!}\]
对于组合，其公式为：
\[C(n,r) = \frac{n!}{r!(n-r)!}\]
其中，\(n!\) 表示n的阶乘，即 \(n \times (n-1) \times ... \times 1\)。
### 结论
通过学习基本的计数技巧，如匹配法、鸽巢原理、排列与组合等，我们可以解决许多实际问题。这些方法不仅有助于我们在理论层面上理解计数问题，而且还能帮助我们在计算机科学领域设计更高效的算法。随着进一步的学习，我们会发现更多复杂的计数方法和技术，这些都将为我们的研究和实践提供有力的支持。
