生成函数

生成函数将一个数列编码为形式幂级数的系数，从而将组合计数转化为代数和解析运算。

Definition

生成函数是一个形式幂级数，其系数记录了数列的项，通过对级数进行代数运算来研究和组合计数数列。

Scope

该领域涵盖了普通生成函数和指数生成函数，将组合构造转化为级数运算的对应关系，递推关系的求解，以及从生成函数的奇点中提取渐近行为的解析组合学程序。它是枚举组合学中主要的统一方法。

Sub-topics

• analytic combinatorics asymptotics
• ordinary and exponential generating functions
• recurrence relations

Core questions

• 计数序列如何被封装为幂级数并进行代数操作？
• 组合构造如何转化为生成函数上的运算？
• 如何使用生成函数求解线性和非线性递推关系？
• 生成函数的解析行为如何揭示渐近增长？

Key concepts

• 普通生成函数
• 指数生成函数
• 形式幂级数
• 符号方法
• 递推关系
• 奇点分析

Clinical relevance

生成函数是算法和数据结构平均情况分析的主力工具，它们广泛应用于概率论（概率生成函数）、统计物理学以及随机组合结构的研究中。

History

欧拉在18世纪引入生成函数来解决划分问题；斯坦利将该方法系统化应用于组合学，弗拉霍莱和塞奇威克则将其发展为渐近分析的解析理论。

Key figures

• Leonhard Euler
• Philippe Flajolet
• Richard P. Stanley

Seminal works

• flajolet2009
• stanley2011

Frequently asked questions

为什么将序列视为幂级数？

对级数进行的代数运算——加法、乘法、代换——对应着自然的组合运算，因此一个单一的封闭形式函数可以捕获整个无限序列。

生成函数需要收敛吗？

作为形式幂级数，它们纯粹通过代数方式进行操作，无需考虑收敛性；收敛性仅在通过解析方法提取渐近行为时才重要。