Skip to content

03 There Are A Lot Of Them. Elementary Counting Problems

Permutations

Definition 3.1. 将个不同对象排成一列，且每个对象只能使用一次，这称之为排列(permutation)。个对象的所有排列的个数是，这称之为n的阶乘(factorial)，用表示。

Theorem 3.2. 一个个元素的集合的所有排列的个数是。

这里有个约定：。为什么不等于零呢？考虑两个房子，一间个人，一间个人，将两间房的人分别拍成一列，共有种排列。如果呢？为了使在这种极端情况下也成立，我们不得不令。
是一个重要的数，但是它有多大呢？斯特林公式(Stirling's formula)给出了近似值 符号意味着。

Example 3.3. 三种不同的颜色图一个三个水平条纹的棋子，要求颜色各不相同，多少种图法？
Solution. 略。

Example 3.4. 某园丁需要将五朵红花，三朵黄花和两朵白花种成一排。有多少种方式？
这个题目不能直接套用前面的公式，因为不是所有的对象都是不同的。这种集合称之为多重集(multiset)，其排列问题称之为多重集的全排列(multiset permutation)。
假设10朵花都不相同，那么共有种排列方式，但是对于某种排列，交换任意两朵红花，结果是一致的，对于红花共有种重复。黄花和白花类似。所以不同排列的方式共有

对该问题进行泛化，可以得到如下命题：
Theorem 3.5. 多重集有个对象，它们属于类，每类对应的个数分别是，那么排列数是

Strings over a Finite Alphabet

我们接下来要处理的问题是用元素有限的字母表(alphabet)来构造字符串。

Theorem 3.6. 用个元素的字母表构造长度为的字符串，其数量是个。
Proof. 选择第一个字符，有种不同的方式。第二个字符可以和第一个字符相同，也有种方式，依此类推，第个字符也有种方式。选择这个字符是独立的，所有共有种选择方式。

Example 3.7. 位正整数有个。
Solution. 略。

下面介绍组合计数中常用的一种方法：双射(bijections)。举个例子，在舞厅中有一些男人和一些女人，我们不知道男人的数量，但是我们知道有243个女人。那么我们可以对男女进行配对。如果没人被剩下来，那么男人也是243个；如果男人剩下了，那么男的比女的多，反之男的比女的少。

Definition 3.8. 和是有限集合，满足
(1) 如果，那么
(2) 对所有的，存在唯一的使得
我们称是到的双射。

Definition 3.9. 令。如果满足Definition 3.8的条件(1)，我们称之为单射(one-to-one, injection)；如果满足Definition 3.8的条件(2)，我们称之为满射(surjection)。

Proposition 3.10. 和是有限集合，如果在到上存在满射，那么和的元素数量一样多。
Proof. 满射将和的元素进行了配对，如果匹配了对，那么和都有个元素。

这个方法非常重要。如果对计数很难，我们可以找到一个集合，在到上存在一个满射，且它较容易计数，那么问题就变得更容易解决了。

Example 3.11. 个元素的集合所有子集的个数是。
Solution. 构造一个双射。任意一个子集可以看作是一个长度为的字符串，如果第个元素在中，那么第个字符是1，否则是0。同时，相同的子集得到的字符串是相同的。
根据Theorem 3.6，这些字符串组成的集合有个元素。

Example 3.12. 一个城市有10个路口，有些要安装交通灯，这些路口中的某些路口还会盖加气站。共有多少种不同的方式？
Solution. 某个路中有三种可能性，两者都有，只有交通灯，什么也没有。总计有种。

Theorem 3.13. 从个元素的字母表中组成个字母的字符串，每个字母最多用一次，那么字符串总数是 其中

Example 3.14. 总统从20个候选人种选出5个组成内阁，问有多少种选法？
Solution. 略。

Choice Problems

从给定集合中选出一个子集(subset)，顺序是无关紧要的。

Definition 3.15. 从集合中选出个元素的子集的个数用 来表示，也被称作是二项式系数(binomial coefficient)。

Theorem 3.16. 对所有非负整数，

Definition 3.17. 是集合的子集，表示的补集。是唯一满足下面条件的的子集： 当且仅当，其中。

Proposition 3.18. 对所有非负整数，有以下两个性质： Proof. 我们建立一个从个元素的子集到个元素的子集的双射：是任意一个个元素的子集，是对应的个元素的子集，。根据双射定义，两者元素个数相等，所以= 。
取即可得到第二个性质。=0，这个唯一的集合就是空集。

Example 3.19. 一个医学院学生一月份要去医院工作五天，但是不能连续两天都去，他有多少种不同的选法呢？
Solution. 不妨设这个学生选择的五天依次是，根据题意，那么。我们可以选择，然后再得到，所以问题从集合中选择不相邻的五个数转化成了从集合选择五个数，那么有 种不同选法。

Example 3.20. 从集合中有放回的选择五个数，那么有多少种选法？
Solution. 和上题类似，这五个数满足 选择一个双射，那么 那么共有 种选法。

Theorem 3.21. 从集合中选择个元素的多重集，有 种不同选法。

下面是本章的总结。

Exercises

(24) 幻方(magic square)是每行每列相加都相等的由非负整数组成的方阵。表示的方阵的个数，其中是每行每列的和。求证： Solution. 对于的方阵，如下图所示四个数就能确定一种组成形式。

下图展示了其他位置上的数。

每个数都是非负数，所以有以下一系列的限制 我们下面分三种情况讨论。
(a) ，那么被所隐含，也就是冗余的。那么 第一个不等式等价于公式(3)，第二个不等式等价于我们的假设，第三个不等式等价于我们的假设，最后一个就是我们的公式(2)。确定的话，那么也就确定了。利用例题中的方法将不等号变成等号，那么共有 种可能性。
(b) ，那么是冗余的。那么 与(a)同理，那么共有 种可能性。
(c) ，那么都是冗余的。 同理，共有 种可能性。