====== 生成函数理论 3——普通生成函数 ======

==== 定义 1 ====

若形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 与 $g(x)=\sum_{n=0}^{\infty}b_nx^n$ 满足 $f(x)g(x)=1$，则称 $g(x)$ 为 $f(x)$ 的乘法逆。

==== 性质 2 ====

形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 有乘法逆的充分必要条件是 $a_0\ne 0$。

==== 性质 3 ====

设形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 与 $g(x)=\sum_{n=0}^{\infty}b_nx^n$ 互为复合逆，并且 $a_0=0$，则有 $b_0=0$ 且 $a_1\ne 0,b_1\ne 0$。

==== 事实 4 ====

若形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 满足 $f'(x)=0$，则 $f(x)$ 是常数级数 $a_0$。

==== 事实 5 ====

若形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 满足 $f'(x)=f(x)$，则 $f(x)=Ce^x$，其中 $C$ 是某个常数

==== 事实 6 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，则 $\{a_{n+1}\}_{n=0}^{\infty}$ 的普通生成函数是 $$
\frac{f(x)-a_0}{x}.
$$

==== 事实 7 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，则 $\{a_{n+2}\}_{n=0}^{\infty}$ 的普通生成函数是 $$
\frac{f(x)-a_0-a_1x}{x^2}.
$$

==== 性质 8 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，则 $\{a_{n+k}\}_{n=0}^{\infty}$ 的普通生成函数是 $$
\frac{f(x)-a_0-a_1x-\cdots-a_{k-1}x^{k-1}}{x^k}.
$$

==== 事实 9 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，则 $\{na_n\}_{n=0}^{\infty}$ 的普通生成函数是 $$
xDf,
$$ 这里为了方便，用 $xD$ 表示运算 $x\frac{d}{dx}$.

==== 推论 10 ====

$\{n\}_{n=0}^{\infty}\leftrightarrow xD\left(\frac{1}{1-x}\right)=\frac{x}{(1-x)^2}$.

==== 事实 11 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，则 $\{n^ka_n\}_{n=0}^{\infty}$ 的普通生成函数是 $$
(xD)^kf=(xD)[(xD)^{k-1}f].
$$

==== 性质 12 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，$P$ 是任一多项式，则 $\{P(n)a_n\}_{n=0}^{\infty}$ 的普通生成函数是 $$
P(xD)f.
$$

==== 例 13 ====

求和 $$
\sum_{n=0}^{\infty}\frac{n^2+4n+5}{n!}
$$ 解 由于 $$
e^x=\sum_{n=0}^{\infty}\frac{1}{n!}x^n,
$$ 故 $$
((xD)^2+4(xD)+5)e^x=\sum_{n=0}^{\infty}\frac{n^2+4n+5}{n!}x^n,
$$ 即 $$
(x^2+5x+5)e^x=\sum_{n=0}^{\infty}\frac{n^2+4n+5}{n!}x^n.
$$ 在上式中，令 $x=1$，即可得到 $$
\sum_{n=0}^{\infty}\frac{n^2+4n+5}{n!}=11e.
$$

==== 性质 14 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n,g(x)=\sum_{n=0}^{\infty}b_nx^n$（即 $f(x),g(x)$ 分别是数列 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的普通生成函数），则 $f(x)g(x)$ 是数列 $\displaystyle \left\{\sum_{k=0}^na_kb_{n-k}\right\}_{n=0}^{\infty}$ 的普通生成函数。

==== 性质 15 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$（即 $f(x)$ 是数列 $\{a_n\}_{n=0}^{\infty}$ 的普通生成函数），$k$ 为正整数，则 $f^k(x)$ 是数列 $$
\left\{\sum_{n_1+n_2+\cdots+n_k=n}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=0}^{\infty}
$$ 的普通生成函数。

==== 例 16 ====

令 $f(n,k)$ 表示正整数 $n$ 写成 $k$ 个非负整数有序和的方法数，例如 $f(4,2)=5$。试求 $f(n,k)$ 的显式表达式。

解 数列 $\{1\}_{n=0}^{\infty}$ 的普通生成函数是 $\frac{1}{1-x}$，故 $\frac{1}{(1-x)^k}$ 是数列 $$
\left\{\sum_{n_1+n_2+\cdots+n_k=n}1\right\}_{n=0}^{\infty}
$$ 的普通生成函数。上面的数列就是 $\{f(n,k)\}_{n=0}^{\infty}$，从而 $$
f(n,k)=[x^n]\frac{1}{(1-x)^k}=\binom{n+k-1}{n}.
$$

==== 推论 17 ====

若 $f(x)=\sum_{n=0}^{\infty}a_nx^n$，$k$ 为正整数，则 $\frac{f(x)}{1-x}$ 是数列 $\displaystyle \left\{\sum_{k=0}^{n}a_k\right\}_{n=0}^{\infty}$ 的普通生成函数。

==== 例 18 （调和级数） ====

$H_n$ 定义如下： $$
H_n=
\begin{cases}
0,&n=0,\\
1+\frac 1 2+\cdots+\frac 1 n, &n\ge 1.
\end{cases}
$$ 求 $\{H_n\}_{n=0}^{\infty}$ 的普通生成函数。

解 要求的函数是 $\displaystyle \frac{1}{1-x}$ 乘以 $\displaystyle \left\{\frac{1}{n}\right\}_{n=1}^{\infty}$ 的普通生成函数。后者当然就是 $$
f(x)=\sum_{n=1}^{\infty}\frac{x^n}{n}.
$$ 由 $f'(x)=\sum_{n=1}^{\infty}x^{n-1}=\frac{1}{1-x}$，经过简单的计算就可以得到 $f(x)=-\ln(1-x)$。所以 $$
\sum_{n=0}^{\infty}H_nx^n=-\frac{1}{1-x}\ln(1-x)=\frac{1}{1-x}\ln\frac{1}{1-x}.
$$

==== 例 19 ====

用硬币垒成一个“喷泉”如下：每行的硬币都连续摆在一起，除最下一行外，每枚硬币恰好置于其下面一行的两枚硬币之间。令 $f_n$ 表示如此可能垒成的最下一行恰有 $n$ 枚硬币的“喷泉”数，试求 $\{f_n\}_{n=0}^{\infty}$ 的普通生成函数。

解 首先 $f_0=1$，若只有一行，则数目为 $1$；若有多于一行，设从下面往上数第二行有 $k$ 枚硬币，则 $1\le k\le n-1$，且这 $k$ 枚硬币所在的位置有 $n-k$ 种，所以 $$
f_n=\sum_{k=1}^{n-1}(n-k)f_k+1=\sum_{k=1}^{n}(n-k)f_k+1.
$$ 令 $\{f_n\}_{n=0}^{\infty}$ 的普通生成函数为 $f(x)$，则 $$
\begin{align}
f(x)&=\sum_{n=0}^{\infty}f_nx^n=\sum_{n=0}^{\infty}\left(\sum_{k=1}^{n}(n-k)f_k+1\right)x^n\\
&=\sum_{n=0}^{\infty}\left(\sum_{k=1}^n(n-k)f_k\right)x^n+\sum_{n\ge 0}1\cdot x^n\\
&=\sum_{n=0}^{\infty}\left(\sum_{k=1}^n(n-k)f_k\right)x^n+\frac{1}{1-x}.
\end{align}
$$ 设 $g(x)=f(x)-1$，即 $g(x)$ 为 $g_n$ 的普通生成函数，其中 $g_0=f_0-1=0$，而 $n\ge 1$ 时，$g_n=f_n$，则有 $$
\sum_{k=1}^n(n-k)f_k=\sum_{k=1}^n(n-k)g_k=\sum_{k=0}^n(n-k)g_k.
$$ 然而 $\{n\}_{n=0}^{\infty}$ 的普通生成函数是 $(xD)\frac{1}{1-x}=\frac{x}{(1-x)^2}$，所以 $$
\sum_{n=0}^{\infty}\left(\sum_{k=0}^n(n-k)g_k\right)x^n=\frac{x}{(1-x)^2}g(x)=\frac{x}{(1-x)^2}(f(x)-1).
$$ 由 $$
f(x)=\frac{x}{(1-x)^2}(f(x)-1)+\frac{1}{1-x}
$$ 解得 $$
f(x)=\frac{1-2x}{1-3x+x^2}.
$$ 经计算，可求得 $$
f_n=\frac{-1+\sqrt 5}{2\sqrt 5}\left(\frac{3+\sqrt 5}{2}\right)^n+\frac{1+\sqrt5}{2\sqrt5}\left(\frac{3-\sqrt5}{2}\right)^n.
$$