《组合数学》 §2.1 学习笔记

2.1.1 ~ 2.1.2

略。

定理 2.2.3

定义斐波那契数列

$$f_n = \begin{cases} 0 & n = 0 \\[8pt]1 & n = 1 \\[8pt]f_{n-1} + f_{n-2} & n \ge 2 \end{cases}$$

当 $n \ge 0$ 时有

$$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$$

证明略。

例 2.1.4

略。

定义 2.1.5

称数列 $\{h_n\}_{n=0}^{\infty}$ 满足 $k$ 阶常系数线性齐次递推关系，若对所有的 $n \ge k$ ，有

$$h_n = a_1h_{n-1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k}$$

其中 $a_k \ne 0~(k \ge 1)$ 为常数。

设 $q$ 为非零复数，容易看出，$h_n = q^n$ 是上述 $k$ 阶常系数线性齐次递推关系的解当且仅当 $q$ 是 $k$ 次多项式方程

$$g(x) = x^k - a_1x^{k-1} - \cdots - a_{k-1}x - a_k = 0$$

的根。称方程 $g(x) = x^k - a_1x^{k-1} - \cdots - a_{k-1}x - a_k = 0$ 为上述常系数线性齐次递推关系的特征方程。

定理 2.1.6

若 $k$ 阶常系数线性齐次递推关系

$$h_n = a_1h_{n-1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k},\quad a_k \ne 0~(k \ge 1)$$

的特征方程 $g(x) = 0$ 有 $k$ 个互不相同的根 $q_1,q_2,\cdots,q_k$ ，则

$$h_n = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n,\quad n \ge 0$$

是下述意义下的一般解：无论给定怎样的初始值 $h_0,h_1,\cdots h_{k-1}$ ，

都存在相应的常数 $c_1,c_2,\cdots c_k$ 使得上式是满足递推关系和初始条件的为一数列。

证明略。

例 2.1.7

由字母 $\mathtt{a,b,c}$ 组成的长度为 $n$ 的字符串在通信信道上传送，满足条件：

不得有两个 $a$ 连续出现在任一字符串中。确定通信信道允许传送的字符串个数。

解 记 $h_n$ 为允许传送的长度为 $n$ 的字符串个数，则 $h_1 = 3,h_2 = 8$ 。

考虑长度为 $n$ 的最后一个符号，若其不为 $\tt a$ ，则有 $2h_{n-1}$ 个字符串；

反之则倒数第二个符号不一定是 $\tt{a}$ ，故此时有 $2h_{n-2}$ 个字符串。故当 $n \ge 2$ 时，有

$$h_n = 2h_{n-1} + 2h_{n-2}$$

不妨定义 $h_0 = 1$ ，因为这也满足上述递推关系。解特征方程

$$x^2 - 2x - 2=0$$

得到根

$$q_1 = 1 + \sqrt{3},\quad q_2 = 1 - \sqrt{3}$$

于是可设 $h_n$ 为

$$h_n = c_1(1 + \sqrt{3})^n + c_2(1 - \sqrt{3})^n$$

其中 $c_1,c_2$ 为待定系数。通过初始条件 $h_0 = 1,h_1 = 3$ 解得

$$c_1 = \frac{2+\sqrt{3}}{2\sqrt{3}},\quad c_2 = \frac{-2 + \sqrt{3}}{2\sqrt{3}}$$

故

$$h_n = \frac{2 + \sqrt{3}}{2\sqrt{3}}(1 + \sqrt{3})^n + \frac{-1+\sqrt{3}}{2\sqrt{3}}(1 - \sqrt{3})^n$$

下面给出比定理 2.1.6 更为一般的结论

定理 2.1.8

设 $k$ 阶常系数线性齐次递推关系

$$h_n = a_1h_{n-1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k},\quad a_k \ne 0~(k \ge 1)$$

的特征方程

$$g(x) = x^k - a_1x^{k-1} - \cdots - a_{k-1}x - a_k = 0$$

有互异根 $q_1,q_2,\cdots,q_t$ ，其中 $q_i$ 是 $s_i$ 重根 $(1 \le i \le t,s_1 + s_2 + \cdots s_t = k)$ ，则

$$h_n = \sum_{i=1}^tP_i(n)q_i^n$$

是该递推关系的一般解，其中 $P_i(n)$ 是关于 $n$ 的次数小于 $s_i$ 的多项式。

例 2.1.9

求解线性齐次递推关系

$$h_n = -h_{n-1} + 3h_{n-2} + 5h_{n-3} + 2h_{n-4},\quad n \ge 4$$

初始条件为 $h_0 = 1,h_1 = 0,h_2 = 1,h_3 = 2$ 。

解 由上述定理，解特征方程

$$x^4 + x^3 - 3x^2 - 5x - 2 = 0$$

得到根 $q_1 = -1$ （3重）和 $q_2 = 2$ 。于是可设 $h_n$ 为

$$h_n = (c_1n^2 + c_2n + c_3)(-1)^n + c_42^n$$

其中 $c_1,c_2,c_3,c_4$ 为常数。通过初始条件 $h_0 = 1,h_1 = 0,h_2=1,h_3=2$ 解得

$$c_1 = 0,\quad c_2 = -\frac{3}{9},\quad c_3 = \frac{7}{9},\quad c_4 = \frac{2}{9}$$

所以

$$h_n = \left(\frac{7}{9} - \frac{3n}{9}\right)(-1)^n + \frac{2}{9}\cdot 2^n$$