生成函数学习笔记

TLE_Automat · 2022-03-13 15:43:15 · 个人记录

生成函数学习笔记

一.牛顿二项式定理

定理

介绍生成函数前，先介绍一下牛顿二项式定理，这是我们将生成函数从封闭形式转化为形式幂级数的有力工具。

定义牛顿二项式系数

\binom{r}{n} = \left\{\begin{aligned} &0 &(n<0) \\ &1 &(n=0) \\ &\frac{r(r-1)\cdots(r-n+1)}{n!} &(n>0) \end{aligned} \right.

注意其中的 n\in \mathbb{Z} ，而 r\in \mathbb{R} ，所以牛顿二项式系数没有组合意义，当 r,n 均为非负整数时，\binom{r}{n} 在数值上等于 C_{r}^{n} 。

牛顿二项式定理

(x+y)^\alpha = \sum\limits_{n=0}^{\infty} \binom{\alpha}{n} x^n y^{\alpha - n}

其中 \alpha \in \mathbb{R} 。（一种可行的证明是使用泰勒级数将左式展开）

推论（常用结论）

令 m 为正整数，n 为整数，则有
\binom{-m}{n} = (-1)^{n} \binom{m+n-1}{n}
令 m 为正整数，则有
\begin{aligned} &(1+x)^m = \sum\limits_{n=0}^{\infty}(-1)^n\binom{m+n-1}{n}x^n \\ &(1-x)^m = \sum\limits_{n=0}^{\infty}\binom{m+n-1}{n}x^n \end{aligned}
令 \alpha = \frac{1}{2} ，则有
(1+x)^{\frac{1}{2}} = 1 + \sum\limits_{n=1}^{\infty} \frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}x^n

二.普通生成函数

定义

普通生成函数，简称生成函数。

设序列 \{a_n\} ，构造其形式幂级数

G(x) = a_0x_0 + a_1x_1 + \cdots + a_nx_n +\cdots

称 G(x) 为序列 \{a_n\} 的生成函数。其中 \{a_n\} 可以是有限项的序列，也可以是无穷项的序列。

基本运算

加法：

设 F(x) , G(x) 分别为长度为 k 的序列 \{a_n\} , \{b_n\} 的生成函数，则
F(x) + G(x) = \sum\limits_{n=0}^{k} (a_n+b_n) x^n
乘法：

设 F(x) , G(x) 分别为长度为 k 的序列 \{a_n\} , \{b_n\} 的生成函数，则
F(x) G(x) = \left(\sum\limits_{n=0}^{k} a_nx^n\right)\left(\sum\limits_{n=0}^{k} b_nx^n\right) = \sum\limits_{n=0}^{k} x^n \sum\limits_{i=0}^{n} a_i b_{n-i}
可见，乘法后的 x^n 的系数，其实就是 \{a_n\} 和 \{b_n\} 前 n 项的卷积。

（注意这里卷积完长度大于 k 项，并不是完全相等，但这里只需要前 k 项系数相等即可）

封闭形式

令 a_n = 1 ，则 \{a_n\} 的生成函数为

G(x) = \sum\limits_{i=0}^{\infty} x^n

因为

1+G(x)x = G(x)

所以

G(x) = \frac{1}{1-x}

这就是序列 \{a_n\} 的生成函数的封闭形式。

亿些小练习：

求序列 a_n = p^n 的生成函数的封闭形式，p 为常数。
求序列 a_n = \binom{m}{n} 的生成函数的封闭形式，m 为常数。
求序列 a_n = n+1 的生成函数的封闭形式。
求序列 a_n = (-1)^n 的生成函数的封闭形式。
求序列 a_n = (-1)^n(n+1) 的生成函数的封闭形式。

答案：

G(x) = \frac{1}{1-px}
G(x) = (1+x)^m
G(x) = \frac{1}{(1-x)^2}
G(x) = \frac{1}{1+x}
G(x) = \frac{1}{(1+x)^2}

应用 1 求数列通项公式

斐波那契数列通项公式的求解：点这里。

卡特兰数数列通项公式的求解：点这里。

使用生成函数求解给定递推式序列的通项式的一般方法：

设出 \{a_n\} 的生成函数 G(x) 。
利用递推方程的依赖关系，导出关于生成函数 G(x) 的方程。
求解方程，得到关于 G(x) 的函数表达式。
将 G(x) 展开成幂级数的形式，x^n 项的系数即为 a_n 。

应用 2 求解组合问题的方案数

前缀和相关

有长度为 k 的序列 \{a_n\},\{b_n\} ，b_n = \sum\limits_{i=0}^{n} a_n 。

则设 \{a_n\} , \{b_n\} 的生成函数分别为 A(x),B(x) ，则有
\begin{aligned} A(x) &= \sum\limits_{n=0}^{k} a_n x^n \\ B(x) &= \sum\limits_{n=0}^{k} b_n x^n \\ &= \sum\limits_{n=0}^{k} x^n\sum\limits_{i=0}^{n} a_i \cdot 1 \\ &= \left(\sum\limits_{n=0}^{k} a_n x^n\right) \left(\sum\limits_{n=0}^{k} x^n\right) \\ &= \frac{A(x)}{1-x} \end{aligned}
所以 B(x) 的封闭形式就是 A(x) 的封闭形式除以 1-x ，这是计数问题中比较重要的一个结论。
多重集的 r 组合数

设多重集 S = \{ n_1 \cdot a_1 , n_2\cdot a_2 , \cdots , n_k \cdot a_k \} 。

则 S 的一个 r 组合就是 S 的一个子多重集 \{x_1 \cdot a_1 , x_2 \cdot a_2 , \cdots , x_k \cdot a_k\} ，满足 x_i \in \mathbb{N} ,x_i \le n_i , i=1,2,\cdots k 。

考虑 S 的 r 组合数的生成函数
G(y) = (1+y+\cdots +y^{n_1})(1+y+\cdots + y^{n_2})\cdots(1+y+\cdots +y^{n_k})
右边展开后 y^r 项的系数就是 S 的 r 组合数。
不定方程非负整数解的个数

考虑不定方程 x_1 + x_2 +\cdots + x_k = r , x_i\in \mathbb{N} 。

这个方程的解的个数可以通过隔板法求解，为 \binom{r+k-1}{k-1} 。

我们考虑用生成函数求解这个问题，设其生成函数
G(y) = (1+y+\cdots)^k
易得其封闭形式为
G(x) = \frac{1}{(1-y)^k} = (1-y)^{-k}
用牛顿二项式定理将其重新转化为形式幂级数
G(x) = \sum_{n=0}^{\infty} \binom{-k}{n} (-y)^{n} = \sum_{n=0}^{\infty} (-1)^n\frac{k(k+1)\cdots(k+n-1)}{n!} (-y)^{n} = \sum_{n=0}^{\infty} \binom{k+n-1}{n} y^n
所以第 r 项系数为 \binom{r+k-1}{r} = \binom{r+k-1}{k-1} 。

这里我们可以对原不定方程做一些限制。

例如 l_i \le x_i \le r_i ，此时其生成函数为
G(y) = (y^{l_1} + y^{l_1+1} + \cdots +y^{r_1})(y^{l_2}+y^{l_2+1}+\cdots+y^{r_2})\cdots (y^{l_k}+y^{l_k+1}+\cdots+y^{r_k})
再比如 p_1 x_1 + p_2 x_2 + \cdots + p_k x_k = r ,x_i,p_i\in \mathbb{N} ，其生成函数为
G(y) = (1 + y^{p_1} + y^{2p_1} + \cdots)(1 + y^{p_2} + y^{2p_2} + \cdots)\cdots(1 + y^{p_k} + y^{2p_k} + \cdots)
这些生成函数 y^r 项的系数就对应着这个不定方程解的个数。

其封闭形式为
G(y) = \prod_{n=1}^k\frac{1}{1-y^{p_n}}
两边同时取 \ln 得
\ln G(y) = \sum\limits_{n=1}^{k} \ln\frac{1}{1-y^{p_n}}
因为
\ln \frac{1}{1-x^k} = \sum\limits_{n=1}^{\infty} \frac{x^{nk}}{n}
所以
\ln G(y) = \sum\limits_{n=1}^{k} \sum\limits_{i=1}^{\infty} \frac{y^{i p_n}}{i}
假设 p_n 的值域为 [1,m] ，则可以改变顺序为枚举 p_n 的值，设 t_x 为 p_n =x 的个数，则有
\ln G(y) = \sum\limits_{v=1}^{m} \sum\limits_{i=1}^{\infty} \frac{t_v}{i}y^{iv} = \sum\limits_{v=1}^{m} \sum\limits_{i=1}^{\lfloor r/v\rfloor} \frac{t_v}{i}y^{iv}
如果 r,m 同级，我们就可以直接上 O(n\log n) 枚举出系数，然后多项式 \exp 出 y^r 以内的系数，就可以接解决问题了。

附证明 \ln \frac{1}{1-x^k} = \sum\limits_{n=1}^{\infty} \frac{x^{nk}}{n} 。

首先设 G(x) = \ln \frac{1}{1-x^k} = -\ln(1-x^k) ，设 F(x) = 1 - x^k ，则有 G(x) = -\ln F(x) ，两边求导得
G'(x) = - \frac{F'(x)}{F(x)} = \frac{kx^{k-1}}{1-x^k}
将上式的右边展开得
G'(x) = kx^{k-1} \sum\limits_{n=0}^{\infty} x^{kn} = k\sum\limits_{n=1}^{\infty} x^{kn-1}
两边同时做不定积分得
\int G'(x) = G(x) = k \sum\limits_{n=1}^{\infty} \int x^{kn -1} = k \sum\limits_{n=1}^{\infty} \frac{x^{kn}}{kn} = \sum\limits_{n=0}^{\infty} \frac{x^{kn}}{n}
正整数拆分的计数问题

考虑正整数的无序拆分问题，就是将正整数 N 拆分成若干个正整数之和，不考虑顺序。可以根据是否允许重复分为可重复无序拆分和不可重复无序拆分。

例如正整数 3 的可重复无序拆分有 3 种，分别是 3 = 3 , 3 = 1 + 2 , 3 = 1+1+1 ，而不可重复无序拆分只有 2 种，分别是 3 = 3 , 3 = 1 + 2 。

设给定正整数 N ，将 N 无序拆分成正整数 a_1 , a_2 , \cdots ,a_n ，则有等式
a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = N
这与不定方程的解的个数问题十分类似。

如果允许重复，那么对应的生成函数其实就是
G(y) = (1 + y^{a_1} + y^{2a_1} + \cdots)(1 + y^{a_2} + y^{2a_2} + \cdots)\cdots(1 + y^{a_n} + y^{2a_n} + \cdots)
如果不允许重复，那么对应的生成函数就更简单了
G(y) = (1+y^{a_1})(1+y^{a_2})\cdots(1+y^{a_n})

三.指数生成函数

定义

设长度为 k 的序列 \{a_n\} ，称

G_e(x) = \sum\limits_{n=0}^{k} a_n \frac{x^n}{n!}

为序列 \{a_n\} 的指数生成函数。

基本运算

与普通生成函数的运算相同。

封闭形式

记 P(m,n) = \frac{m!}{(m-n)!} ，则当 m 为常数时，P(m,n) 的指数生成函数为

G_e(x) = \sum\limits_{n=0}^{\infty} \frac{m!}{(m-n)!} \frac{x^n}{n!} = \sum\limits_{n=0}^{\infty} C(m,n)x^n = (1+x)^m

则 P(m,n) 的指数生成函数的封闭形式就是 (1+x)^m 。

令 a_n = 1 ，则序列 \{a_n\} 的指数生成函数为

G_e(x) = \sum\limits_{n=0}^{\infty} \frac{x^n}{n!} = e^x

上式左边其实就是 e^x 的泰勒展开，所以序列 a_n = 1 的指数生成函数的封闭形式就是 e^x。

还有一个比较重要的结论是 e^{\lambda x} 展开形式为

G_e(x) = \sum\limits_{n=0}^{\infty} \lambda^{n} \frac{x^n}{n!}

应用

多重集的排列数

设 S = \{n_1\cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k\} ，则 S 的 r 排列的指数生成函数为
G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)
其中
f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^{n_i}}{n_i!}
考虑 x^r 项一定由以下 k 项相乘的形式组合而成
\frac{x^{m_1}}{m_1!} \frac{x^{m_2}}{m_2!}\cdots\frac{x^{m_k}}{m_k!}
并且满足以下限制
\begin{aligned} & m_1 + m_2 + \cdots + m_k = r \\ & m_i \in \mathbb{N} , m_i \le n_i \end{aligned}
而这种组合的形式可以化为
\frac{x^{m_1 + m_2 + \cdots + m_k}}{m_1!m_2!\cdots m_k!} = \frac{x^r}{r!}\frac{r!}{m_1!m_2!\cdots m_k!}
所以这个问题中
a_r = \sum\limits_{m_1+m_2 +\cdots m_k = r} \frac{r!}{m_1! m_2! \cdots m_k!}
其组合意义就是 S 的 r 排列数。

一个有趣的练习题：

由 \text{A,B,C,D,E,F} 构成长度为 n 的序列，要求 \text{A,B} 在排列中出现次数之和为偶数，求方案数。

考虑如果没有 \text{A,B} 出现次数和的限制，实际上就是一个求多重集的 n 排列数，每个元素都有无穷多个，此时其生成函数为
G_e(x) = \left( \sum\limits_{n=0}^{\infty} \frac{x^n}{n!} \right)^6 = e^{6x}
因为 \text{A,B} 出现次数之和为偶数，所以 \text{A,B} 出现次数的奇偶性相同，所以 \text{A,B} 所在的项一定同时是
\sum\limits_{n=0}^{\infty}[n \text{ is odd number}]\frac{x^n}{n!} = \frac{e^x - e^{-x}}{2}
或者
\sum\limits_{n=0}^{\infty}[n \text{ is even number}]\frac{x^n}{n!} = \frac{e^{x} + e^{-x}}{2}
所以考虑限制之后的生成函数就是
G_e(x) = e^{4x} \left(\left(\frac{e^x + e^{-x}}{2}\right)^2 + \left(\frac{e^x - e^{-x}}{2}\right)^2\right) = \frac{e^{6x} + e^{2x}}{2} = \frac{1}{2}\sum\limits_{n=0}^{\infty} (6^n + 2^n)\frac{x^n}{n!}
所以方案数为 \frac{6^n+2^n}{2} 。