以序列计数问题为例浅谈生成函数运用

序列计数问题解析

问题描述

现有若干种颜色不同的骨牌，其中大小为 \(1 \times i\) 的骨牌共有 \(a_i\) 种，且每种骨牌都可以无限量使用。要求计算用这些骨牌不重叠地铺满一排 \(1 \times n\) 的方格，共有多少种方法（其中 \(a_i, n \leq 5000\)）。

基础生成函数定义

针对 “只选择一种骨牌” 的情况，定义基础生成函数 \(A(x)\) 为：

\(A(x) = \sum_{i=1}^{\infty} a_i x^i\)

其中 \(x^i\) 的系数 \(a_i\) 表示大小为 \(1 \times i\) 的骨牌的种类数。

答案生成函数的推导

方法一：递推推导（基于最后一个决策点）

通过分析铺满方格的最后一步选择的骨牌类型，建立递推关系，进而推导出答案生成函数。

步骤 i：建立递推关系

设 \(f(n)\) 表示铺满长度为 \(n\) 的方格的方案数。考虑最后一个放置的骨牌大小为 \(i\)（\(i \leq n\)），则该骨牌左侧需要铺满长度为 \(n-i\) 的方格，对应的方案数为 \(f(n-i)\)。由于大小为 \(i\) 的骨牌有 \(a_i\) 种选择，因此递推关系为：

\[f(n) = \sum_{i=1}^{n} a_i f(n-i) \]

（注：规定 \(f(0) = 1\)，表示长度为 0 的方格有 1 种空铺方案）。

步骤 ii：定义答案生成函数

设答案的生成函数 \(F(x)\) 为：

\[F(x) = \sum_{n=0}^{\infty} f(n) x^n \]

其中 \(x^n\) 的系数即为铺满长度为 \(n\) 的方格的方案数 \(f(n)\)。

步骤 iii：代入递推关系到生成函数

将递推关系代入生成函数 \(F(x)\)，可得：

\[F(x) = \sum_{n=0}^{\infty} \left( \sum_{i=1}^{n} a_i f(n-i) \right) x^n \]

当 \(n=0\) 时，内层求和 \(\sum_{i=1}^{0} a_i f(0-i)\) 为空（无意义），结合 \(f(0)=1\)，可拆分表达式为：

\[F(x) = f(0)x^0 + \sum_{n=1}^{\infty} \left( \sum_{i=1}^{n} a_i f(n-i) \right) x^n = 1 + \sum_{n=1}^{\infty} \left( \sum_{i=1}^{n} a_i f(n-i) \right) x^n \]

步骤 iv：指标反转与化简

交换求和顺序，先对骨牌大小 \(i\) 求和，再对剩余长度求和：

\[F(x) = 1 + \sum_{i=1}^{\infty} a_i \sum_{n=i}^{\infty} f(n-i) x^n \]

令 \(k = n - i\)（即 \(n = k + i\)），当 \(n = i\) 时 \(k = 0\)，因此内层对 \(n\) 的求和可转化为对 \(k\) 的求和：

\[\sum_{n=i}^{\infty} f(n-i) x^n = \sum_{k=0}^{\infty} f(k) x^{k+i} = x^i \sum_{k=0}^{\infty} f(k) x^k = x^i F(x) \]

代入上式可得：

\[F(x) = 1 + \sum_{i=1}^{\infty} a_i \cdot x^i F(x) = 1 + F(x) \sum_{i=1}^{\infty} a_i x^i \]

由于 \(\sum_{i=1}^{\infty} a_i x^i = A(x)\)，因此：\(F(x) = 1 + A(x) F(x)\)。

步骤 v：求解生成函数关系

对 \(F(x) = 1 + A(x) F(x)\) 移项并求解 \(F(x)\)：$$F(x) - A(x) F(x) = 1 \implies F(x) (1 - A(x)) = 1 \implies F(x) = \frac{1}{1 - A(x)}$$

方法二：直接组合意义分析

通过组合意义直接推导生成函数关系：

1. 子问题拆分：铺满长度为 \(n\) 的方格可按使用骨牌的数量 \(k\) 拆分子问题（\(k = 0, 1, 2, \dots\)），其中 \(k=0\) 对应空铺方案。当前的子问题是k个骨牌铺满长度n，第一个骨牌谁都可选，方案数生成函数A(x),第二个骨牌谁都可选，方案数生成函数A(x)，第三个骨牌谁都可选，方案数生成函数A(x)......

2. 单个骨牌的生成函数：选择任意一个骨牌的方案数生成函数为 \(A(x)\)，因此选择 \(k\) 个骨牌的方案数生成函数为 \(A(x)^k\)（乘法原理）。

3. 总生成函数：根据加法原理，所有可能骨牌数量的方案数生成函数之和为：

\[F(x) = \sum_{k=0}^{\infty} A(x)^k \]

1. 化简公式：根据无穷等比数列求和公式（当 \(|A(x)| < 1\) 时），上式可化简为：

\[F(x) = \frac{1}{1 - A(x)} \]

。

结论

铺满 \(1 \times n\) 方格的方案数为生成函数 $$F(x) = \frac{1}{1 - A(x)}$$ 中 \(x^n\) 的系数，即 \([x^n]F(x) = [x^n]\frac{1}{1 - A(x)}\)。