《组合数学》详解 Chapter 2 排列与组合

Ink_Render · 2021-04-18 10:00:25 · 个人记录

2.1 四个基本计数原理

这四个原理是计数中最简单也是随时都在使用的，分别为加法，乘法，减法，除法原理。接下来将按顺序介绍这四个原理。

• 加法原理

首先，我们要引入一个概念：划分。

对于一个集合 S ，定义其划分为满足：

的 S 的子集的集合 T 。

注意，在定义中，一个集合的划分依然是一个集合（而非一种关系或运算），这个集合为 T = \{ S_i | i \in [1,n] \} 。同时，根据这个定义，划分的元素可以有空集，不过由于无意义，所以我们一般默认划分没有空集（有空集也不用管）。

在上面的式子中，我们可以发现， 由于 S 中的每一个元素都出现过（式①），而没有一个元素出现过两次（式②），所以S 中的每一个元素都刚好在且仅在 T 的一个元素中。

那么，我们就可以换一种通俗的说法来定义划分，就是有 n 个桶，把 S 中的元素随便往这 n 个桶里丢，最后的结果即为一个划分。

回到加法原理。加法原理描述如下：对于集合 S 的划分中的元素 S_1 , S_2 , \cdots , S_n ，有：

证明也很简单，因为 S 中的元素在划分中出现且仅出现一次，如果我们把 S_i 中的元素一个一个扔回 S （S 初始为 \varnothing ），那么，每扔回一个，对于 S 都是不在集合中的元素，所以每个元素都要计数。

加法原理的应用主要是对原问题进行划分（这里的划分与上文的术语不同，指的是意义上的“分成几个部分”）。将一个复杂的问题划分成若干个不相交易解决的子问题，再用加法原理求和。在信息学中，这就是我们很熟悉的分治算法。

• 乘法原理

乘法原理的定义为：

若

则

假设现在你要去参加一个 party ，要选一套好看的衣服，你的衣服有 p 件，裤子有 q 件，则你有 p \times q 种搭配选择。

与加法原理有些类似的是，乘法原理需要选择与选择之间无关。拿上面的例子来说，你选的裤子与之前选的衣服无关，不管你选哪件衣服，你都有 q 裤子可以选。如果你是个美学大师，认为对于每一件衣服，只有某些裤子可以搭配，这种情况下乘法原理就不能用了。

接下来两个原理较简单，本文只给出，不做注解。

• 减法原理

若

则

• 除法原理

除法原理是乘法原理一定程度上的逆定理。

若集合 S 的一个划分 T=\{S_i|S_i \subseteq S\} 。

则

其实就是把一个集合均分，每份 k 个，求份数。

在讲完这四个基本计数定理之后，我们就可以开始进行一些简单的计数。在此之前，我们还需声明与区分两个概念：排列与组合。排列，顾名思义，就是一些元素按照顺序排成一列，而组合则是只考虑这些元素有哪些而不考虑顺序。所以说，排列有序，组合无序。

例子 对于集合 S=\{1,2,3\} ，包含三个元素的排列有 6 个（123 , 132，213，231，312，321），而组合只有一个。

2.2 集合的排列

我们定义一个集合 S 的 r 排列为从集合 S 中取出 r 个元素进行的排列。比如集合 S=\{1,2,3\} 的 2 排列有 12，13，21，23，31，32 共 6 个。我们用 P(n,r) 表示一个元素个数为 n 的集合的 r 排列个数，如果 r>n （排列的元素数比集合的元素个数还大），则 P(n,r)=0 。

那么，我们如何计数出 P(n,r) 呢？我们按照乘法原理来思考：我们把一个 r 排列看成 r 个位置，每个位置可放入一个元素。对于第一个位置，我们可以在 S 中选出一个元素，那么对于第一个位置，我们有 n 种放置的可能。在放完第一个元素后， S 中还剩下 n-1 个元素，对于我们而言，不论第一次选出的元素是哪个，都不影响接下来的操作（我们并不关心剩下哪些元素，只关心剩下多少个元素），所以可以使用乘法原理。于是我们在剩下的 n-1 个元素中选出一个放在第二位，剩下 n-2 个元素，以此类推。这样我们就可以得出计算 P(n,r) 的方法：

定理 2.2.1

对于 0 \le r \le n ，有

同时，由于 P 是一个对于每个不同序列都无差别的计数函数，所以很多时候还有一些巧妙的计数方法：

例子 求集合 S=\{i|i \in [1,6] , i \in N \} 的含有 5 的 4 排列数。

这道题目是在排列计数的基础上增加了一个限制。我们先考虑，既然排列中一定有 5 ，那么可以先将 5 填入排列中，有 4 种可能。此时，还剩下 3 个位置，这时我们可以暂时把 5 忽略掉，考虑剩下 3 个位置的情况，显然是 P(5,3)=60 ，所以一共就有 4 \times 60 = 240 个排列。

在这个例子中，我们将问题分为了两个部分，先解决有限制的部分，再解决一般的部分。由于不论 5 在哪个位置，排列都是一样的，所以可以直接乘法原理计数。

我们刚刚讲的严格意义上来说应该叫线性排列，因为最后会排成一列。在集合的排列中，还有一种特殊的排列——循环排列，指的是将排列中的数围成一个圈，每两个通过旋转可以转变为完全相同的循环排列被视作同一个循环排列。对于这种排列，我们可以这样想：对于一个线性排列 { 1，2，3，4 }，将它转换为循环排列后，会有另外 3 个线性排列与它相同，即 { 2，3，4，1 } ， { 3，4，1，2 } ， { 4，1，2，3 } 。我们只要每次把线性排列的第一个元素放到最后即可生成出每一个转换成循环排列相同的那些线性排列，也就是说，对于线性 r 排列，每 r 个排列会变成一个循环排列，则在 n 个元素中的循环 r 排列的排列数 P'(n,r) （非通用表达，仅为本文中的表示）为：

定理 2.2.2

对于 0 \le r \le n ，有

这种排列一般出现在圆桌等环状结构中。

2.3 集合的组合（子集）

相对于排列，组合在计数中运用的更加广泛，在集合中，我们说的更多的是子集，这两个术语本质上并没有区别。我们定义一个集合 S 的 r 子集 S_0 是满足 S_0 \subseteq S 并且 |S_0|=r 的集合。比如 S=\{1,2,3\} 的 2 子集有：\{1,2\}，\{1,3\}，\{2,3\} 共 3 个。

我们用 \dbinom{n}{r} （或者是 C(n,r)，C_n^r，_n\!\,C_r）表示一个有 n 个元素的集合的 r 子集的个数。对它的计算我们可以从刚刚的排列推导过来。

我们考虑，对于每一个 r 子集，它都有 P(r,r)=r! 个不同的排列，而对于不同的两个子集，由于它们的元素不同，所以它们的排列必然两两不同，所以每 r! 个 r 排列对应着一个 r 子集。对于一个有 n 个元素的集合，它有 P(n,r) 个 r 排列，所以

定理 2.3.1

对于 0 \le r \le n，有

通过定理 2.3.1 ，我们可以发现：分母部分的两个求阶乘的数相加刚好为 n ，也就是说，如果我们把 r 换成 n-r ，我们应该可以得到一样的结论，所以

推论 2.3.2

对于 0 \le r \le n，有

组合数还有很多重要的性质，在本章，我们先讨论其中两个。

其一：

定理 2.3.3

对于 0 \le k \le n-1，有

在这里我们给出两种证明方式：

1. 暴力计算

2. 组合推理证明

我们将满足 |S|=n 的集合 S 的 k 子集分入两个集合 A 和 B ，集合 A 中放入含有 S 的第一个元素的 k 子集，集合 B 中放入不含有 S 的第一个元素的 k 子集，则集合 A 中的元素相当于是在选完 1 之后在剩下的 n-1 个元素中选 k-1 个， B 相当于选 k 个，所以

经过对比，我们可以发现，组合推理证明明显比暴力计算要简单，这种推理法在后面也会经常用到。

比如下面这个定理：

定理 2.3.4

对于 n \ge 0 ，有

这个定理明显不好使用暴力计算，我们考虑推理：

可以发现， \sum\limits_{i=0}^{n} \dbinom{n}{i} 其实就是满足 |S|=n 的集合 S 的所有子集数。而我们又可以用另一种方法找到 S 的每一个子集： S 的每一个元素，我们都可以选或不选，则根据乘法原理，一共有 \begin{matrix} \underbrace{2 \times 2 \times \cdots \times 2}\\ n \end{matrix}=2^n 个子集。故得证。

如果有大佬提前看了后面的内容或是了解过，就会知道组合数也被称为二项式系数，我们在后文会讲到。

讲完了集合的排列与组合（子集），我们再来了解一下多重集合的排列与组合。

首先，先要了解什么是多重集合。多重集合本质上不是集合，因为在 集合定义的基础上，多重集合的一个元素可以出现多次。我们用在元素前加上 n_i \cdot（点乘）表示这个元素在多重集合中出现了 n_i 次，称 n_i为重数，所以，多重集合形为 S=\{n_1 \cdot a_1,n_2 \cdot a_2 ,\cdots n_k \cdot a_k\} 。值得注意的是，其中的 n_j \in [1,\infty] ，也就是说有的元素可能有 \infty 个。

在本章节，我们只对多重集合的排列与组合的一些特殊情况进行研究。在 Chapter 6 ，我们会对多重集合的排列与组合再进行深入研究。

2.4 多重集合的排列

首先，我们先来看一种情况——多重集合中的每个元素都有 \infty 个。在这种情况下，每一位我们都可以选择任意一个元素，即这一位的选择与前无关，那么根据乘法原理，有

定理 2.4.1

设有 n 种元素的多重集合 S 满足 \forall i\, \operatorname{s.t.}\,n_i=\infty ，则此多重集合的 k 排列数为

当然，我们可以对这个定理进行一些分析。我们知道，乘法原理可用的先决条件是前面的选择与后面无关或是前面的每一个选择所对应的后面的选择数都相同，也就是说，其实我们只要保证 S 的每一个元素在每一个位置都能取到，即每一个元素的重数均大于 k 即可。

于是我们得到定理 2.4.1 的加强版：

定理 2.4.1 plus

设有 n 种元素的多重集合 S 满足 \forall i\, \operatorname{s.t.}\,n_i\ge k ，则此多重集合的 k 排列数为

第二个定理与第一个定理的限制则完全相反。定理 2.4.1 规定了元素的重数范围，而定理 2.4.2 则是规定了排列的长度。

首先思考，如果我们将一个所有元素重数都不为 \infty 的多重集合 S 中的所有元素都拿出来进行排列，也就意味着我们不用考虑拿出来了哪些元素，而是只需要考虑元素之间的顺序。这种情况下，我们可以按顺序考虑每一种元素放置的位置。假设元素总个数为 n=\sum\limits_{i=1}^{k} n_i 。对于第一种元素，我们要在 n 个位置中找到 n_1 个位置来放置他们，有 \dbinom{n}{n_1} 种情况。接下来，我们又要在剩下的 n-n_1 个位置中选 n_2 个位置，有 \dbinom{n-n_1}{n_2} 种情况。以此类推。于是，我们可以得到

定理 2.4.2

设有 k 种元素的多重集合 S ，设 n=\sum\limits_{i=1}^{k} n_k ，则这个集合的 n 排列数为

我们将其展开，则

这个定理通常用于这种描述的题目：将一个有重复元素的序列重新排序可以得到多少个不同的序列。

例子 现在有一个数 1424 ，问将其重新排列可以构造出多少个不同的数（包括原数）。

这个序列实际上代表着多重集合 S=\{1 \cdot 1 , 1 \cdot 2 , 2 \cdot 4 \} ，运用定理 2.4.2 可以得到答案为

（也许你要说， 12 个完全排列可以用程序暴力生成，而不是使用这个有着一大堆 “！” 的东西。不过，如果这个数是 314159265358979323846 ，或许定理 2.4.2 就会尤为重要）

2.5 多重集合的组合

在 Chapter 2 ，对于多重集合的组合，我们也只考虑一种特殊情况，即多重集合 S 的所有元素的重数均为 \infty 。

既然是组合，我们需要关注的就只有选出的每一种元素的个数。我们将 S 的组合也表示成多重集合的形式 S'=\{x_1 \cdot a_1 , x_2 \cdot a_2 ,\cdots , x_k \cdot a_k\} ，接下来我们要找到符合要求的 x_1,x_2,\cdots ,x_k 的组数。如果我们要找到 S 的 r 组合，则只要满足 x_1+x_2+\cdots+x_k=r 即可。所以，问题也就转化成了找到方程 x_1+x_2+\cdots+x_k=r 解的组数。

我们尝试来构造一个序列，其中有 r 个 1 和 k-1 个 0 。我们用以下步骤来构造这个序列：

1. 将所有 1 先放入序列

2. 将 0 插入进去。

这个过程的本质是，将 r 个 1 分成了 k 个部分，我们再看看前面，这不就是找到了上面的方程的一组解吗？对于第 i-1 个 0 和第 i 个 0 ，他们之间的 1 的个数就是 x_i 的值。例如，序列 10111001 所表示的就是方程 x_1+x_2+x_3+x_4=5 的一组解 x_1=1,x_2=3,x_3=0,x_4=1 。这也就告诉我们，我们只要找出满足条件的序列的个数即可。而我们在上个小节讲过，这个序列有可看做是多重集合 S=\{r \cdot 1 , (k-1) \cdot 0\} 的 r+k-1 排列数，即

定理 2.5.1

设有 k 种元素的多重集合 S 满足 \forall i\, \operatorname{s.t.}\,n_i=\infty ，则此多重集合的 r 组合数为

不过，在更多的时候，这个定理被用于计算上面的方程的解的组数。

有时候，上述的方程还会有一些限制，比如：

例子 对于 S=\{\infty \cdot 1 ,\infty \cdot 2 ,\infty \cdot 3\} ，问其每种元素都出现过的 8 组合有多少个？

这个题目中，对组合中元素的重数有了一定限制，即 \forall i \operatorname{s.t.} n_i \ge 1。这种情况下，我们需要想办法将限制一般化。

我们可以运用等量代换，用 y_i 代替 x_i-1 ，那么 y_i 就是我们定理 2.5.1 中的形式，所以我们的方程从 x_1+x_2+x_3=8 变成了 y_1+y_2+y_3=5 ，那么答案就为 \dbinom{5+3-1}{5}=\dbinom{7}{5}=21 。

在 Chapter 5 ，我们会再次讲到有关限制上下界的多元方程的解的个数。

在本章节的最后，我们来探讨一下基础计数在计算有限概率时的应用。

2.6 有限概率

关于有限概率，学术性的定义读者可以自行百度，我们在这里只进行通俗定义：

对于一个实验 \varepsilon ，可能出现的结果是有限的 n 个，如果每一个结果的出现都是等可能的（或者你可以理解为每一个结果都没有限制或限制相同），那么我们说这个实验是随机的。我们将这个实验的所有可能的结果的集合称为样本空间，记作集合 S=\{s_1,s_2,\cdots,s_n\} ，其中的 s_i 表示结果。

当我们进行实验时，对于 S 中的每一个结果，假设它们每个出现的次数都相同（虽然现实中这基本不可能），因为它们的出现都是等可能的，那么，对于其中的每一个 s_i ，它出现的次数占总次数的 \frac{1}{n} ，我们就说这个时间的概率为 \frac{1}{n} ，记作

或简记为

通常，一个事件会是一个包含若干个结果的集合 E ，我们将一个事件的概率定义为事件与样本空间的比值，即

根据定义，因为

所以

同时，这个公式告诉我们，我们在求解有限概率时，只需要计数出样本空间和事件的大小。这样，我们就完成了从有限概率到计数问题的转换。

例子 现在有一个集合 S=\{1,2,4,5,6,8\} ，我们在其中随机构造出一个 4 子集，问出现的子集同时有 1 和 2 的子集有多少个。

运用前面的知识

当然，很容易能想到，概率也是可以进行一些运算的。

定义事件 E 的补事件 \overline{E} 为 \{s_i|s_i \in S ,s_i \not\in E\} ，则

练习题中会有更多的有限概率计算。

2.7 练习题

（未完……）