学习笔记：生成函数

· · 算法·理论

生成函数

生成函数（Generating Function），也叫做母函数。是组合数学中的一种重要的方法，它将离散数列与形式幂级数对应起来。

对于有限数列 {a_i}(i=0,1,...,n)，我们定义其相对应的生成函数为：

\sum^{n}_{i=0}{a_ix^i}

对于无限数列 {a_i}(i=0,1,...,\infty)，我们定义其相对应的生成函数为：

\sum^{\infty}_{i=0}{a_ix^i}

先来举几个小例子：

  1. 当数列为 \left\{1, 2, 3\right\} 时，其相对应的生成函数为 1+2x+3x^2。

  2. 当数列为 \left\{1, 1, 4, 5, 1, 4\right\} 时，其相对应的生成函数为 1+x+4x^2+5x^3+x^4+4x^5。

  3. 当数列为 \left\{1, 9, 1, 9, 8, 1, 0\right\} 时，其相对应的生成函数为 1+9x+x^2+9x^3+8x^4+x^5。

通过对以上几个小例子的观察，我们可以很明显地看出一些规律：数列的相加对应生成函数的相加，数列的卷积对应生成函数的相乘。