普通生成函数与指数生成函数
普通生成函数编码无标签计数序列，而指数生成函数处理有标签结构，两者都将组合构造转化为代数形式。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
序列的普通生成函数是以该序列为系数的幂级数；指数生成函数将每个系数除以一个阶乘，这种形式适用于计数带标签的对象。
Scope
本主题介绍两种主要的生成函数、形式幂级数框架以及将组合构造（不相交并集、乘积、序列、集合和循环）直接映射到级数运算的符号方法。它阐述了区分普通和指数设置的乘积公式。
Core questions
- 何时应使用普通生成函数而非指数生成函数？
- 组合运算如何对应于级数的代数运算？
- 为什么指数生成函数的乘法可以计数带标签的合并？
- 符号方法如何使计数公式的推导自动化？
Key concepts
- 普通生成函数
- 指数生成函数
- 形式幂级数
- 卷积与乘积法则
- 符号方法
- 带标签与无标签结构
Key theories
- 符号方法
- 弗拉霍莱特和塞奇威克的符号方法提供了一个系统的字典，将对象类上的组合构造转化为其生成函数上的运算，从而可以从结构描述中读出计数公式。
- 生成函数的乘积法则
- 两个普通生成函数的乘积通过总大小枚举有序对，而指数生成函数的乘积枚举带标签的合并，这种区别决定了应使用哪种形式。
Clinical relevance
符号方法使数据结构和算法的枚举及平均情况分析自动化，而指数生成函数是计数计算机科学中出现的带标签树、排列和集合划分的自然工具。
History
欧拉和波利亚预示的组合构造与生成函数运算之间的系统对应关系，由弗拉霍莱特和塞奇威克发展为形式符号方法。
Key figures
- Philippe Flajolet
- Robert Sedgewick
- Richard P. Stanley
Related topics
Seminal works
- flajolet2009
- stanley2011
Frequently asked questions
- 何时优先使用指数生成函数？
- 当被计数的对象带有可区分的标签时，例如带标签的树或排列，指数生成函数的阶乘加权使其乘积能够正确计数。
- 生成函数中的变量有意义吗？
- 在形式设置中，它是一个标记大小的占位符；只有当应用解析方法时，它才被视为具有数值的复变量。