生成函数入门经典
0.1
我大概在两个月前听说了生成函数 然后就一直想学 但一直找不到蒟蒻我看得懂的资料
观赏巨神用生成函数解各种炫酷的递归式 很羡慕qwq
近些天有时间了就通读了一遍具体数学 但蒟蒻我太菜了 只能了解一些定义
所以本篇只是普通型生成函数的一点点定义 巨神勿喷
（有空了可能会更新qwq）
0.5 前置知识
（这里会列一些书）
幂级数
同济大学高等数学下册
最基础的微积分
同济大学高等数学上册
递归式与和式的一些处理技巧
具体数学
可能需要一些数列知识
选择性必修2
1 引入
对于一个数列 我们有时需要对它进行一些操作
如左移、右移、与某系数相乘、使其正负交错、与某数列相加、与某数列卷积等等
此时某路过的巨神说：你好菜 用通项公式不就好了qwq
通项公式那么好求还要nmd生成函数
果然巨神就是巨神 瞧一眼就知道通项
我错了我错了
既然不知道通项
那我们引入另一种数学工具 用某个函数来表示这个数列 以此通过一个式子获得数列的全部信息
普通型生成函数
$$
G(z)=\sum_{n\geq0}g_nz^{n}
$$
指数型生成函数
$$
G(z)=\sum_{n\geq0}g_n\frac{z^n}{n!}
$$
狄利克雷生成函数
$$
G(z)=\sum_{n\geq1}\frac{g_n}{n^z}
$$
因为蒟蒻我太菜了 所以现在只讨论普通型qwq
可以看到 普通型生成函数将数列$g_n$的全部信息都放进了一个函数中 并且函数后有一个幂级数 所以大概率在某个取值处无穷级数收敛 就算不收敛 也可以得到一个封闭形式 并且大概率是一个分式
注意：这里生成函数的自变量z被称为形式级数 收敛称为形式收敛
换句话说 我们并不真的关注函数是否收敛 z的幂次数只用来标记这是数列的哪一项 只要得到封闭形式就行
2基本操作
2.1右移
显而易见
$$
\begin{align}
z^mG(z)&=\sum_ng_nz^{n+m}\&=\sum_ng_{n-m}z^n
\end{align}
$$
2.2左移
即构造前m个数被删除的序列
先减去前m项 再除$z^m$
$$
\begin{align}
\frac{G(z)-g_0-g_1z-…-g_{m-1}z^{m-1}}{z^m}&=\sum_{n\geq m}g_nz^{n-m}\&=\sum_{n\geq 0}g_{n+m}z^n
\end{align}
$$
2.3交错
用常数倍cz代替z
$$
\begin{align}
G(cz)&=
\sum_{n}g_n(cz)^{n}\&=
\sum_{n\geq 0}c^ng_{n}z^n
\end{align}
$$
当c=-1时 得到原数列正负交错的数列的生成函数
2.4求导
$$
\begin{align}
G’(z)&=g_1+2g_2z+3g_3z^2+…
\&=\sum_n(n+1)g_{n+1}z^n
\end{align}
$$
我们得到了将一个求和因子n下放为因数的序列的生成函数
再右移一位
$$
\begin{align}
zG’(z)=\sum_nng_nz^n
\end{align}
$$
这很有用qwq
2.5积分
$$
\begin{align}
\int_0^z G(t)dt=g_0z+\frac{1}{n}g_{n-1}z^n
\end{align}
$$
可以看做求导的逆运算
2.6卷积
把两生成函数相乘
$$
\begin{align}
F(z)G(z)&=(f_0+f_1z+f_2z^2+…)(g_0+g_1z+g_2z^2+…)\
&=(f_0g_0)+(f_0g_1+f_1g_0)z+(f_0g_2+f_1g_1+f_2g_2)z^2+…\
&=\sum_n(\sum_kf_kg_{n-k})z^n
\end{align}
$$
是不是很眼熟 这就是卷积
另 将生成函数与1/(1-n)相卷就得到了数列前缀和的生成函数
3一些例子
3.1定义性
$$
\frac{1}{(1-z)^{n+1}}=\sum_{k\geq0} {n+k\choose n}z^k\
\frac{z^n}{(a-n)^{n+1}}=\sum_{k\geq0}{k\choose n}z^k\
$$
作为一个特例
$$
\frac{1}{1-z}=1+z+z^2+z^3+…=\sum_{k\geq0}z^k
$$
这是数列1,1,1,1…的生成函数 所以卷积是前缀和
另
$$
\frac{1}{1-az}=1+az+a^2z^2+a^3z^3…
$$
3.2证明斐波那契数列通项公式
设feb之生成函数为F(z)
则分别将其与其右移一位之函数与右移两位之函数纵列
$$
\begin{align}
F(z)=f_0+f_1z+f_2z^2&+f_3z^3+f_z^4…\
zF(z)=f_0z+f_1z^2&+f_2z^3+f_3z^4…\
z^2F(z)=f_0z^2&+f_1z^3+f_2z^4…
\end{align}
$$
此时你可能惊讶于我恶心的对齐 不过不要慌
首先考虑feb之递归式 然后将纵列对齐的部分相减 我们得到
$$
F(z)-zF(z)-z^2F(z)=z
$$
对F(z)求解即得其生成函数封闭形式
$$
F(z)=\frac{z}{1-z-z^2}
$$
对于通项公式 我们的目标是求
$$
\frac{A}{1-az}+\frac{B}{1-bz}=\frac{z}{1-z-z^2}
$$
因为看起来这很像而且等号左边二式之和的通项公式很易确定