「OI」生成函数 Generating Function

生成函数(generating function),又称母函数,是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。

简介

生成函数(generating function),又称母函数,是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。

生成函数有许多不同的种类,但大多可以表示为单一的形式:

\[F(x)=\sum _ na _ nk _ n(x)\]

其中 \(k _ n(x)\) 被称为核函数不同的核函数会导出不同的生成函数。

对于生成函数 \(F(x)\),我们用 \([k _ n(x)]F(x)\) 来表示它的第 \(n\) 项核函数对应的系数,即 \(a _ n\)。

普通生成函数

定义

序列 \(a\) 的普通生成函数(ordinary generating function,OGF)定义为形式幂级数:

\[F(x)=\sum _ na _ nx^n\]

基本运算

考虑两个序列 \(a,b\) 的普通生成函数,分别为 \(F(x),G(x)\)。那么有

\[F(x)\pm G(x)=\sum _ n(a _ n\pm b _ n)x^n\]

因此 \(F(x)\pm G(x)\) 是序列 \(\langle a _ n\pm b _ n\rangle\) 的普通生成函数。

考虑乘法运算,也就是卷积:

\[F(x)G(x)=\sum _ nx^n\sum^n _ {i=0}a _ ib _ {n-i}\]

因此 \(F(x)G(x)\) 是序列 \(\langle\sum^n _ {i=0}a _ ib _ {n-i}\rangle\) 的普通生成函数。

封闭形式

在运用生成函数的过程中,我们不会一直使用形式幂级数的形式,而会适时地转化为封闭形式以更好地化简。

  • 例如 \(\langle 1,1,1,\cdots\rangle\) 的普通生成函数
    \[F(x)=\sum _ {n\geq 0}x^n\]
    根据错位相减法我们可以有
    \[xF(x)+1=F(x)\]
    解这个方程可以得出
    \[F(x)=\frac{1}{1-x}\]
    上面这个式子就是 \(F(x)=\sum _ {n\geq 0}x^n\) 的封闭形式。
  • 考虑等比数列 \(\langle 1,p,p^2,\cdots\rangle\) 的生成函数
    \[F(x)=\sum _ {n\geq 0}p^nx^n\]

    \[pxF(x)+1=F(x)\]
    所以有
    \[F(x)=\frac{1}{1-px}\]

等比数列的封闭形式与展开形式是常用的变换手段。

应用

求组合问题方案数

在许多不同种类的食物中选出 \(n\) 个,每种食物的限制如下:

  1. 承德汉堡:偶数个;
  2. 可乐:0 个或 1 个;
  3. 鸡腿:0 个,1 个或 2 个;
  4. 蜜桃多:奇数个;
  5. 鸡块:4 的倍数个;
  6. 包子:0 个,1 个,2 个或 3 个;
  7. 土豆片炒肉:不超过一个;
  8. 面包:3 的倍数个。

每种食物都是以“个”为单位,只要总数加起来是 \(n\) 就算一种方案。对于给出的 \(n\) 你需要计算出方案数,对 \(10007\) 取模。

题解

我们不妨设生成函数的第 \(n\) 项核函数的系数来表示选择 \(n\) 个该食物合法的方案数。

那么我们有

  1. 承德汉堡:偶数个
    \[
    \begin{aligned}
    F(x)&=1\times x^0+0\times x^1+1\times x^2+\cdots\\
    &=\sum _ {n\geq 0}x^{2n}\\
    &=\frac{1}{1-x^2}\\
    \end{aligned}
    \]
  2. 可乐:0 个或 1 个
    \[F(x)=1+x\]
  3. 鸡腿:0 个,1 个或 2 个;
    \[
    \begin{aligned}
    F(x)&=1+x+x^2\\
    &=\frac{1-x^3}{1-x}
    \end{aligned}
    \]
  4. 蜜桃多:奇数个;
    \[
    \begin{aligned}
    F(x)&=1\times x^1+1\times x^3+\cdots\\
    &=\sum _ {n\geq 0}x^{2n+1}\\
    &=\frac{x}{1-x^2}
    \end{aligned}
    \]
  5. 鸡块:4 的倍数个;
    \[
    \begin{aligned}
    F(x)&=1\times x^0+1\times x^4+\cdots\\
    &=\sum _ {n\geq 0}x^{4n}\\
    &=\frac{1}{1-x^4}
    \end{aligned}
    \]
  6. 包子:0 个,1 个,2 个或 3 个;
    \[
    \begin{aligned}
    F(x)&=1+x+x^2+x^3\\
    &=\frac{1-x^4}{1-x}
    \end{aligned}
    \]
  7. 土豆片炒肉:不超过一个;
    \[
    \begin{aligned}
    F(x)&=1\times x^0+1\times x^1\\
    &=1+x
    \end{aligned}
    \]
  8. 面包:3 的倍数个。
    \[
    \begin{aligned}
    F(x)&=1\times x^0+1\times x^3+\cdots\\
    &=\sum _ {n\geq 0}x^{3n}\\
    &=\frac{1}{1-x^3}
    \end{aligned}
    \]

根据乘法原理以及普通生成函数的运算法则,我们可以知道,实际上的选择方案数就是把上面的全部乘起来后得到函数的第 \(n\) 项核函数的系数。

所以我们先乘起来
\[F(x)=\frac{x}{(1-x)^4}\]

化为展开形式
\[F(x)=\sum _ {n\geq 1}\binom{n+2}{n-1}x^n\]

因此答案为 \(\binom{n+2}{n-1}=\binom{n+2}{3}=\frac{(n+2)(n+1)n}{6}\)。

斐波那契数列的生成函数

首先我们先定义斐波那契数列为
\[
f _ i=
\begin{cases}
1&,i=0\ \text{or}\ i=1\\
f _ {i-2}+f _ {i-1}&,i\geq 2
\end{cases}
\]

定义斐波那契数列的普通生成函数为 \(F(x)\),那么我们有
\[F(x)=xF(x)+x^2F(x)-f _ 0x+f _ 1x+f _ 0\]

解得
\[F(x)=\frac{x}{1-x-x^2}\]

下面考虑求出展开形式以寻找通项公式。

方法一

\[
\begin{aligned}
F(x)&=\frac{x}{1-(x+x^2)}\\
&=\sum_{n\geq 0}(x+x^2)^n\\
&=\sum_{n\geq 0}\sum_{i=0}^n\binom{n}{i}x^{2i}x^{n-i}\\
&=\sum_{n\geq 0}\sum_{i=0}^n\binom{n}{i}x^{n+i}\\
&=\sum_{n\geq 0}x^n\sum_{i=0}^n\binom{n-i}{i}
\end{aligned}
\]

我们得到了斐波那契数列与组合数的关系,这个问题我们以后再聊。

方式二

考虑待定系数法。
\[\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{x}{1-x-x^2}\]

通分
\[\frac{A-Abx+B-aBx}{(1-ax)(1-bx)}=\frac{x}{1-x-x^2}\]

我们可以得到一个方程组
\[
\begin{cases}
A+B=0\\
-Ab-aB=1\\
a+b=1\\
ab=-1
\end{cases}
\]

解得
\[
\begin{cases}
A=\frac{1}{\sqrt{5}}\\
B=-\frac{1}{\sqrt{5}}\\
a=\frac{1+\sqrt{5}}{2}\\
b=\frac{1-\sqrt{5}}{2}
\end{cases}
\]

所以我们有
\[\frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\]

卡特兰数的通项公式

未完待续。

指数生成函数

定义

序列 \(a\) 的指数生成函数(exponential generating function,EGF)定义为形式幂级数:

\[\hat{F}(x)\sum _ na _ n\frac{x^n}{n!}\]

基本运算

指数生成函数的加减法与普通生成函数是相同的,也就是对应项系数相加。

考虑指数生成函数的乘法运算。对于两个序列 \(a,b\),设它们的指数生成函数分别为 \(\hat{F}(x),\hat{G}(x)\),那么

\[
\begin{aligned}
\hat{F}(x)\hat{G}(x)&=\sum _ {i\geq 0}a _ i\frac{x^i}{i!}\sum _ {j\geq 0}b _ j\frac{x^j}{j!}\\
&=\sum _ {n\geq 0}x^n\sum^n _ {i=0}a _ ib _ {n-i}\frac{1}{i!(n-i)!}\\
&=\sum _ {n\geq 0}\frac{x^n}{n!}\sum^n _ {i=0}\binom{n}{i}a _ ib _ {n-i}
\end{aligned}
\]

因此 \(\hat{F}(x)\hat{G}(x)\) 是序列 \(\langle\sum^n _ {i=0}\binom{n}{i}a _ ib _ {n-i}\rangle\) 的生成函数。

封闭形式

我们同样考虑指数生成函数的封闭形式。

序列 \(\langle 1,1,\cdots\rangle\) 的指数生成函数是

\[\hat{F}(x)=\sum _ {n\geq 1}\frac{x^n}{n!}=e^x\]

这是因为你将 \(e^x\) 在原点处泰勒展开就得到了它的无穷级数形式。

类似地,等比数列 \(\langle 1,p,p^2,\cdots\rangle\) 的指数生成函数是 \(e^{px}\)。

相关习题

参考资料