生成函数理论初步

定义

定义一个数列 \(\{a_n\}^\infty_{n=0}\) 的

普通生成函数（OGF）为：

\[\boxed{f(x)=\sum\limits_{n=0}^\infty a_nx^n} \]

指数生成函数（EGF）为：

\[\boxed{f(x)=\sum\limits_{n=0}^\infty\dfrac{a_n}{n!}x^n} \]

Dirichlet生成函数为（DGF）为：

\[\boxed{f(s)=\sum\limits_{n=1}^\infty\dfrac{a_n}{n^s}} \]

例如数列 \(\{1,1,\dots\}_{n=0}^\infty\) 的

普通生成函数（OGF）为：

\[\boxed{f(x)=\sum\limits_{n=0}^\infty x^n=\dfrac{1}{1-x}} \]

指数生成函数（EGF）为：

\[\boxed{f(x)=\sum\limits_{n=0}^\infty\dfrac{x^n}{n!}=e^x} \]

Dirichlet生成函数为（DGF）为：

\[\boxed{f(s)=\sum\limits_{n=1}^\infty\dfrac{1}{n^s}:=\zeta(s)} \]

扩展

普通生成函数（OGF）

生成函数就是数列的和函数，这里的 \(=\) 是形式收敛

我们知道，\(\{a_n\}_{n=0}^\infty\) 的普通生成函数是 \(f(x)=\sum\limits^\infty_{n=0}a_nx^n\)

那如果我们要求 \(\{a_{n+1}\}_{n=0}^\infty\) 的生成函数呢

\[\begin{align*} f(x)&=\sum\limits^\infty_{n=0}a_nx^n \\ &=\sum\limits^\infty_{n=1}a_nx^n+a_n \\ &=\sum\limits^\infty_{n=0}a_{n+1}x^{n+1}+a_n \\ &=\dfrac{1}{x}\sum\limits^\infty_{n=0}a_{n+1}x^{n}+a_n \end{align*} \]

所以，\(\{a_{n+1}\}_{n=0}^\infty\) 的OGF为：\(\dfrac{f(x)-a_0}{x}\)

由此，我们可以推出数列：\(\{a_{n+k}\}_{n=0}^\infty\) 的OGF为：\(\dfrac{f(x)-a_0-a_1x-\dots-a_{k-1}x^{k-1}}{x^k}\)

事实上，我们有时候不仅需要求 \(\{a_{n+k}\}_{n=0}^\infty\) 的OGF，还需要求 \(\{na_n\}_{n=0}^\infty\) 的OGF，相当于我们用一个常数 \(n\) 去乘这个数列

我们知道，\(\text{d}(x^n)=nx^{n-1}\)

\(f^\prime(x)=\sum\limits^\infty_{n=0}na_nx^{n-1}\)

所以 \(\{na_n\}_{n=0}^\infty\) 的OGF是：\(x\text{D}f\) （以下设 \(\text{D}=\dfrac{\text{d}}{\text{d}x}\)）

则 \(\{n^ka_n\}_{n=0}^\infty\) 的OGF是：\((x\text{D})^kf\)

由此我们可以再得出一个更强的结论：\(\{g(x)a_n\}_{n=0}^\infty\) 的OGF是：\(g(x\text{D})f\)

有时候我们需要将两个数列或是他们的生成函数相乘，此时又代表着什么意义呢？

设 \(f(x)=\sum\limits^\infty_{n=0}a_nx^n\) 与 \(g(x)=\sum\limits^\infty_{n=0}b_nx^n\) 分别是数列 \(\{a_n\}^\infty_{n=0}\) 和 \(\{b_n\}^\infty_{n=0}\) 的生成函数

则

\[\begin{align*} h(x)=f(x)g(x)&=\sum\limits^\infty_{n=0}a_nx^n\sum\limits^\infty_{n=0}b_nx^n \\ &=\sum\limits^\infty_{m=0}\sum\limits^\infty_{n=0}a_mb_nx^{m+n} \end{align*} \]

比较系数，发现 \(x^n\) 这一项的系数等于 \(\sum\limits^n_{k=0}a_kb_{n-k}\)

所以 \(f(x)g(x)\) 是数列 \(\left\{\sum\limits^n_{k=0}a_kb_{n-k}\right\}_{n=0}^\infty\) 的生成函数，我们可以从组合意义上来帮助理解，这里不做过多叙述

一个简单的推论：\(\dfrac{1}{(1-x)^k}\) 是数列 \(\left\{\dbinom{n+k-1}{n}\right\}_{n=0}^\infty\) 的OGF

接下来是一个更强的结论：

设有 \(m\) 个数列 \(\{a1_n\}^\infty_{n=0},\{a2_n\}^\infty_{n=0},\dots,\{am_n\}^\infty_{n=0}\) 他们的生成函数分别是 \(f1(x),f2(x),\dots,fm(x)\)

则 \(f1(x)f2(x)\dots fm(x)\) 是数列 \(\left\{\sum\limits_{n_1+n_2+\dots+n_m=n}a1_{n_1}a2_{n_2}\dots am_{n_m}\right\}_{n=0}^\infty\) 的OGF

指数生成函数（EGF）

由定义，数列 \(\{a_n\}^\infty_{n=0}\) 的EGF为： \(f(x)=\sum\limits^\infty_{n=0}\dfrac{a_n}{n!}x^n\)

像上文一样，我们首先依然是要求 \(\{a_{n+1}\}^\infty_{n=0}\) 的EGF

\[\begin{align*} \sum\limits^\infty_{n=0}\dfrac{a_{n+1}}{n!}x^n&=\sum\limits^\infty_{n=1}\dfrac{a_n}{(n-1)!}x^{n-1} \\ &=\sum\limits^\infty_{n=1}\dfrac{na_n}{n!}x^{n-1} \\ &=\text{D}f \end{align*} \]

注：做求导运算的时候一定注意 \(n!\) 是一个常数

由上式立即可得：\(\{a_{n+k}\}^\infty_{n=0}\) 的EGF为 \(\text{D}^kf\)

数乘：\(\{na_{n}\}^\infty_{n=0}\) 的EGF为：

\[\begin{align*} \sum\limits^\infty_{n=0}\dfrac{na_n}{n!}x^n&=\sum\limits^\infty_{n=0}\dfrac{a_n}{(n-1)!}x^n \\ &=x\sum\limits^\infty_{n=1}\dfrac{a_{n+1}}{n!}x^n \\ &=x\text{D}f \end{align*} \]

此结果依然可得出一个推论：\(\{g(x)a_n\}_{n=0}^\infty\) 的EGF是 \(g(x\text{D})f\)

接下来是乘法运算：

设 \(f(x)=\sum\limits^\infty_{n=0}\dfrac{a_n}{n!}x^n\) 与 \(g(x)=\sum\limits^\infty_{n=0}\dfrac{b_n}{n!}x^n\) 分别是数列 \(\{a_n\}^\infty_{n=0}\) 和 \(\{b_n\}^\infty_{n=0}\) 的指数生成函数，则：

\[\begin{align*} h(x)=f(x)g(x)&=\sum\limits^\infty_{n=0}\dfrac{a_n}{n!}x^n\sum\limits^\infty_{m=0}\dfrac{b_m}{m!}x^m \\ &=\sum\limits^\infty_{n=0}\sum\limits^\infty_{m=0}\dfrac{a_nb_m}{n!m!}x^{n+m} \end{align*} \]

观察可知，对于 \(x^n\) 这一项来说，它的系数是 \(\sum\limits^n_{i=0}\dfrac{a^ib^{n-i}}{i!(n-i)!}\)

我们把分子分母上的式子同乘 \(\dbinom{n}{i}\)，会发现分母变为了 \(n!\)，分子变为了 \(\dbinom{n}{i}a^ib^{n-i}\)

所以，\(f(x)g(x)\) 是数列 \(\left\{\sum\limits^n_{k=0}\dbinom{n}{k}a^kb^{n-k}\right\}_{n=0}^\infty\) 的EGF

Dirichlet生成函数（DGF）

以下 \(p\) 均为素数

DGF在数论中比较常见，所以它跟其他的生成函数不同，我们由定义，直接讨论 \(f(s)g(s)\) 的Dirichlet生成函数

\[\begin{align*} h(s)=f(s)g(s)&=\sum^\infty_{n=1}\dfrac{a_n}{n^s}\sum^\infty_{m=1}\dfrac{b_m}{m^s} \\ &=\sum^\infty_{n=1}\sum^\infty_{m=1}\dfrac{a_nb_m}{n^sm^s} \end{align*} \]

按照往常的思路，依然是先观察系数，发现 \(n^s\) 这一项的系数是 \(\left\{\sum\limits_{d|n}a_db_{\frac{n}{d}}\right\}_{n=1}^\infty\)

所以，\(f(s)g(s)\) 是数列 \(\left\{\sum\limits_{d|n}a_db_{\frac{n}{d}}\right\}_{n=1}^\infty\) 的DGF

推广到一般：若 \(f(s)\) 是数列 \(\{a_n\}^\infty_{n=1}\) 的DGF，则 \(f^k(s)\) 是数列 \(\left\{\sum\limits_{a_1a_2\cdots a_k=n}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=1}^\infty\) 的DGF

如若函数 \(f\) 是一个积性数论函数，则数列 \(\{f(n)\}_{n=1}^\infty\) 的DGF是：

\[\begin{align*} \sum\limits^\infty_{n=1}\dfrac{f(n)}{n^s}=\prod\limits_p\left(\sum\limits_{k=0}^\infty f(p^k)p^{-ks}\right) \end{align*} \]

其中，\(p\) 是 \(n\) 的素因子

注意到上式 \(p^{-ks}=\dfrac{1}{(p^k)^s}\)，原式即得证

应用

OGF的应用

从数量不限的苹果香蕉橘子梨中选取 \(n\) 个水果，要求苹果数是偶数，香蕉数是 \(5\) 的倍数，橘子最多有 \(4\) 个，梨最多有 \(1\) 个，记这样的装法有 \(h_n\) 种，求 \(h_n\)

设 \(f(x)\) 为 \(h_n\) 的OGF，则：

\[\begin{align*} f(x)&=(1+x^2+x^4+\dots)(1+x^5+x^{10}+\dots)(1+x+x^2+x^3+x^4)(1+x) \\ &=\dfrac{1}{1-x^2}\dfrac{1}{1-x^5}\dfrac{1-x^5}{1-x}(1+x)\tag{1} \\ &=\dfrac{1+x}{(1-x^2)(1+x)} \\ &=\dfrac{1}{(1-x)^2}\tag{2} \\ &=\sum\limits^\infty_{n=0}\dbinom{n+1}{n}x^n \end{align*} \]

其中 \((1)\) 处：\(1+x+x^2+x^3+x^4=\dfrac{1+x+x^2+\cdots}{1+x^5+x^{10}+\cdots}=\dfrac{1-x^5}{1-x}\)

\((2)\) 处可用大除法算得

之后比较系数可得：\(h_n=n+1\)

EGF的应用

用红白蓝三种颜色对 \(1\) 行 \(n\) 列的棋盘上的所有方格进行涂色，若要求涂成红色的方格数为偶数，则有多少种涂色方法？

设 \(h_n\) 表示方法数，根据EGF的性质，立即给出

\[\begin{align*} h(x)&=\left(1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots\right)\left(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+\cdots\right)^2 \\ &=\left(\dfrac{\text{e}^x+\text{e}^{-x}}{2}\right)(\text{e}^x)^2\tag1 \\ &=\dfrac{1}{2}(\text{e}^{3x}+\text{e}^{x}) \end{align*} \]

\((1)\) 处：

\[\begin{align*} \text{e}^x+\text{e}^{-x}&=\sum\limits^\infty_{n=0}\dfrac{x^n}{n!}+\sum\limits^\infty_{n=0}\dfrac{(-1)^n}{n!}x^n \\ &=\{2·1+2\dfrac{x^2}{2!}+2\dfrac{x^4}{4!}+\cdots\}_{n=0}^\infty \end{align*} \]

比较系数，得 \(h_n=\dfrac{3^n+1}{2}\)

确定每位数字都是奇数，且 \(1\) 和 \(3\) 都出现偶数次的 \(n\) 位数的个数

设 \(h_n\) 表示方法数

\[\begin{align*} h(x)&=\left(1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots\right)^2\left(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+\cdots\right)^3 \\ &=\left(\dfrac{\text{e}^x+\text{e}^{-x}}{2}\right)^2\text{e}^{3x} \\ &=\dfrac{1}{4}(\text{e}^{5x}+2\text{e}^{3x}+\text{e}^x) \end{align*} \]

比较系数，\(h_n=\dfrac{5^n+2·3^n+1}{4}\)

从 \(a,b,c\) 中可重复的选取 \(4\) 个字母，其中至少有两个 \(a\)，设能组成的不同的字符串的个数是 \(h_n\)，求 \(h_n\)

\[\begin{align*} h(x)&=(\text{e}^x-1-x)\text{e}^{2x} \\ &=\text{e}^{3x}-\text{e}^{2x}-x\text{e}^{2x}\tag1 \\ &=3^n-2^n-\tfrac{n2^n}{2} \end{align*} \]

\((1)\) 处：

\[\begin{align*} x\text{e}^{2x}&=x\sum\limits^\infty_{n=0}\dfrac{2^n}{n!}x^n \\ &=\sum\limits_{n=1}^\infty\dfrac{2^{n-1}}{(n-1)!}x^n \\ &=\sum\limits_{n=1}^\infty\dfrac{\frac{n}{2}2^n}{n!}x^n \end{align*} \]

DGF的应用

介绍一个黑科技：常值函数，为什么说它黑呢？看看下面这个例子

常值函数 \(f:\mathbb{Z}^+\to1\) 是一个积性数论函数，从而 \(\{1\}^\infty_{n=1}\) 的DGF是：

\[\boxed{\zeta(s)=\prod\limits_p\left(\sum\limits_{k=0}^\infty p^{-ks}\right)=\dfrac{1}{\prod\limits_p(1-p^{-s})}} \]

我们回忆一下积性数论函数 \(\mu(n)\)

它的DGF是

\[\boxed{\tilde{\mu}(s)=\sum\limits_{n=1}^\infty\dfrac{\mu(n)}{n^s}=\prod\limits_p(1-p^{-s})} \]

也即：\(\tilde{\mu}(s)\zeta(s)=1\)