组合学 [7]

本篇内容

• 经典计数问题（分配问题）
• 整数的分割
• Stirling number of the second
• 容斥原理

覆盖集

1. 概念

一个集合 $A$ 的一个覆盖集（cover）是指由若干子集 ${A_1, A_2, \dots, A_n}$ 组成的集合族，满足 $\bigcup_{i=1}^{n}A_i=A$。也就是说，这个覆盖集由若干个子集组成，取并集后能够得到原来的集合 $A$。我们与集合的分割做一个简单的区分就是这些子集之间可以有相同的元素，允许它们之间的元素重复。

2. 定理

对于一个有限集合 $A$ 和它的一个覆盖集 ${A_1, A_2, \dots, A_n}$ ，原集合 $A$ 的大小不超过所有子集 $A_i$ 的大小之和。也就是说，覆盖集中的所有子集大小之和是一种上界，$A$ 的大小不会超过这个上界。这个引理可以用归纳法来证明。

归纳证明可以分为三个步骤：

• 当 $n=1$ 时，引理显然成立。
• 假设当 $n=k$ $(k\geq2)$ 时引理成立，即 $|A|\leq\sum_{i=1}^{k}|A_i|$。
• 当 $n=k+1$ 时，我们可以将 $A_{k+1}$ 加入到已有的覆盖集 ${A_1, A_2, \dots, A_k}$ 中，得到新的覆盖集 ${A_1, A_2, \dots, A_k, A_{k+1}}$ 。因为这个覆盖集能够覆盖整个集合 $A$，所以 $\bigcup_{i=1}^{k+1}A_i=A$ 。然后我们可以用数学归纳法的假设，得到

$$|A|\leq\sum_{i=1}^{k}|A_i|+|A_{k+1}|=\sum_{i=1}^{k+1}|A_i|$$

综上所述，对于一个有限集合 $A$ 和它的一个覆盖集 ${A_1, A_2, \dots, A_n}$ ，我们可以用覆盖集中所有子集大小之和作为 $A$ 的上界。

鸽子洞原理

鸽子洞原理（Pigeonhole Principle）是离散数学中的一个基本原理，简言之，如果将 $n+1$ 个物体分别放入 $n$ 个容器中，那么至少有一个容器中要放置不少于 $2$ 个物体。

更一般地，如果有 $N$ 个物体需要放置到 $n$ 个容器中，那么至少有一个容器中要放置不少于 $\lceil \frac{N}{n} \rceil$ 个物体。

这个原理的证明可以这样理解：

如果有 $n+1$ 只鸽子分别放入 $n$ 个鸽子洞中，且每个鸽子洞中最多只能放置一只鸽子，那么最多只能放置 $n$ 只鸽子，无法放置第 $n+1$ 只鸽子，与前提条件矛盾，因此必然存在一个容器中至少放置了 $2$ 只鸽子。

同样地，如果有 $N$ 个物体需要放置到 $n$ 个容器中，且每个容器中最多只能放置 $\lfloor \frac{N}{n} \rfloor$ 个物体，那么最多只能放置 $n \cdot \lfloor \frac{N}{n} \rfloor$ 个物体，无法放置剩余的 $N - n \cdot \lfloor \frac{N}{n} \rfloor$ 个物体，也与前提条件矛盾，因此必然存在一个容器中至少放置了 $\lceil \frac{N}{n} \rceil$ 个物体。

经典问题

1. 汉诺塔问题

汉诺塔问题是一个经典的数学谜题，也被称为汉诺威塔或汉诺塔。问题的设定是：有三个柱子，最左边的柱子上有 $n$ 个盘子，盘子大小不同，大的在下面，小的在上面。现在需要把所有盘子移动到最右边的柱子上，但是在移动的过程中，必须保证任何时候大盘子在下面，小盘子在上面。同时，每次只能移动一个盘子，且不能将大盘子放到小盘子上面。问需要多少次操作才能完成任务。

显然，对于 $n=1$ 的情况，只需要一次移动即可完成任务，因此 $H_1=1$ 。对于 $n=2$ 的情况，可以将最小的盘子从 1 号柱移动到 2 号柱，然后将剩下的一个盘子从 1 号柱移动到 3 号柱，最后将 2 号柱上的盘子移动到 3 号柱即可完成任务。因此， $H_2=3$ 。对于 $n\geq 3$ 的情况，我们可以先将前 $n-1$ 个盘子从 1 号柱移动到 2 号柱，然后将第 $n$ 个盘子从 1 号柱移动到 3 号柱，最后将 2 号柱上的 $n-1$ 个盘子移动到 3 号柱。由于每次移动只能移动一个盘子，因此移动 $n-1$ 个盘子需要 $H_{n-1}$ 步，移动一个盘子需要 1 步，移动 $n-1$ 个盘子需要 $H_{n-1}$ 步，因此总共需要 $H_n=2H_{n-1}+1$ 步。

2. 斐波那契数列

斐波那契数列是一个数学序列，它的定义如下：

$$f_0=1,\ f_1=1,\ f_n=f{n-1}+f_{n-2} (n\geq 2)$$

也就是说，序列的前两项都是1，从第三项开始，每一项都等于前两项的和。这个数列得名于意大利数学家斐波那契。

对于斐波那契数列，可以通过递推公式 $f_n=f_{n-1}+f_{n-2}$ 来计算$f_n$的值，但是更常用的方法是通过其通项公式来计算。

3. 通项公式

斐波那契数列的通项公式为

$$f_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$

这个公式可以通过求解递推公式的特征方程得到，具体的求解过程可以参考线性代数中矩阵特征值与特征向量的相关知识。

因此，如果要求解斐波那契数列中第 $n$ 项的值，可以直接使用上面的通项公式进行计算。
需要注意的是，通项公式虽然可以方便地计算出序列中任意一项的值，但是在实际计算中可能会存在精度问题，因此在进行精确计算时还是需要使用递推公式来计算。

同样地，如果要求解汉诺塔问题中移动$n$个盘子所需要的最少步数 $H_n$ ，可以使用递推公式 $H_n=2H_{n-1}+1$ 进行计算，也可以使用通项公式 $H_n=2^n-1$ 来计算。通项公式可以通过归纳法证明，具体证明过程可以参考离散数学中的数学归纳法原理和数学归纳法证明的相关知识。

线性齐次递推关系式

线性齐次递推关系式（linear homogeneous recurrence relation）是一种数学函数序列。这个序列满足递推式:

$$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_k a_{n-k}$$

其中 $n\geq k$，$c_1,\dots,c_k$ 为常数，$c_k \neq 0$。

这种递推式的特点是：每个项都是前 $k$ 项的线性组合，并且递推式中的系数都是不随 $n$ 变化的常数，因此称为“线性、齐次、常系数”的递推关系式。

例如，$f_n=f_{n-1}+f_{n-2}$ 是一个线性齐次递推关系式，因为它可以写成 $f_n=1\cdot f_{n-1}+1\cdot f_{n-2}$，而 $H_n=2H_{n-1}+1$ 则不是线性齐次递推关系式，因为它不是一个线性组合。

线性齐次递推关系式有许多应用，比如在计算机科学中，它们可以用来描述算法的时间复杂度。另外，对于一个线性齐次递推关系式，我们可以通过求解其特征方程来得到它的通项公式，进而计算出每一项的值。通常情况下，初始条件 $a_0,a_1,\dots,a_{k-1}$ 也是已知的，这样就可以唯一确定整个序列了。

存在性和唯一性

对于递推式 $a_n=\sum_{i=1}^{k}c_i a_{n-i}$，我们希望找到一个序列 ${x_n}$ 作为递推式的解，且满足初始条件 $x_i=a_i$ 对于 $0\leq i<k$ 成立。

1. 存在性

可以构造一个序列 ${x_n}$，满足上述初始条件和递推式，因此解的存在性得到了保证。具体而言，初始条件保证了 ${x_n}$ 的前 $k$ 个元素与 ${a_n}$ 相等，然后我们可以利用递推式得到 ${x_n}$ 的后续元素。

2. 唯一性

如果存在两个序列 ${x_n}$ 和 ${x_n'}$ 满足递推式和初始条件，那么这两个序列是相等的。具体而言，假设 $x_n\neq x_n'$，那么存在最小的 $n$ 使得 $x_n\neq x_n'$，由于递推式只涉及前面的 $k$ 项，因此 $x_n$ 和 $x_n'$ 在前 $n-k$ 个元素上必须相等。然后根据递推式，我们可以得到 $x_n$ 和 $x_n'$ 之间的关系，然而这与假设矛盾，因为 $n$ 是最小的使得 $x_n\neq x_n'$ 的值。因此我们得出结论：如果存在一个解满足初始条件和递推式，那么它是唯一的。

综上所述，该定理保证了递推式的解的存在性和唯一性。这在离散数学中有着广泛的应用，例如在计算机科学中，递归和动态规划算法中常常需要求解递推式的解。

特征根

特征根（characteristic roots），也称为特征值（eigenvalues），是解线性齐次递推关系式（Linear Homogeneous Recursive Relation，LHRR）的重要工具。对于 LHRR ，其递推关系式可以表示为 $a_n=\sum\limits_{i=1}^k c_i a_{n-i}$ ，其中 $c_i$ 为常数， $a_n$ 表示第 $n$ 项的值。

假设存在一种解形式为 $a_n=r^n$ ，将其代入递推关系式中得到 $r^n=\sum\limits_{i=1}^k c_i r^{n-i}$ ，通过整理可以得到 $r^n = c_1 r^{n-1} + c_2 r^{n-2} + \dots + c_k r^{n-k}$ 。这个等式被称为特征方程式（characteristic equation），其左边为特征根 $r$ 的幂，右边为特征根所对应的系数。因此，特征根是特征方程式的根。

例如，在 LHRR ， $f_n=f_{n-1}+f_{n-2}, n\geq 2$ 中，其特征方程式为 $r^2-r-1=0$，特征根为 $r_1=\frac{1+\sqrt{5}}{2}$ 和 $r_2=\frac{1-\sqrt{5}}{2}$ 。因此， $f_n=\alpha_1 r_1^n+\alpha_2 r_2^n$ 是 LHRR $f_n=f_{n-1}+f_{n-2}, n\geq 2$ 的通解，其中 $\alpha_1$ 和 $\alpha_2$ 是常数，可以通过初始条件来确定。

特征根在线性代数和微分方程中也有广泛的应用。在矩阵的特征值分解中，特征根是矩阵特征值的通称。在微分方程的解法中，特征根是齐次线性微分方程的解形式。

线性非齐次递推关系式

线性非齐次递推关系式（Linear Nonhomogeneous Recurrence Relation，LNRR）是指具有常系数和非零右端项的递推关系式，其中右端项可以是一个常数项或者是一个函数项。对于一个LNRR，可以找到对应的齐次递推关系式（Homogeneous Recurrence Relation，HRR），也称为其相关齐次递推关系式（Associated Homogeneous Recurrence Relation，AHRR）。AHRR 是一个不含右端项的齐次递推关系式。

一个 LNRR 的通项公式可以通过求解其对应的 AHRR 和特解（Particular Solution）相加得到。AHRR 的解可以表示为 $a_n=\sum\limits_{i=1}^k c_ia_{n-i}$，其中 $c_1, c_2, \ldots, c_k$ 是常数且 $c_k\neq0$，$k$ 表示关系式的阶数。特解可以根据右端项的形式得到，例如如果右端项是一个常数，那么特解就是一个常数，如果右端项是一个一次函数，那么特解就是一个一次函数，等等。

举个例子，对于 LNRR： $a_n=a_{n-1}+a_{n-2}+n^2+n+1$ ，可以得到对应的 AHRR 是 $a_n=a_{n-1}+a_{n-2}$ 。根据这个 AHRR ，我们可以得到其特征方程 $r^2=r+1$ ，解得 $r_1=\frac{1+\sqrt{5}}{2}$ 和 $r_2=\frac{1-\sqrt{5}}{2}$。因此，AHRR 的通项公式是 $a_n = c_1 r_1^n + c_2 r_2^n$，其中 $c_1$ 和 $c_2$ 是常数。

接下来，我们需要求出特解。因为右端项是一个二次多项式，我们猜测特解是一个二次多项式 $an^2+bn+c$ ，其中 $a$ 、$b$ 和 $c$ 是待定系数。将其代入 LNRR 中，得到

$$(an^2+bn+c)-(a(n-1)^2+b(n-1)+c)-(a(n-2)^2+b(n-2)+c)=n^2+n+1$$

化简后，可以得到 $a=\frac{1}{2}$，$b=-\frac{1}{2}$，$c=1$。因此，特解为 $a_n=\frac{1}{2}n^2-\frac{1}{2}n+1$。

最终，我们得到了 LNRR 的通项公式 $a_n=c_1r_1^n+c_2r_2^n+\frac{1}{2}n^2-\frac{1}{2}n+1$ 。其中，$c_1$ 和 $c_2$ 可以通过给定的初始条件求得。

通解

定理指出，如果 $x_n$ 是 LNRR 的解，那么只要存在与 LHRR 相关的解 $y_n$ ，那么 $z_n=x_n+y_n$ 就是 LNRR 的解。这意味着，任何 LNRR 的解都可以表示为其对应 LHRR 解和一个特定解的和，这个特定解称为“通解”或“一般解”。

在这个定理中， $y_n$ 是 LHRR 的解，它与 $x_n$ 的关系是 $y_n=z_n-x_n$ 。这个式子告诉我们，如果我们知道了 LNRR 的一个解$z_n$，那么可以通过减去对应的 LHRR 解 $x_n$ ，得到一个与 LHRR 相关的解 $y_n$ 。因此，我们可以使用这个通解公式 $z_n=x_n+y_n$ 来求解 LNRR 。

总的来说，通解就是一类函数的一般形式，它包含了所有可能的特解。通解不是唯一的，因为可以通过加上任意一个与 LHRR 相关的解，得到另一个解。在实际应用中，我们需要选择一个特定的通解，以满足问题的初始条件或其他要求。