跳到主要内容

递推关系与生成函数

递推关系描述“当前状态由过去状态决定”的规律，是离散数学、算法分析与组合计数中的核心工具。

1. 递推关系基础​

递推关系由两部分构成：

  • 递推式（状态转移）；
  • 初值条件（边界）。

示例：斐波那契数列

Fn=Fn−1+Fn−2,F0=0, F1=1. F_n=F_{n-1}+F_{n-2},\quad F_0=0,\ F_1=1.

2. 一阶线性递推​

一般形式：

an=ran−1+b. a_n=ra_{n-1}+b.

若 r≠1r\neq 1，通解可写为

an=rna0+brn−1r−1. a_n=r^n a_0+b\frac{r^n-1}{r-1}.

例题 1​

给定 an=2an−1+3, a0=1a_n=2a_{n-1}+3,\ a_0=1，求 ana_n。

解：

an=2n⋅1+3(2n−1)=4⋅2n−3. a_n=2^n\cdot 1+3(2^n-1)=4\cdot2^n-3.

3. 二阶常系数齐次递推​

一般形式：

an=c1an−1+c2an−2. a_n=c_1a_{n-1}+c_2a_{n-2}.

令特征方程

λ2−c1λ−c2=0. \lambda^2-c_1\lambda-c_2=0.
  • 两个不同根 λ1,λ2\lambda_1,\lambda_2：an=Aλ1n+Bλ2na_n=A\lambda_1^n+B\lambda_2^n；
  • 重根 λ\lambda：an=(A+Bn)λna_n=(A+Bn)\lambda^n。

例题 2（斐波那契闭式）​

对 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}，特征方程为

λ2−λ−1=0. \lambda^2-\lambda-1=0.

两根为

ϕ=1+52, ψ=1−52. \phi=\frac{1+\sqrt5}{2},\ \psi=\frac{1-\sqrt5}{2}.

故

Fn=ϕn−ψn5. F_n=\frac{\phi^n-\psi^n}{\sqrt5}.

4. 非齐次递推与待定系数法​

例题 3​

求解

an−3an−1=2n,a0=0. a_n-3a_{n-1}=2^n,\quad a_0=0.

解：

  1. 齐次解：an(h)=C⋅3na_n^{(h)}=C\cdot3^n。
  2. 设特解 an(p)=k⋅2na_n^{(p)}=k\cdot2^n，代入得
k2n−3k2n−1=2n⇒−k2=1⇒k=−2. k2^n-3k2^{n-1}=2^n\Rightarrow -\frac{k}{2}=1\Rightarrow k=-2.
  1. 总解：an=C3n−2⋅2na_n=C3^n-2\cdot2^n。
  2. 用 a0=0a_0=0 得 C=2C=2。

所以

an=2⋅3n−2n+1. a_n=2\cdot3^n-2^{n+1}.

5. 普通生成函数 (OGF) 详解​

对序列 {an}\{a_n\}，其 OGF 为 A(x)=∑n=0∞anxnA(x) = \sum_{n=0}^\infty a_n x^n。

5.1 核心性质与运算​

运算序列生成函数
线性性质αan+βbn\alpha a_n + \beta b_nαA(x)+βB(x)\alpha A(x) + \beta B(x)
平移（右移）0,…,0,a0,a1,…0, \dots, 0, a_0, a_1, \dotsxkA(x)x^k A(x)
差分an−an−1a_n - a_{n-1}(1−x)A(x)(1-x)A(x)
前缀和∑i=0nai\sum_{i=0}^n a_iA(x)1−x\frac{A(x)}{1-x}
卷积∑i=0naibn−i\sum_{i=0}^n a_i b_{n-i}A(x)B(x)A(x)B(x)
导数(n+1)an+1(n+1)a_{n+1}A′(x)A'(x)

5.2 常用闭式映射​

  • 11−x=∑n=0∞xn\frac{1}{1-x} = \sum_{n=0}^\infty x^n (序列 1,1,1,…1, 1, 1, \dots)
  • 1(1−x)k=∑n=0∞(n+k−1k−1)xn\frac{1}{(1-x)^k} = \sum_{n=0}^\infty \binom{n+k-1}{k-1} x^n (多重集组合)
  • (1+x)n=∑k=0n(nk)xk(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k (二项式)

例题 5：受限计数​

求用 1分、2分、5分硬币组成 nn 分钱的方案数。

解：生成函数为 A(x)=(1+x+x2+… )(1+x2+x4+… )(1+x5+x10+… )A(x) = (1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^5+x^{10}+\dots) =1(1−x)(1−x2)(1−x5)= \frac{1}{(1-x)(1-x^2)(1-x^5)}。 方案数即为 xnx^n 的系数。

6. 指数生成函数 (EGF)​

对于排列问题（元素有顺序），使用 EGF：

A^(x)=∑n=0∞anxnn!.\hat{A}(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}.

6.1 核心性质：指数卷积​

若 an,bna_n, b_n 分别对应 A^(x),B^(x)\hat{A}(x), \hat{B}(x)，则 A^(x)B^(x)\hat{A}(x)\hat{B}(x) 对应序列：

cn=∑i=0n(ni)aibn−i.c_n = \sum_{i=0}^n \binom{n}{i} a_i b_{n-i}.

这恰好对应了“先从 nn 个位置选 ii 个放 aa，剩下的放 bb”的结构。

例题 6：错排再访​

错排序列的 EGF 为： D^(x)=e−x1−x\hat{D}(x) = \frac{e^{-x}}{1-x}。 通过展开 e−xe^{-x} 与 (1−x)−1(1-x)^{-1} 的乘积可直接得到 DnD_n 的通项公式。

7. 本章练习​

练习 1：递推求解​

求解 an=2an−1+an−2a_n = 2a_{n-1} + a_{n-2}，a0=0,a1=1a_0=0, a_1=1（白银分割比相关）。

Check Solution

特征方程 λ2−2λ−1=0\lambda^2 - 2\lambda - 1 = 0，解得 λ=1±2\lambda = 1 \pm \sqrt{2}。 通解 an=A(1+2)n+B(1−2)na_n = A(1+\sqrt{2})^n + B(1-\sqrt{2})^n。 代入初值得 an=(1+2)n−(1−2)n22a_n = \frac{(1+\sqrt{2})^n - (1-\sqrt{2})^n}{2\sqrt{2}}。

练习 2：OGF 展开​

求 1(1−x)3\frac{1}{(1-x)^3} 的 xnx^n 项系数。

Check Solution

根据广义二项式定理：(n+3−13−1)=(n+22)=(n+2)(n+1)2\binom{n+3-1}{3-1} = \binom{n+2}{2} = \frac{(n+2)(n+1)}{2}。

练习 3：染色问题（EGF 应用）​

用红、蓝、绿三种颜色涂 nn 个排成一行的格子，要求红色必须出现偶数次，求方案数。

Check Solution

红色的 EGF：ex+e−x2\frac{e^x + e^{-x}}{2}；蓝/绿的 EGF：exe^x。 总 EGF：G^(x)=ex+e−x2⋅ex⋅ex=12(e3x+ex)\hat{G}(x) = \frac{e^x + e^{-x}}{2} \cdot e^x \cdot e^x = \frac{1}{2}(e^{3x} + e^x)。 xn/n!x^n/n! 的系数为 12(3n+1)\frac{1}{2}(3^n + 1)。

练习 4：Catalan 数（思考题）​

Catalan 数的递推式为 Cn=∑i=0n−1CiCn−1−iC_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}。试写出其生成函数方程。

Check Solution

设 C(x)C(x) 为生成函数，则 C(x)=xC2(x)+1C(x) = x C^2(x) + 1。 解得 C(x)=1−1−4x2xC(x) = \frac{1 - \sqrt{1-4x}}{2x}。

7. 学习闭环​