跳转至

# 普通生成函数

序列 𝑎 a 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

𝐹(𝑥)=∑𝑛 𝑎 𝑛 𝑥 𝑛 F(x)=∑n a n x n

𝑎 a 既可以是有穷序列，也可以是无穷序列．常见的例子（假设 𝑎 a 以 0 0 为起点）：

1. 序列 𝑎 =⟨1,2,3⟩a=⟨1,2,3⟩ 的普通生成函数是 1 +2 𝑥 +3 𝑥 2 1+2 x+3 x 2．
2. 序列 𝑎 =⟨1,1,1,⋯⟩a=⟨1,1,1,⋯⟩ 的普通生成函数是 ∑𝑛≥0 𝑥 𝑛∑n≥0 x n．
3. 序列 𝑎 =⟨1,2,4,8,1 6,⋯⟩a=⟨1,2,4,8,16,⋯⟩ 的生成函数是 ∑𝑛≥0 2 𝑛 𝑥 𝑛∑n≥0 2 n x n．
4. 序列 𝑎 =⟨1,3,5,7,9,⋯⟩a=⟨1,3,5,7,9,⋯⟩ 的生成函数是 ∑𝑛≥0(2 𝑛 +1)𝑥 𝑛∑n≥0(2 n+1)x n．

换句话说，如果序列 𝑎 a 有通项公式，那么它的普通生成函数的系数就是通项公式．

## 基本运算

考虑两个序列 𝑎,𝑏 a,b 的普通生成函数，分别为 𝐹(𝑥),𝐺(𝑥)F(x),G(x)．那么有

𝐹(𝑥)±𝐺(𝑥)=∑𝑛(𝑎 𝑛±𝑏 𝑛)𝑥 𝑛 F(x)±G(x)=∑n(a n±b n)x n

因此 𝐹(𝑥) ±𝐺(𝑥)F(x)±G(x) 是序列 ⟨𝑎 𝑛 ±𝑏 𝑛⟩⟨a n±b n⟩ 的普通生成函数．

考虑乘法运算，也就是卷积：

𝐹(𝑥)𝐺(𝑥)=∑𝑛 𝑥 𝑛 𝑛∑𝑖=0 𝑎 𝑖 𝑏 𝑛−𝑖 F(x)G(x)=∑n x n∑i=0 n a i b n−i

因此 𝐹(𝑥)𝐺(𝑥)F(x)G(x) 是序列 ⟨∑𝑛 𝑖=0 𝑎 𝑖 𝑏 𝑛−𝑖⟩⟨∑i=0 n a i b n−i⟩ 的普通生成函数．

## 封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简．

例如 ⟨1,1,1,⋯⟩⟨1,1,1,⋯⟩ 的普通生成函数 𝐹(𝑥) =∑𝑛≥0 𝑥 𝑛 F(x)=∑n≥0 x n，我们可以发现

𝐹(𝑥)𝑥+1=𝐹(𝑥)F(x)x+1=F(x)

那么解这个方程得到

𝐹(𝑥)=1 1−𝑥 F(x)=1 1−x

这就是 ∑𝑛≥0 𝑥 𝑛∑n≥0 x n 的封闭形式．

考虑等比数列 ⟨1,𝑝,𝑝 2,𝑝 3,𝑝 4,⋯⟩⟨1,p,p 2,p 3,p 4,⋯⟩ 的生成函数 𝐹(𝑥) =∑𝑛≥0 𝑝 𝑛 𝑥 𝑛 F(x)=∑n≥0 p n x n，有

𝐹(𝑥)𝑝 𝑥+1=𝐹(𝑥)𝐹(𝑥)=1 1−𝑝 𝑥 F(x)p x+1=F(x)F(x)=1 1−p x

等比数列的封闭形式与展开形式是常用的变换手段．

小练习

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）．难度是循序渐进的．

1. 𝑎 =⟨0,1,1,1,1,⋯⟩a=⟨0,1,1,1,1,⋯⟩．
2. 𝑎 =⟨1,0,1,0,1,⋯⟩a=⟨1,0,1,0,1,⋯⟩．
3. 𝑎 =⟨1,2,3,4,⋯⟩a=⟨1,2,3,4,⋯⟩．
4. 𝑎 𝑛 =(𝑚 𝑛)a n=(m n)（𝑚 m 是常数，𝑛 ≥0 n≥0）．
5. 𝑎 𝑛 =(𝑚+𝑛 𝑛)a n=(m+n n)（𝑚 m 是常数，𝑛 ≥0 n≥0）．

答案

第一个：

𝐹(𝑥)=∑𝑛≥1 𝑥 𝑛=𝑥 1−𝑥 F(x)=∑n≥1 x n=x 1−x

第二个：

𝐹(𝑥)=∑𝑛≥0 𝑥 2 𝑛=∑𝑛≥0(𝑥 2)𝑛=1 1−𝑥 2 F(x)=∑n≥0 x 2 n=∑n≥0(x 2)n=1 1−x 2

第三个（求导）：

𝐹(𝑥)=∑𝑛≥0(𝑛+1)𝑥 𝑛=∑𝑛≥1 𝑛 𝑥 𝑛−1=∑𝑛≥0(𝑥 𝑛)′=(1 1−𝑥)′=1(1−𝑥)2 F(x)=∑n≥0(n+1)x n=∑n≥1 n x n−1=∑n≥0(x n)′=(1 1−x)′=1(1−x)2

第四个（二项式定理）：

𝐹(𝑥)=∑𝑛≥0(𝑚 𝑛)𝑥 𝑛=(1+𝑥)𝑚 F(x)=∑n≥0(m n)x n=(1+x)m

第五个：

𝐹(𝑥)=∑𝑛≥0(𝑚+𝑛 𝑛)𝑥 𝑛=1(1−𝑥)𝑚+1 F(x)=∑n≥0(m+n n)x n=1(1−x)m+1

可以使用归纳法证明．

首先当 𝑚 =0 m=0 时，有 𝐹(𝑥) =1 1−𝑥 F(x)=1 1−x．

而当 𝑚 >0 m>0 时，有

1(1−𝑥)𝑚+1=1(1−𝑥)𝑚 1 1−𝑥=(∑𝑛≥0(𝑚+𝑛−1 𝑛)𝑥 𝑛)(∑𝑛≥0 𝑥 𝑛)=∑𝑛≥0 𝑥 𝑛 𝑛∑𝑖=0(𝑚+𝑖−1 𝑖)=∑𝑛≥0(𝑚+𝑛 𝑛)𝑥 𝑛 1(1−x)m+1=1(1−x)m 1 1−x=(∑n≥0(m+n−1 n)x n)(∑n≥0 x n)=∑n≥0 x n∑i=0 n(m+i−1 i)=∑n≥0(m+n n)x n

## 斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数．

斐波那契数列定义为 𝑎 0 =0,𝑎 1 =1,𝑎 𝑛 =𝑎 𝑛−1 +𝑎 𝑛−2 (𝑛 >1)a 0=0,a 1=1,a n=a n−1+a n−2(n>1)．设它的普通生成函数是 𝐹(𝑥)F(x)，那么根据它的递推式，我们可以类似地列出关于 𝐹(𝑥)F(x) 的方程：

𝐹(𝑥)=𝑥 𝐹(𝑥)+𝑥 2 𝐹(𝑥)−𝑎 0 𝑥+𝑎 1 𝑥+𝑎 0 F(x)=x F(x)+x 2 F(x)−a 0 x+a 1 x+a 0

那么解得

𝐹(𝑥)=𝑥 1−𝑥−𝑥 2 F(x)=x 1−x−x 2

那么接下来的问题是，如何求出它的展开形式？

### 展开方式一

不妨将 𝑥 +𝑥 2 x+x 2 当作一个整体，那么可以得到

𝐹(𝑥)=𝑥 1−(𝑥+𝑥 2)=𝑥∞∑𝑘=0(𝑥+𝑥 2)𝑘=𝑥∞∑𝑘=0 𝑘∑𝑖=0(𝑘 𝑖)𝑥 𝑘−𝑖(𝑥 2)𝑖=∞∑𝑘=0 𝑘∑𝑖=0(𝑘 𝑖)𝑥 𝑘+𝑖+1=∞∑𝑛=1⌊(𝑛−1)/2⌋∑𝑖=0(𝑛−𝑖−1 𝑖)𝑥 𝑛.F(x)=x 1−(x+x 2)=x∑k=0∞(x+x 2)k=x∑k=0∞∑i=0 k(k i)x k−i(x 2)i=∑k=0∞∑i=0 k(k i)x k+i+1=∑n=1∞∑i=0⌊(n−1)/2⌋(n−i−1 i)x n.

最后一步中，令 𝑛 =𝑘 +𝑖 +1 n=k+i+1 并更换求和顺序．由此，可以得到通项公式：

𝑎 𝑛=⌊(𝑛−1)/2⌋∑𝑖=0(𝑛−𝑖−1 𝑖).a n=∑i=0⌊(n−1)/2⌋(n−i−1 i).

这并不是我们熟知的有关黄金分割比的形式．

### 展开方式二

考虑求解一个待定系数的方程：

𝐴 1−𝑎 𝑥+𝐵 1−𝑏 𝑥=𝑥 1−𝑥−𝑥 2 A 1−a x+B 1−b x=x 1−x−x 2

通分得到

𝐴−𝐴 𝑏 𝑥+𝐵−𝑎 𝐵 𝑥(1−𝑎 𝑥)(1−𝑏 𝑥)=𝑥 1−𝑥−𝑥 2 A−A b x+B−a B x(1−a x)(1−b x)=x 1−x−x 2

待定项系数相等，我们得到

⎧{ { {⎨{ { {⎩𝐴+𝐵=0−𝐴 𝑏−𝑎 𝐵=1 𝑎+𝑏=1 𝑎 𝑏=−1{A+B=0−A b−a B=1 a+b=1 a b=−1

解得

⎧{ { { {⎨{ { { {⎩𝐴=1√5 𝐵=−1√5 𝑎=1+√5 2 𝑏=1−√5 2{A=1 5 B=−1 5 a=1+5 2 b=1−5 2

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

𝑥 1−𝑥−𝑥 2=∑𝑛≥0 𝑥 𝑛 1√5((1+√5 2)𝑛−(1−√5 2)𝑛)x 1−x−x 2=∑n≥0 x n 1 5((1+5 2)n−(1−5 2)n)

这也被称为斐波那契数列的另一个封闭形式（𝑥 1−𝑥−𝑥 2 x 1−x−x 2 是一个封闭形式）．

对于任意多项式 𝑃(𝑥),𝑄(𝑥)P(x),Q(x)，生成函数 𝑃(𝑥)𝑄(𝑥)P(x)Q(x) 的展开式都可以使用上述方法求出．在实际运用的过程中，我们往往先求出 𝑄(𝑥)Q(x) 的根，把分母表示为 ∏(1 −𝑝 𝑖 𝑥)𝑑 𝑖∏(1−p i x)d i 的形式，然后再求分子．

当对分母进行因式分解但有重根时，每有一个重根就要多一个分式，如考虑生成函数

𝐺(𝑥)=1(1−𝑥)(1−2 𝑥)2 G(x)=1(1−x)(1−2 x)2

的系数的通项公式，那么有

𝐺(𝑥)=𝑐 0 1−𝑥+𝑐 1 1−2 𝑥+𝑐 2(1−2 𝑥)2 G(x)=c 0 1−x+c 1 1−2 x+c 2(1−2 x)2

解得

⎧{ {⎨{ {⎩𝑐 0=1 𝑐 1=−2 𝑐 2=2{c 0=1 c 1=−2 c 2=2

那么

[𝑥 𝑛]𝐺(𝑥)=1−2 𝑛+1+(𝑛+1)⋅2 𝑛+1[x n]G(x)=1−2 n+1+(n+1)⋅2 n+1

## 牛顿二项式定理

我们重新定义组合数的运算：

(𝑟 𝑘)=𝑟 𝑘――𝑘!(𝑟∈𝐂,𝑘∈𝐍)(r k)=r k―k!(r∈C,k∈N)

注意 𝑟 r 的范围是复数域．在这种情况下．对于 𝛼 ∈𝐂 α∈C，有

(1+𝑥)𝛼=∑𝑛≥0(𝛼 𝑛)𝑥 𝑛(1+x)α=∑n≥0(α n)x n

二项式定理其实是牛顿二项式定理的一个特殊情况．

## 卡特兰数的生成函数

参考 Catalan 数形式的代数推演．

## 应用

接下来给出一些例题，来介绍生成函数在 OI 中的具体应用．

### 食物

食物

在许多不同种类的食物中选出 𝑛 n 个，每种食物的限制如下：

1. 承德汉堡：偶数个
2. 可乐：0 个或 1 个
3. 鸡腿：0 个，1 个或 2 个
4. 蜜桃多：奇数个
5. 鸡块：4 的倍数个
6. 包子：0 个，1 个，2 个或 3 个
7. 土豆片炒肉：不超过一个．
8. 面包：3 的倍数个

每种食物都是以「个」为单位，只要总数加起来是 𝑛 n 就算一种方案．对于给出的 𝑛 n 你需要计算出方案数，对 1 0 0 0 7 10007 取模．

这是一道经典的生成函数题．对于一种食物，我们可以设 𝑎 𝑛 a n 表示这种食物选 𝑛 n 个的方案数，并求出它的生成函数．而两种食物一共选 𝑛 n 个的方案数的生成函数，就是它们生成函数的卷积．多种食物选 𝑛 n 个的方案数的生成函数也是它们生成函数的卷积．

在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：

1. ∑𝑛≥0 𝑥 2 𝑛 =1 1−𝑥 2∑n≥0 x 2 n=1 1−x 2．
2. 1 +𝑥 1+x．
3. 1 +𝑥 +𝑥 2 =1−𝑥 3 1−𝑥 1+x+x 2=1−x 3 1−x．
4. 𝑥 1−𝑥 2 x 1−x 2．
5. ∑𝑛≥0 𝑥 4 𝑛 =1 1−𝑥 4∑n≥0 x 4 n=1 1−x 4．
6. 1 +𝑥 +𝑥 2 +𝑥 3 =1−𝑥 4 1−𝑥 1+x+x 2+x 3=1−x 4 1−x．
7. 1 +𝑥 1+x．
8. 1 1−𝑥 3 1 1−x 3．

那么全部乘起来，得到答案的生成函数：

𝐹(𝑥)=(1+𝑥)(1−𝑥 3)𝑥(1−𝑥 4)(1+𝑥)(1−𝑥 2)(1−𝑥)(1−𝑥 2)(1−𝑥 4)(1−𝑥)(1−𝑥 3)=𝑥(1−𝑥)4 F(x)=(1+x)(1−x 3)x(1−x 4)(1+x)(1−x 2)(1−x)(1−x 2)(1−x 4)(1−x)(1−x 3)=x(1−x)4

然后将它转化为展开形式（使用封闭形式练习中第五个练习）：

𝐹(𝑥)=∑𝑛≥1(𝑛+2 𝑛−1)𝑥 𝑛 F(x)=∑n≥1(n+2 n−1)x n

因此答案就是 (𝑛+2 𝑛−1) =(𝑛+2 3)(n+2 n−1)=(n+2 3)．

### Sweet

「CEOI2004」Sweet

有 𝑛 n 堆糖果．不同的堆里糖果的种类不同（即同一个堆里的糖果种类是相同的，不同的堆里的糖果的种类是不同的）．第 𝑖 i 个堆里有 𝑚 𝑖 m i 个糖果．现在要吃掉至少 𝑎 a 个糖果，但不超过 𝑏 b 个．求有多少种方案．

两种方案不同当且仅当吃的个数不同，或者吃的糖果中，某一种糖果的个数在两个方案中不同．

𝑛 ≤1 0,0 ≤𝑎 ≤𝑏 ≤1 0 7,𝑚 𝑖 ≤1 0 6 n≤10,0≤a≤b≤10 7,m i≤10 6．

在第 𝑖 i 堆吃 𝑗 j 个糖果的方案数（显然为 1）的生成函数为

𝐹 𝑖(𝑥)=𝑚 𝑖∑𝑗=0 𝑥 𝑗=1−𝑥 𝑚 𝑖+1 1−𝑥 F i(x)=∑j=0 m i x j=1−x m i+1 1−x

因此总共吃 𝑖 i 个糖果的方案数的生成函数就是

𝐺(𝑥)=𝑛∏𝑖=1 𝐹 𝑖(𝑥)=(1−𝑥)−𝑛 𝑛∏𝑖=1(1−𝑥 𝑚 𝑖+1)G(x)=∏i=1 n F i(x)=(1−x)−n∏i=1 n(1−x m i+1)

现在我们要求的是 ∑𝑏 𝑖=𝑎[𝑥 𝑖]𝐺(𝑥)∑i=a b[x i]G(x)．

由于 𝑛 ≤1 0 n≤10，因此我们可以暴力展开 ∏𝑛 𝑖=1(1 −𝑥 𝑚 𝑖+1)∏i=1 n(1−x m i+1)（最多只有 2 𝑛 2 n 项）．

然后对 (1 −𝑥)−𝑛(1−x)−n 使用牛顿二项式定理：

(1−𝑥)−𝑛=∑𝑖≥0(−𝑛 𝑖)(−𝑥)𝑖=∑𝑖≥0(𝑛−1+𝑖 𝑖)𝑥 𝑖(1−x)−n=∑i≥0(−n i)(−x)i=∑i≥0(n−1+i i)x i

我们枚举 ∏𝑛 𝑖=1(1 −𝑥 𝑚 𝑖+1)∏i=1 n(1−x m i+1) 中 𝑥 𝑘 x k 项的系数，假设为 𝑐 𝑘 c k．那么它和 (1 −𝑥)−𝑛(1−x)−n 相乘后，对答案的贡献就是

𝑐 𝑘 𝑏−𝑘∑𝑖=𝑎−𝑘(𝑛−1+𝑖 𝑖)=𝑐 𝑘((𝑛+𝑏−𝑘 𝑏−𝑘)−(𝑛+𝑎−𝑘−1 𝑎−𝑘−1))c k∑i=a−k b−k(n−1+i i)=c k((n+b−k b−k)−(n+a−k−1 a−k−1))

这样就可以 𝑂(𝑏)O(b) 地求出答案了．

时间复杂度 𝑂(2 𝑛 +𝑏)O(2 n+b)．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：sshwy, StudyingFather, countercurrent-time, Enter-tainer, H-J-Granger, NachtgeistW, CCXXXI, AngelKitty, c-forrest, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Ir1d, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, GavinZhengOI, Gesrua, Great-designer, HeRaNO, hly1204, kxccc, lychees, Molmin, Peanut-Tang, purple-vine, Revltalize, schtonn, shuzhouliu, skylee03, SukkaW, Tiphereth-A, xglight
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用