组合数学中的组合序列的递推关系与生成函数求解

字数 3462 2025-12-15 19:53:44

组合数学中的组合序列的递推关系与生成函数求解

我们先从最基础的“序列”概念开始，逐步深入到如何用代数方法系统地求解递推关系。

组合序列与递推关系：在组合数学中，组合序列 \(a_0, a_1, a_2, \dots\) 通常用于计数具有某种结构的、规模为 \(n\) 的对象个数。一个递推关系定义了序列项之间的依赖关系。例如，斐波那契数列 \(F_n\) 由 \(F_{n} = F_{n-1} + F_{n-2}\)（对 \(n \ge 2\)）定义，初始条件为 \(F_0 = 0, F_1 = 1\)。这是常系数线性齐次递推关系的一个经典例子，其一般形式为：

\[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}, \quad \text{对于 } n \ge k \]

其中 \(c_1, \dots, c_k\) 是常数，且 \(c_k \ne 0\)。

生成函数：从序列到形式幂级数：为了用强大的代数工具处理序列，我们引入其普通生成函数。它是一个形式幂级数，将所有序列项“打包”：

\[ A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots \]

这里 \(x\) 是一个形式变量，我们暂时不关心其收敛性，而只关注其代数运算性质。生成函数的核心思想是，序列的递推关系可以翻译为生成函数满足的代数方程。

用生成函数求解常系数线性递推：我们以求解斐波那契数列为例，演示标准步骤。
- 步骤一：建立生成函数方程。
  令 \(F(x) = \sum_{n\ge0} F_n x^n\)。利用递推式 \(F_n = F_{n-1} + F_{n-2}\) 对 \(n \ge 2\) 成立，我们从 \(F(x)\) 中减去较低的项以对齐指标：

\[ \begin{aligned} F(x) &= F_0 + F_1 x + \sum_{n\ge2} F_n x^n \\ &= 0 + 1 \cdot x + \sum_{n\ge2} (F_{n-1} + F_{n-2}) x^n \\ &= x + \sum_{n\ge2} F_{n-1} x^n + \sum_{n\ge2} F_{n-2} x^n \\ &= x + x\sum_{n\ge2} F_{n-1} x^{n-1} + x^2\sum_{n\ge2} F_{n-2} x^{n-2} \\ &= x + x\sum_{m\ge1} F_m x^m + x^2\sum_{k\ge0} F_k x^k \quad (\text{令 } m=n-1, k=n-2)\\ &= x + x(F(x) - F_0) + x^2 F(x) \\ &= x + x F(x) + x^2 F(x). \end{aligned} \]

于是我们得到关于生成函数 \(F(x)\) 的线性方程：

\[ F(x) = x + xF(x) + x^2 F(x)。 \]

*   **步骤二：求解生成函数的闭形式**。

将含 \(F(x)\) 的项合并：

\[ F(x) - xF(x) - x^2 F(x) = x \quad \Rightarrow \quad (1 - x - x^2)F(x) = x。 \]

    因此，

\[ F(x) = \frac{x}{1 - x - x^2}。 \]

    这个有理函数表达式就是斐波那契数列生成函数的闭形式。

*   **步骤三：从闭形式提取通项公式（部分分式分解）**。

我们希望将 \(F(x)\) 重新展开为幂级数以读取系数 \(F_n\)。首先对分母因式分解：令 \(1 - x - x^2 = 0\) 的解为 \(\phi = \frac{1+\sqrt{5}}{2}\) 和 \(\hat{\phi} = \frac{1-\sqrt{5}}{2}\)，满足 \(\phi + \hat{\phi} = 1, \phi \hat{\phi} = -1\)。于是：

\[ 1 - x - x^2 = - (x^2 + x - 1) = - (x - \phi)(x - \hat{\phi}) = (\phi - x)(1 - \phi x / \phi) \text{ 等形式，但更直接作部分分式分解：} \]

设存在常数 \(A, B\) 使得：

\[ \frac{x}{1 - x - x^2} = \frac{A}{1 - \phi x} + \frac{B}{1 - \hat{\phi} x}。 \]

通分后比较分子：\(x = A(1 - \hat{\phi} x) + B(1 - \phi x) = (A+B) - (A\hat{\phi} + B\phi)x\)。
比较系数得方程组：

\[ \begin{cases} A + B = 0, \\ -(A\hat{\phi} + B\phi) = 1。 \end{cases} \]

由第一式 \(B = -A\)，代入第二式：\(-A(\hat{\phi} - \phi) = 1\)。注意到 \(\phi - \hat{\phi} = \sqrt{5}\)，所以 \(A = \frac{1}{\phi - \hat{\phi}} = \frac{1}{\sqrt{5}}\)，\(B = -\frac{1}{\sqrt{5}}\)。
因此，

\[ F(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi x} - \frac{1}{1 - \hat{\phi} x} \right)。 \]

*   **步骤四：利用几何级数展开，得到通项**。

因为 \(\frac{1}{1 - r x} = \sum_{n\ge0} r^n x^n\)，所以：

\[ F(x) = \frac{1}{\sqrt{5}} \sum_{n\ge0} (\phi^n - \hat{\phi}^n) x^n。 \]

比较 \(x^n\) 的系数，即得比内公式：

\[ F_n = \frac{1}{\sqrt{5}} (\phi^n - \hat{\phi}^n)。 \]

一般理论：特征多项式法：对于一般的常系数线性齐次递推 \(a_n = c_1 a_{n-1} + \dots + c_k a_{n-k}\)，上述生成函数方法可系统化。其生成函数为有理函数 \(A(x) = P(x) / (1 - c_1 x - \dots - c_k x^k)\)，其中 \(P(x)\) 由初始条件决定。分母多项式 \(1 - c_1 x - \dots - c_k x^k\) 的倒数 \(x^k - c_1 x^{k-1} - \dots - c_k\) 称为递推的特征多项式。特征方程的根 \(r_1, \dots, r_k\) 决定了通解形式：若根互异，则 \(a_n = \alpha_1 r_1^n + \dots + \alpha_k r_k^n\)，系数 \(\alpha_i\) 由初始条件确定。这正是从生成函数的部分分式分解得到的结论。
扩展到更复杂的情形：此方法可推广到非齐次递推（如 \(a_n = c_1 a_{n-1} + f(n)\)）和带有多项式系数的线性递推（例如，卡特兰数的递推 \(C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}\) 导致其生成函数满足二次方程 \(C(x) = 1 + x C(x)^2\)）。后者通常导出生成函数的代数方程，求解后需用广义二项式定理或复分析技巧（如拉格朗日反演）提取系数。

通过将组合序列的递推关系编码为生成函数的代数方程，我们得以运用强大的分析工具求解通项、分析渐近性质（正如你已学过的“组合序列的渐近性质”），这体现了生成函数作为组合分析与代数桥梁的核心作用。

组合数学中的组合序列的递推关系与生成函数求解我们先从最基础的“序列”概念开始，逐步深入到如何用代数方法系统地求解递推关系。组合序列与递推关系：在组合数学中，组合序列 \( a_ 0, a_ 1, a_ 2, \dots \) 通常用于计数具有某种结构的、规模为 \( n \) 的对象个数。一个递推关系定义了序列项之间的依赖关系。例如，斐波那契数列 \( F_ n \) 由 \( F_ {n} = F_ {n-1} + F_ {n-2} \)（对 \( n \ge 2 \)）定义，初始条件为 \( F_ 0 = 0, F_ 1 = 1 \)。这是常系数线性齐次递推关系的一个经典例子，其一般形式为： \[ a_ n = c_ 1 a_ {n-1} + c_ 2 a_ {n-2} + \dots + c_ k a_ {n-k}, \quad \text{对于 } n \ge k \] 其中 \( c_ 1, \dots, c_ k \) 是常数，且 \( c_ k \ne 0 \)。生成函数：从序列到形式幂级数：为了用强大的代数工具处理序列，我们引入其普通生成函数。它是一个形式幂级数，将所有序列项“打包”： \[ A(x) = \sum_ {n=0}^{\infty} a_ n x^n = a_ 0 + a_ 1 x + a_ 2 x^2 + \dots \] 这里 \( x \) 是一个形式变量，我们暂时不关心其收敛性，而只关注其代数运算性质。生成函数的核心思想是，序列的递推关系可以翻译为生成函数满足的代数方程。用生成函数求解常系数线性递推：我们以求解斐波那契数列为例，演示标准步骤。步骤一：建立生成函数方程。令 \( F(x) = \sum_ {n\ge0} F_ n x^n \)。利用递推式 \( F_ n = F_ {n-1} + F_ {n-2} \) 对 \( n \ge 2 \) 成立，我们从 \( F(x) \) 中减去较低的项以对齐指标： \[ \begin{aligned} F(x) &= F_ 0 + F_ 1 x + \sum_ {n\ge2} F_ n x^n \\ &= 0 + 1 \cdot x + \sum_ {n\ge2} (F_ {n-1} + F_ {n-2}) x^n \\ &= x + \sum_ {n\ge2} F_ {n-1} x^n + \sum_ {n\ge2} F_ {n-2} x^n \\ &= x + x\sum_ {n\ge2} F_ {n-1} x^{n-1} + x^2\sum_ {n\ge2} F_ {n-2} x^{n-2} \\ &= x + x\sum_ {m\ge1} F_ m x^m + x^2\sum_ {k\ge0} F_ k x^k \quad (\text{令 } m=n-1, k=n-2)\\ &= x + x(F(x) - F_ 0) + x^2 F(x) \\ &= x + x F(x) + x^2 F(x). \end{aligned} \] 于是我们得到关于生成函数 \( F(x) \) 的线性方程： \[ F(x) = x + xF(x) + x^2 F(x)。 \] 步骤二：求解生成函数的闭形式。将含 \( F(x) \) 的项合并： \[ F(x) - xF(x) - x^2 F(x) = x \quad \Rightarrow \quad (1 - x - x^2)F(x) = x。 \] 因此， \[ F(x) = \frac{x}{1 - x - x^2}。 \] 这个有理函数表达式就是斐波那契数列生成函数的闭形式。步骤三：从闭形式提取通项公式（部分分式分解）。我们希望将 \( F(x) \) 重新展开为幂级数以读取系数 \( F_ n \)。首先对分母因式分解：令 \( 1 - x - x^2 = 0 \) 的解为 \( \phi = \frac{1+\sqrt{5}}{2} \) 和 \( \hat{\phi} = \frac{1-\sqrt{5}}{2} \)，满足 \( \phi + \hat{\phi} = 1, \phi \hat{\phi} = -1 \)。于是： \[ 1 - x - x^2 = - (x^2 + x - 1) = - (x - \phi)(x - \hat{\phi}) = (\phi - x)(1 - \phi x / \phi) \text{ 等形式，但更直接作部分分式分解：} \] 设存在常数 \( A, B \) 使得： \[ \frac{x}{1 - x - x^2} = \frac{A}{1 - \phi x} + \frac{B}{1 - \hat{\phi} x}。 \] 通分后比较分子：\( x = A(1 - \hat{\phi} x) + B(1 - \phi x) = (A+B) - (A\hat{\phi} + B\phi)x \)。比较系数得方程组： \[ \begin{cases} A + B = 0, \\ -(A\hat{\phi} + B\phi) = 1。 \end{cases} \] 由第一式 \( B = -A \)，代入第二式：\( -A(\hat{\phi} - \phi) = 1 \)。注意到 \( \phi - \hat{\phi} = \sqrt{5} \)，所以 \( A = \frac{1}{\phi - \hat{\phi}} = \frac{1}{\sqrt{5}} \)，\( B = -\frac{1}{\sqrt{5}} \)。因此， \[ F(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi x} - \frac{1}{1 - \hat{\phi} x} \right)。 \] 步骤四：利用几何级数展开，得到通项。因为 \( \frac{1}{1 - r x} = \sum_ {n\ge0} r^n x^n \)，所以： \[ F(x) = \frac{1}{\sqrt{5}} \sum_ {n\ge0} (\phi^n - \hat{\phi}^n) x^n。 \] 比较 \( x^n \) 的系数，即得比内公式： \[ F_ n = \frac{1}{\sqrt{5}} (\phi^n - \hat{\phi}^n)。 \] 一般理论：特征多项式法：对于一般的常系数线性齐次递推 \( a_ n = c_ 1 a_ {n-1} + \dots + c_ k a_ {n-k} \)，上述生成函数方法可系统化。其生成函数为有理函数 \( A(x) = P(x) / (1 - c_ 1 x - \dots - c_ k x^k) \)，其中 \( P(x) \) 由初始条件决定。分母多项式 \( 1 - c_ 1 x - \dots - c_ k x^k \) 的倒数 \( x^k - c_ 1 x^{k-1} - \dots - c_ k \) 称为递推的特征多项式。特征方程的根 \( r_ 1, \dots, r_ k \) 决定了通解形式：若根互异，则 \( a_ n = \alpha_ 1 r_ 1^n + \dots + \alpha_ k r_ k^n \)，系数 \( \alpha_ i \) 由初始条件确定。这正是从生成函数的部分分式分解得到的结论。扩展到更复杂的情形：此方法可推广到非齐次递推（如 \( a_ n = c_ 1 a_ {n-1} + f(n) \)）和带有多项式系数的线性递推（例如，卡特兰数的递推 \( C_ n = \sum_ {i=0}^{n-1} C_ i C_ {n-1-i} \) 导致其生成函数满足二次方程 \( C(x) = 1 + x C(x)^2 \)）。后者通常导出生成函数的代数方程，求解后需用广义二项式定理或复分析技巧（如拉格朗日反演）提取系数。通过将组合序列的递推关系编码为生成函数的代数方程，我们得以运用强大的分析工具求解通项、分析渐近性质（正如你已学过的“组合序列的渐近性质”），这体现了生成函数作为组合分析与代数桥梁的核心作用。