《组合数学》 §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 \]