本文主要是介绍生成函数性质速查表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
摘要: 生成函数的性质【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings
生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。
生成函数的一个重要线索来自于 18 世纪欧拉对整数分拆问题的研究，其中有了一些生成函数思想的雏形（该项研究同样也是卷积和的思想来源的线索）。
最早提出母函数的是法国数学家拉普拉斯，他在其 1812 年出版的《概率的分析理论》中明确提出“概率生成函数的计算”，书中对欧拉的整数分拆的研究做了延伸。生成函数的理论由此基本建立。
生成函数可以对组合对象进行计数，也可以作为分析工具去求解递归式。求解递归式的过程中，最关键的一步是在递归式的基础上，做各种变形，去凑生成函数的性质，得到生成函数满足的微分方程或函数方程。
下面我们不加证明地罗列普通生成函数和指数生成函数的常用性质，在凑的时候要用到，背是背不下来的，用到的时候可以查。
普通生成函数 (OGF)
OGF 的性质
普通生成函数常用于无标记的组合结构的计数问题。
记 A ( z ) = ∑ n = 0 ∞ a n z n A(z) = \sum\limits_{n=0}\limits^{\infty}a_{n}z^{n} A(z)=n=0∑∞anzn、 B ( z ) = ∑ n = 0 ∞ b n z n B(z) = \sum\limits_{n=0}\limits^{\infty}b_{n}z^{n} B(z)=n=0∑∞bnzn：
| 性质 | 公式 |
|---|---|
| 数列的相加 | A ( z ) + B ( z ) = ∑ n = 0 ∞ ( a n + b n ) z n A(z) + B(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n} + b_{n})z^{n} A(z)+B(z)=n=0∑∞(an+bn)zn |
| 数列的数乘 | α A ( z ) = ∑ n = 0 ∞ α a n z n \alpha A(z) = \sum\limits_{n=0}\limits^{\infty}\alpha a_{n}z^{n} αA(z)=n=0∑∞αanzn |
| 数列的卷积(OGF的相乘) | A ( z ) B ( z ) = ∑ n = 0 ∞ ( ∑ k = 0 n a k b n − k ) z n A(z)B(z) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k}b_{n-k})z^{n} A(z)B(z)=n=0∑∞(k=0∑nakbn−k)zn |
| 数列的差分 | ( 1 − z ) A ( z ) = a 0 + ∑ n = 1 ∞ ( a n − a n − 1 ) z n (1 - z)A(z) = a_{0} + \sum\limits_{n=1}\limits^{\infty}(a_{n} - a_{n-1})z^{n} (1−z)A(z)=a0+n=1∑∞(an−an−1)zn |
| 数列的部分和 | A ( z ) 1 − z = ∑ n = 0 ∞ ( ∑ k = 0 n a k ) z n \frac{A(z)}{1 - z} = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k})z^{n} 1−zA(z)=n=0∑∞(k=0∑nak)zn |
| 数列的右移(OGF乘自变量) | z A ( z ) = ∑ n = 1 ∞ a n − 1 z n zA(z) = \sum\limits_{n=1}\limits^{\infty}a_{n-1}z^{n} zA(z)=n=1∑∞an−1zn |
| 数列的左移(OGF除自变量) | A ( z ) − a 0 z = ∑ n = 0 ∞ a n + 1 z n \frac{A(z)-a_{0}}{z} = \sum\limits_{n=0}\limits^{\infty}a_{n+1}z^{n} zA(z)−a0=n=0∑∞an+1zn |
| OGF的导数(数列乘下标) | A ′ ( z ) = ∑ n = 0 ∞ ( n + 1 ) a n + 1 z n A'(z) = \sum\limits_{n=0}\limits^{\infty}(n+1)a_{n+1}z^{n} A′(z)=n=0∑∞(n+1)an+1zn |
| OGF的积分(数列除下标) | ∫ 0 z A ( t ) d t = ∑ n = 1 ∞ a n − 1 n − 1 z n \int_{0}^{z}A(t)\mathrm{d}t = \sum\limits_{n=1}\limits^{\infty}\frac{a_{n-1}}{n-1}z^{n} ∫0zA(t)dt=n=1∑∞n−1an−1zn |
| OGF自变量的比例因子 | A ( λ z ) = ∑ n = 0 ∞ λ n a n z n A(\lambda z) = \sum\limits_{n=0}\limits^{\infty}\lambda^{n}a_{n}z^{n} A(λz)=n=0∑∞λnanzn |
| OGF的复合 | A ( B ( z ) ) = ∑ n = 0 ∞ a n ( B ( z ) ) n A(B(z)) = \sum\limits_{n=0}\limits^{\infty}a_{n}(B(z))^{n} A(B(z))=n=0∑∞an(B(z))n，要求 b 0 = 0 b_{0} = 0 b0=0 |
常见数列的 OGF
| 数列 a n a_{n} an | OGF A ( z ) A(z) A(z) |
|---|---|
| a n = 1 a_{n} = 1 an=1 | A ( z ) = 1 1 − z A(z) = \frac{1}{1-z} A(z)=1−z1 |
| a n = n a_{n} = n an=n | A ( z ) = z ( 1 − z ) 2 A(z) = \frac{z}{(1-z)^{2}} A(z)=(1−z)2z |
| a n = ( n 2 ) a_{n} = \binom{n}{2} an=(2n) | A ( z ) = z 2 ( 1 − z ) 3 A(z) = \frac{z^{2}}{(1-z)^{3}} A(z)=(1−z)3z2 |
| a n = ( n m ) a_{n} = \binom{n}{m} an=(mn) | A ( z ) = z m ( 1 − z ) m + 1 A(z) = \frac{z^{m}}{(1-z)^{m+1}} A(z)=(1−z)m+1zm |
| a n = ( m n ) a_{n} = \binom{m}{n} an=(nm) | A ( z ) = ( 1 + z ) m A(z) = (1+z)^{m} A(z)=(1+z)m |
| a 2 k = 1 , a 2 k + 1 = 0 a_{2k}=1, a_{2k+1}=0 a2k=1,a2k+1=0 | A ( z ) = 1 1 − z 2 A(z) = \frac{1}{1-z^{2}} A(z)=1−z21 |
| a n = c n a_{n} = c^{n} an=cn | A ( z ) = 1 1 − c z A(z) = \frac{1}{1-cz} A(z)=1−cz1 |
| a n = 1 n ! a_{n} = \frac{1}{n!} an=n!1 | A ( z ) = e z A(z) = e^{z} A(z)=ez |
| a n = 1 n a_{n} = \frac{1}{n} an=n1 | A ( z ) = − ln ( 1 − z ) A(z) = -\ln(1-z) A(z)=−ln(1−z) |
| a n = H n a_{n} = H_{n} an=Hn | A ( z ) = 1 1 − z ln 1 1 − z A(z) = \frac{1}{1-z}\ln\frac{1}{1-z} A(z)=1−z1ln1−z1 |
| a n = n ( H n − 1 ) a_{n} = n(H_{n} - 1) an=n(Hn−1) | A ( z ) = z ( 1 − z ) 2 ln 1 1 − z A(z) = \frac{z}{(1-z)^{2}}\ln\frac{1}{1-z} A(z)=(1−z)2zln1−z1 |
指数生成函数 (EGF)
指数型生成函数常用于有标记的组合结构的计数问题。
记 A ( z ) = ∑ n = 0 ∞ a n z n n ! A(z) = \sum\limits_{n=0}\limits^{\infty}a_{n}\frac{z^{n}}{n!} A(z)=n=0∑∞ann!zn、 B ( z ) = ∑ n = 0 ∞ b n z n n ! B(z) = \sum\limits_{n=0}\limits^{\infty}b_{n}\frac{z^{n}}{n!} B(z)=n=0∑∞bnn!zn：
EGF 的性质
| 性质 | 公式 |
|---|---|
| 数列的相加 | A ( z ) + B ( z ) = ∑ n = 0 ∞ ( a n + b n ) z n n ! A(z) + B(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n} + b_{n})\frac{z^{n}}{n!} A(z)+B(z)=n=0∑∞(an+bn)n!zn |
| 数列的数乘 | α A ( z ) = ∑ n = 0 ∞ α a n z n n ! \alpha A(z) = \sum\limits_{n=0}\limits^{\infty}\alpha a_{n}\frac{z^{n}}{n!} αA(z)=n=0∑∞αann!zn |
| 数列的二项卷积(EGF的相乘) | A ( z ) B ( z ) = ∑ n = 0 ∞ ( ∑ k = 0 n ( n k ) a k b n − k ) z n n ! 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)B(z)=n=0∑∞(k=0∑n(kn)akbn−k)n!zn |
| 数列的差分 | A ′ ( z ) − A ( z ) = ∑ n = 0 ∞ ( a n + 1 − a n ) z n n ! A'(z) - A(z) = \sum\limits_{n=0}\limits^{\infty}(a_{n+1} - a_{n})\frac{z^{n}}{n!} A′(z)−A(z)=n=0∑∞(an+1−an)n!zn |
| 数列的二项部分和 | e z A ( z ) = ∑ n = 0 ∞ ( ∑ k = 0 n ( n k ) a k ) 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!} ezA(z)=n=0∑∞(k=0∑n(kn)ak)n!zn |
| 数列的右移(EGF的积分) | ∫ 0 z A ( t ) d t = ∑ n = 1 ∞ a n − 1 z n n ! \int_{0}^{z}A(t)\mathrm{d}t = \sum\limits_{n=1}\limits^{\infty}a_{n-1}\frac{z^{n}}{n!} ∫0zA(t)dt=n=1∑∞an−1n!zn |
| 数列的左移(EGF的导数) | A ′ ( z ) = ∑ n = 0 ∞ a n + 1 z n n ! A'(z) = \sum\limits_{n=0}\limits^{\infty}a_{n+1}\frac{z^{n}}{n!} A′(z)=n=0∑∞an+1n!zn |
| EGF乘自变量(数列乘下标) | z A ( z ) = ∑ n = 0 ∞ n a n − 1 z n n ! zA(z) = \sum\limits_{n=0}\limits^{\infty}na_{n-1}\frac{z^{n}}{n!} zA(z)=n=0∑∞nan−1n!zn |
| EGF除自变量(数列除下标) | A ( z ) − A ( 0 ) z = ∑ n = 1 ∞ a n + 1 n + 1 z n n ! \frac{A(z)-A(0)}{z} = \sum\limits_{n=1}\limits^{\infty}\frac{a_{n+1}}{n+1}\frac{z^{n}}{n!} zA(z)−A(0)=n=1∑∞n+1an+1n!zn |
常见数列的 EGF
| 数列 a n a_{n} an | EGF A ( z ) A(z) A(z) |
|---|---|
| a n = 1 a_{n} = 1 an=1 | A ( z ) = e z A(z) = e^{z} A(z)=ez |
| a n = n a_{n} = n an=n | A ( z ) = z e z A(z) = ze^{z} A(z)=zez |
| a n = ( n 2 ) a_{n} = \binom{n}{2} an=(2n) | A ( z ) = 1 2 z 2 e z A(z) = \frac{1}{2}z^{2}e^{z} A(z)=21z2ez |
| a n = ( n m ) a_{n} = \binom{n}{m} an=(mn) | A ( z ) = 1 m ! z m e z A(z) = \frac{1}{m!}z^{m}e^{z} A(z)=m!1zmez |
| a 2 k = 1 , a 2 k + 1 = 0 a_{2k}=1, a_{2k+1}=0 a2k=1,a2k+1=0 | A ( z ) = 1 2 ( e z + e − z ) A(z) = \frac{1}{2}(e^{z} + e^{-z}) A(z)=21(ez+e−z) |
| a n = c n a_{n} = c^{n} an=cn | A ( z ) = e c z A(z) = e^{cz} A(z)=ecz |
| a n = 1 n a_{n} = \frac{1}{n} an=n1 | A ( z ) = e z − 1 z A(z) = \frac{e^{z}-1}{z} A(z)=zez−1 |
| a n = n ! a_{n} = n! an=n! | A ( z ) = 1 1 − z A(z) = \frac{1}{1-z} A(z)=1−z1 |
这篇关于生成函数性质速查表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
