Eternity

Until The End

生成函数

发表于 更新于 分类于 ，
本文字数： 976 阅读时长 ≈ 1 分钟

“生命是自然的奇迹，归心是灵魂的光彩。”

生成函数

又可以被称为母函数（$\text{Generating Function,GF}$），是一种形式幂级数，其每一项的系数都对应原序列的信息，一般用 $F(x)=\sum a_nk_n(x)$ 表示。

其中 $a_n$ 表示系数，$k_n(x)$ 是核函数，不同的核函数可以通过求导得到不同的生成函数。

常见的生成函数：

  • 普通生成函数 $k_n(x)=x^n$ ；
  • 指数生成函数 $k_n(x)=\frac{x^n}{n!}$ ；
  • 狄利克雷生成函数 $k_n(x)=\frac{1}{x^n}$ 。

一般有定义为 $a_n=[k_n(x)]F(x)$ ，表示第 $n$ 项核函数对应的系数。

普通生成函数

序列 $a$ 的普通生成函数（$\text{Ordinary Generating Function,OGF}$）定义为形式幂级数 $F(x)=\sum_na^nx^n$ 。

无论 $a$ 有序无序，有界无界，是否收敛，是否有限，$a$ 的 $\operatorname{OGF}$ 都是存在的。

例如：

  • 序列 $\{1,2,3\}$ 的普通生成函数是 $1+2x+3x^2$ ；
  • 序列 $\{1,1,1..\}$ 的普通生成函数是 $\sum_{n\ge 0}x^n=\frac{1}{1-x}$ ；
  • 序列 $\{1,p,p^2,p^3…p^k\}$ 的普通生成函数是 $\frac{1}{1-px}$ 。

有一个较明显的性质：

数列的加法对应生成函数的加法，而数列的卷积对应生成函数的乘法。

生成函数有级数形式，也存在其封闭形式。由等比数列的求和公式可以得到：$1+x+x^2+…$ 可以表示为 $\frac{1}{1-x}$ 。

等比数列

  • 定义式：$\frac{a_n}{a_{n-1}}=q(n\ge 2,a_{n-1}\ne 0,q\ne 0)$ ；
  • 通项公式：$a_n=a_1\times q^{n-1}$ ；
  • 求和公式：$S=\begin{cases}na_1&,q=1\\\frac{a_1(1-q^n)}{1-q}&,q\ne 1\end{cases}$ 。

而对于 $1+x+x^2…+x^{\infty}$ 的求和公式是通过极限的思想得到的：

相当于是 $x^{\infty}$ 可以忽略不计。

其实我觉得上面这个方法是不严谨的，所以有了第二种解释

第二种解释是，对于这个数列，它是无限的，所以满足性质：

$F(x)x+1=F(x)$

即我们将 $F(x)$ 的每一位都乘上 $x$ 在添上本身的第一项 $1$ ，它是与原数列等价的（因为数列无线）。

所以我们将 $F(x)$ 作为未知数，解这个方程：

得到 $F(x)=\frac{1}{1-x}$ 。

运用

生成函数广泛运用于组合计数中。

模型一

对于 $m$ 件物品，每一种物品只有 $1$ 件，求取 $n$ 件物品的总方案数。

构造单个物品的生成函数为 $1+x$ ，则 $m$ 种物品的生成函数就是 $(1+x)^m=\sum\limits_{i=0}^mC^i_mx^m$ ，通过二项式定理展开得到 $n$ 次项的系数为 $C^n_m$ 。

模型二

对于 $m$ 件物品，每一种物品有无数件，求取 $n$ 件物品的总方案数。

依然选择构造单个生成函数为 $1+x+x^2+…=\frac{1}{1-x}$ ，得到 $m$ 种物品的生成函数就是：

这是通过广义二项式定理展开得到的。

也可以得到第 $n$ 次项的系数就是 $C^{m-1}_{m+n-1}$ ，从组合数学的意义上而言，这道题等价于把 $n$ 个相同的球放进 $m$ 个不同的盒子的方案数。通过隔板法也可以得到最后的式子。

广义二项式定理

首先应该知道二项式定理：

$\left(^n_m\right)=\frac{n!}{m!(n-m)!}$

其中 $n,m$ 都指整数。

那么牛顿广义二项式定理就是把 $n$ 扩展到了实数范围，则有：

$(x+y)^{\alpha}=\sum\limits_{k=0}^{\infty}\left(^{\alpha}_k\right)x^{\alpha-k}y^k$ 。

其中 $\left(^{\alpha}_k\right)$ 表示 $\frac{\alpha(\alpha-1)(\alpha-2)…(\alpha-k+1)}{k!}=\frac{(\alpha)_k}{k!}$ 。

例题

BZOJ 3028

没有链接。

似乎是一道非常模板的生成函数题，直接根据每一种食物建立生成函数之后相乘即可。计算得到 $f(n)=\frac{x}{(1-x)^4}$ 。

而我们需要求得的答案为 $[x^n]F(x)$ ，即 $[x^{n-1}]\frac{1}{(1,x)^4}$ ，是 $4$ 个 $\frac{1}{1-x}$ 卷积的结果。

如果从组合数学的方式考虑，用插板法得出答案为 $(^{n+2}_3)$ 。

P2000

这道题的考点压根就不在生成函数，而是如何使用 $\text{NTT}$ 来优化 $n\leq 10^{10^{5}}$ 的高精度。

总结

这里给出一个不成文的结论：

对于普通生成函数而言，可以转换为下面两类模型：

  1. 所取的数是 $k$ 的倍数；
  2. 所取的数不超过 $k$ 。

这样的话，设其生成函数 $f$ 则有：

  1. $f_1=1+x^{k}+x^{2k}+\cdots+x^{\infty}$
  2. $f_2=1+x+x^2+x^3+\cdots+x^k$

然后使用错位相减法，得到：

  1. $f_1=\frac{1}{1-x^k}$
  2. $f_2=\frac{1-x^{k+1}}{1-x}$

实际上，这是一个更加通常的公式：

对于一个集合 $S=\{a_1,a_2,a_3,a_4,a_5,a_6\cdots a_p\}$ ，其生成函数为：

$f=x^{a_1}+x^{a_2}+x^{a_3}+x^{a_4}+\cdots+x^{a_p}$

当然，这里的 $a_p$ 如果是有限项的话，一般这里的 $a$ 都是一个等差数列；如果这里的 $a_p$ 是无限项的话，一般都是一个等比数列。总之，可以使用错位相减法使其消掉一大部分，否则，就是使用 $\text{FFT}$ 或者 $\text{NTT}$ 来优化多项式卷积以达到 $\mathcal O(n\log n)$ 的复杂度。

指数生成函数

序列 $a$ 的指数生成函数（$\text{Exponential Generating Function,EGF}$）被定义为形式幂级数 $F(x)=\sum_{n}a^n\frac{x^n}{n!}$ 。

有几个例子：

  • 序列 $\{1,1..1\}$ 的 $\text{EGF}$ 为 $e^x$ ；
  • 序列 $\{1,p,p^2…p^k\}$ 的 $\text{EGF}$ 为 $e^{px}$ 。

排列数对应序列的 $\text{EGF}$ 是 $F(x)=\sum_{n\ge 0}\frac{n!x^n}{n!}=\frac{1}{1-x}$ 。

例题

圆排列数

将 $n$ 个数排成一个环，求方案数。方案不同当且仅当其无限循环的母串不同。

$n$ 个数的圆排列数是 $(n-1)!$ 。

圆排列数的 $\text{EGF}$ 是 $G(x)=\sum_{n\ge 0}\frac{(n-1)!x^n}{n!}=\sum_{n\ge 0}\frac{x^n}{n}=\ln(\frac{1}{1-x})$ 。

对于这道题的另一解法，从组合的意义上来理解。

将一个排列 $p$ 看作是一个图，从数点 $i$ 有一条出边指向 $p_i$ ，那么整个图是一个由若干个环组成的（称为置换环），而每个环的内部方案数就是圆排列数。

从而把长度为 $n$ 的排列的方案数就是把 $1,2,3..n$ 分成若干个集合，每个集合的圆排列数积的总和，就是 $\exp$ 在 $\text{EGF}$ 中的组合意义。

同理，有标号生成树的 $\text{EGF}$ 经过 $\exp$ 后得到有标号生成森林的 $\text{EGF}$ ，有标号无向连通图的 $\text{EGF}$ 经过 $\exp$ 后得到有标号无向图的 $\text{EGF}$ 。

取 $\ln$ 就是相应的逆运算。

相关文章