覆盖集#

鸽子洞原理#

鸽子洞原理（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$ 个物体。

经典问题#

线性齐次递推关系式#

线性齐次递推关系式（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$ 成立。

特征根#

特征根（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 相关的解，得到另一个解。在实际应用中，我们需要选择一个特定的通解，以满足问题的初始条件或其他要求。