生成函数的性质速查

摘要: 生成函数的性质

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。

生成函数的一个重要线索来自于 18 世纪欧拉对整数分拆问题的研究，其中有了一些生成函数思想的雏形（该项研究同样也是卷积和的思想来源的线索）。

最早提出母函数的是法国数学家拉普拉斯，他在其 1812 年出版的《概率的分析理论》中明确提出“概率生成函数的计算”，书中对欧拉的整数分拆的研究做了延伸。生成函数的理论由此基本建立。

生成函数可以对组合对象进行计数，也可以作为分析工具去求解递归式。求解递归式的过程中，最关键的一步是在递归式的基础上，做各种变形，去凑生成函数的性质，得到生成函数满足的微分方程或函数方程。

下面我们不加证明地罗列普通生成函数和指数生成函数的常用性质，在凑的时候要用到，背是背不下来的，用到的时候可以查。

普通生成函数 (OGF)

OGF 的性质

普通生成函数常用于无标记的组合结构的计数问题。

记 $A(z) = \sum\limits_{n=0}\limits^{\infty}a_{n}z^{n}$、$B(z) = \sum\limits_{n=0}\limits^{\infty}b_{n}z^{n}$：

性质	公式
数列的相加	$A(z) + B(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n} + b_{n})z^{n}$
数列的数乘	$\alpha A(z) = \sum\limits_{n=0}\limits^{\infty}\alpha a_{n}z^{n}$
数列的卷积(OGF的相乘)	$A(z)B(z) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k}b_{n-k})z^{n}$
数列的差分	$(1 - z)A(z) = a_{0} + \sum\limits_{n=1}\limits^{\infty}(a_{n} - a_{n-1})z^{n}$
数列的部分和	$\frac{A(z)}{1 - z} = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k})z^{n}$
数列的右移(OGF乘自变量)	$zA(z) = \sum\limits_{n=1}\limits^{\infty}a_{n-1}z^{n}$
数列的左移(OGF除自变量)	$\frac{A(z)-a_{0}}{z} = \sum\limits_{n=0}\limits^{\infty}a_{n+1}z^{n}$
OGF的导数(数列乘下标)	$A’(z) = \sum\limits_{n=0}\limits^{\infty}(n+1)a_{n+1}z^{n}$
OGF的积分(数列除下标)	$\int_{0}^{z}A(t)\mathrm{d}t = \sum\limits_{n=1}\limits^{\infty}\frac{a_{n-1}}{n-1}z^{n}$
OGF自变量的比例因子	$A(\lambda z) = \sum\limits_{n=0}\limits^{\infty}\lambda^{n}a_{n}z^{n}$
OGF的复合	$A(B(z)) = \sum\limits_{n=0}\limits^{\infty}a_{n}(B(z))^{n}$，要求 $b_{0} = 0$

常见数列的 OGF

数列 $a_{n}$	OGF $A(z)$
$a_{n} = 1$	$A(z) = \frac{1}{1-z}$
$a_{n} = n$	$A(z) = \frac{z}{(1-z)^{2}}$
$a_{n} = \binom{n}{2}$	$A(z) = \frac{z^{2}}{(1-z)^{3}}$
$a_{n} = \binom{n}{m}$	$A(z) = \frac{z^{m}}{(1-z)^{m+1}}$
$a_{n} = \binom{m}{n}$	$A(z) = (1+z)^{m}$
$a_{2k}=1, a_{2k+1}=0$	$A(z) = \frac{1}{1-z^{2}}$
$a_{n} = c^{n}$	$A(z) = \frac{1}{1-cz}$
$a_{n} = \frac{1}{n!}$	$A(z) = e^{z}$
$a_{n} = \frac{1}{n}$	$A(z) = -\ln(1-z)$
$a_{n} = H_{n}$	$A(z) = \frac{1}{1-z}\ln\frac{1}{1-z}$
$a_{n} = n(H_{n} - 1)$	$A(z) = \frac{z}{(1-z)^{2}}\ln\frac{1}{1-z}$

指数生成函数 (EGF)

指数型生成函数常用于有标记的组合结构的计数问题。

记 $A(z) = \sum\limits_{n=0}\limits^{\infty}a_{n}\frac{z^{n}}{n!}$、$B(z) = \sum\limits_{n=0}\limits^{\infty}b_{n}\frac{z^{n}}{n!}$：

EGF 的性质

性质	公式
数列的相加	$A(z) + B(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n} + b_{n})\frac{z^{n}}{n!}$
数列的数乘	$\alpha A(z) = \sum\limits_{n=0}\limits^{\infty}\alpha a_{n}\frac{z^{n}}{n!}$
数列的二项卷积(EGF的相乘)	$A(z)B(z) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}\binom{n}{k}a_{k}b_{n-k})\frac{z^{n}}{n!}$
数列的差分	$A’(z) - A(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n+1} - a_{n})\frac{z^{n}}{n!}$
数列的二项部分和	$e^{z}A(z) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}\binom{n}{k}a_{k})\frac{z^{n}}{n!}$
数列的右移(EGF的积分)	$\int_{0}^{z}A(t)\mathrm{d}t = \sum\limits_{n=1}\limits^{\infty}a_{n-1}\frac{z^{n}}{n!}$
数列的左移(EGF的导数)	$A’(z) = \sum\limits_{n=0}\limits^{\infty}a_{n+1}\frac{z^{n}}{n!}$
EGF乘自变量(数列乘下标)	$zA(z) = \sum\limits_{n=0}\limits^{\infty}na_{n-1}\frac{z^{n}}{n!}$
EGF除自变量(数列除下标)	$\frac{A(z)-A(0)}{z} = \sum\limits_{n=1}\limits^{\infty}\frac{a_{n+1}}{n+1}\frac{z^{n}}{n!}$

常见数列的 EGF

数列 $a_{n}$	EGF $A(z)$
$a_{n} = 1$	$A(z) = e^{z}$
$a_{n} = n$	$A(z) = ze^{z}$
$a_{n} = \binom{n}{2}$	$A(z) = \frac{1}{2}z^{2}e^{z}$
$a_{n} = \binom{n}{m}$	$A(z) = \frac{1}{m!}z^{m}e^{z}$
$a_{2k}=1, a_{2k+1}=0$	$A(z) = \frac{1}{2}(e^{z} + e^{-z})$
$a_{n} = c^{n}$	$A(z) = e^{cz}$
$a_{n} = \frac{1}{n}$	$A(z) = \frac{e^{z}-1}{z}$
$a_{n} = n!$	$A(z) = \frac{1}{1-z}$

---