引言
如何计算从n种物品中选取k个（允许重复）的方案数？如何求斐波那契数列的通项公式？如何优雅地处理复杂的组合计数问题？这些看似不相关的难题，都能通过生成函数（Generating Functions）这一强大的数学工具统一解决。生成函数将离散的数列嵌入到连续的多项式或幂级数中，把递推关系转化为代数方程，把卷积运算转化为多项式乘法，从而大幅降低问题的复杂度。本文将从普通生成函数和指数生成函数入手，深入讲解其原理，并用Java实现多项式运算与组合计数框架。
数学原理
普通生成函数（OGF）
对于数列 a₀, a₁, a₂, ...，其普通生成函数定义为：
$$A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n$$
核心性质：两个生成函数的乘积对应数列的卷积。
若 C(x) = A(x) * B(x)，则 c_n = sum_{k=0}^{n} a_k * b_{n-k}。
指数生成函数（EGF）
对于数列 a₀, a₁, a₂, ...，其指数生成函数定义为：
$$A(x) = a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \cdots = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$
核心性质：EGF的乘积对应带标签组合结构的拼接。
经典示例
- 常数列
{1, 1, 1, ...}的OGF：1/(1-x) - 斐波那契 的OGF：
F(x) = x/(1-x-x²) - 卡特兰数 的OGF：
C(x) = (1 - sqrt(1-4x)) / (2x)
核心应用：组合计数
问题：从n种不同物品中选取k个，每种物品可以选任意多个（包括0个），求方案数。
生成函数解法：每种物品对应 1 + x + x² + x³ + ... = 1/(1-x)，n种物品的生成函数为 (1-x)^(-n)。展开后 x^k 的系数即为答案：C(n+k-1, k)。
Java实现
import java.util.*;
/**
* 生成函数工具类：支持多项式运算、OGF与EGF转换、组合计数
* 所有运算在模MOD下进行
*/
public class GeneratingFunctions {
private static final long MOD = 1_000_000_007L;
/**
* 多项式乘法：朴素O(n^2)算法
* 适用于小规模多项式
*/
public static long[] polynomialMultiply(long[] a, long[] b) {
int n = a.length, m = b.length;
long[] res = new long[n + m - 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[i + j] = (res[i + j] + a[i] * b[j]) % MOD;
}
}
return res;
}
/**
* 多项式快速幂：计算poly(x)^exp，保留前maxDegree项
* 使用二进制分解，时间复杂度O(maxDegree^2 * log(exp))
*/
public static long[] polynomialPower(long[] poly, long exp, int maxDegree) {
// 结果初始化为1（即[1, 0, 0, ...]）
long[] result = new long[maxDegree + 1];
result[0] = 1;
long[] base = Arrays.copyOf(poly, Math.min(poly.length, maxDegree + 1));
while (exp > 0) {
if ((exp & 1) == 1) {
result = truncate(polynomialMultiply(result, base), maxDegree);
}
base = truncate(polynomialMultiply(base, base), maxDegree);
exp >>= 1;
}
return result;
}
/**
* 截断多项式，只保留前maxDegree+1项
*/
private static long[] truncate(long[] poly, int maxDegree) {
if (poly.length <= maxDegree + 1) return poly;
return Arrays.copyOf(poly, maxDegree + 1);
}
/**
* 组合计数：从n种物品中选k个（每种可选无限次）
* 等价于求(1 + x + x^2 + ...)^n = (1-x)^(-n) 中x^k的系数
* 答案为 C(n+k-1, k)
*/
public static long combinationsWithRepetition(int n, int k) {
// 使用生成函数方法验证
// 每种物品的OGF: 1 + x + x^2 + ... 的前k+1项近似
long[] single = new long[k + 1];
Arrays.fill(single, 1); // [1, 1, 1, ..., 1] (k+1个)
long[] result = polynomialPower(single, n, k);
return result[k];
}
/**
* 带限制的组合计数：第i种物品最多选maxCount[i]个
* 生成函数为 product_i (1 + x + ... + x^maxCount[i])
*/
public static long boundedCombinations(int[] maxCount, int target) {
// 动态规划思想，逐个物品乘入生成函数
long[] gf = new long[target + 1];
gf[0] = 1; // 空集的生成函数
for (int limit : maxCount) {
// 当前物品的生成函数: 1 + x + x^2 + ... + x^limit
long[] item = new long[Math.min(limit, target) + 1];
Arrays.fill(item, 1);
gf = truncate(polynomialMultiply(gf, item), target);
}
return gf[target];
}
/**
* 斐波那契数列通项：利用生成函数 F(x) = x / (1 - x - x^2)
* 通过递推计算前n项
*/
public static long[] fibonacciOGF(int n) {
long[] fib = new long[n];
if (n > 0) fib[0] = 0;
if (n > 1) fib[1] = 1;
for (int i = 2; i < n; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
return fib;
}
/**
* 指数生成函数：计算e^x的前n项展开
* e^x = sum_{k=0}^{∞} x^k / k!
* 返回OGF形式（系数为1/k!）
*/
public static long[] exponentialEGF(int n) {
long[] egf = new long[n];
long fact = 1;
for (int i = 0; i < n; i++) {
if (i > 0) fact = fact * i % MOD;
egf[i] = modInverse(fact, MOD);
}
return egf;
}
/**
* 错位排列（derangement）的EGF计算
* D(x) = e^(-x) / (1-x) 的EGF形式
* D_n = n! * sum_{k=0}^{n} (-1)^k / k!
*/
public static long derangement(int n) {
long result = 0;
long fact = 1;
long sign = 1;
for (int k = 0; k <= n; k++) {
if (k > 0) fact = fact * k % MOD;
long term = sign * modInverse(fact, MOD) % MOD;
result = (result + term + MOD) % MOD;
sign = -sign;
}
// 乘以n!
long nFact = 1;
for (int i = 2; i <= n; i++) nFact = nFact * i % MOD;
return result * nFact % MOD;
}
/**
* 斯特林数与普通生成函数的关系
* sum_{n} S(n,k) x^n = x^k / ((1-x)(1-2x)...(1-kx))
* 本方法计算小规模的斯特林数OGF
*/
public static long[] stirling2ndOGF(int k, int maxN) {
// 分母: (1-x)(1-2x)...(1-kx)
long[] denom = new long[]{1};
for (int i = 1; i <= k; i++) {
// (1 - i*x) 对应多项式 [1, -i]
long[] factor = new long[]{1, (MOD - i) % MOD};
denom = truncate(polynomialMultiply(denom, factor), maxN);
}
// 分子: x^k
long[] numer = new long[maxN + 1];
if (k <= maxN) numer[k] = 1;
// 需要计算 numer / denom，这里用级数展开近似
// 实际上可以通过递推直接求，这里展示思想
return polynomialMultiply(numer, seriesInverse(denom, maxN));
}
/**
* 级数求逆：给定A(x)且A[0]=1，求B(x)使得A(x)*B(x)=1
* 使用牛顿迭代法，时间复杂度O(n^2)
*/
public static long[] seriesInverse(long[] a, int maxDegree) {
long[] b = new long[maxDegree + 1];
b[0] = modInverse(a[0], MOD);
for (int n = 1; n <= maxDegree; n++) {
long sum = 0;
for (int i = 1; i <= n && i < a.length; i++) {
sum = (sum + a[i] * b[n - i]) % MOD;
}
b[n] = (MOD - sum) * b[0] % MOD;
}
return b;
}
// ============ 辅助函数 ============
private static long modPow(long base, long exp, long mod) {
long result = 1 % mod;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
private static long modInverse(long a, long mod) {
return modPow(a, mod - 2, mod);
}
private static long combination(int n, int k) {
if (k < 0 || k > n) return 0;
long num = 1, den = 1;
for (int i = 0; i < k; i++) {
num = num * (n - i) % MOD;
den = den * (i + 1) % MOD;
}
return num * modInverse(den, MOD) % MOD;
}
public static void main(String[] args) {
// 测试1：多项式乘法
long[] a = {1, 2, 3}; // 1 + 2x + 3x^2
long[] b = {1, 1, 1}; // 1 + x + x^2
long[] c = polynomialMultiply(a, b);
System.out.println("多项式乘法: " + Arrays.toString(c));
// 期望: [1, 3, 6, 5, 3]
// 测试2：可重复组合
System.out.println("\n=== 可重复组合 C'(n,k) = C(n+k-1, k) ===");
for (int n = 2; n <= 5; n++) {
for (int k = 0; k <= 5; k++) {
long gfResult = combinationsWithRepetition(n, k);
long formula = combination(n + k - 1, k);
System.out.printf("n=%d k=%d: GF=%d, 公式=%d%n", n, k, gfResult, formula);
}
}
// 测试3：带限制的组合
System.out.println("\n=== 带限制组合 ===");
int[] limits = {2, 3, 1}; // 三种物品，最多分别选2,3,1个
for (int k = 0; k <= 6; k++) {
System.out.println("选" + k + "个的方案数: " + boundedCombinations(limits, k));
}
// 测试4：错位排列
System.out.println("\n=== 错位排列 D_n ===");
for (int n = 1; n <= 8; n++) {
System.out.println("D_" + n + " = " + derangement(n));
}
// 测试5：斐波那契数列
System.out.println("\n=== 斐波那契数列 ===");
long[] fib = fibonacciOGF(12);
System.out.println(Arrays.toString(fib));
// 测试6：级数求逆
System.out.println("\n=== 级数求逆 ===");
long[] series = {1, 1, 1}; // 1 + x + x^2
long[] inv = seriesInverse(series, 5);
System.out.println("原级数: " + Arrays.toString(series));
System.out.println("逆级数: " + Arrays.toString(inv));
// 验证: (1+x+x^2) * inv 的前几项应接近[1,0,0,...]
long[] check = polynomialMultiply(series, inv);
System.out.println("验证乘积: " + Arrays.toString(check));
}
}
复杂度分析
- 多项式乘法（朴素）：
O(n*m)，适用于小规模多项式。 - 多项式快速幂：
O(d² log exp)，其中d为保留的最高次数。 - 级数求逆：
O(n²)，基于牛顿迭代可优化至O(n log n)（配合FFT/NTT）。 - 带限制组合：
O(m * t²)，m为物品种类数，t为目标总数。
应用场景
- 组合计数：从复杂约束下的选择方案数
- 递推关系求解：将递推转化为有理函数，提取通项公式
- 概率生成函数：分析随机变量的期望、方差等数字特征
- 形式幂级数：编码理论、信号处理中的卷积运算
总结
生成函数是连接离散组合与连续分析的桥梁，它将复杂的计数问题转化为优雅的多项式运算。本文实现了多项式乘法、快速幂、级数求逆等核心操作，展示了可重复组合、带限制组合、错位排列等经典问题的生成函数解法。掌握生成函数，将极大提升解决高级组合计数问题的能力。
