CVBB ACM Team

====== 生成函数理论 4——指数型生成函数 ======

==== 事实 1 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\displaystyle \{a_{n+1}\}_{n=0}^{\infty}$ 的指数型生成函数是 $$
\sum_{n=0}^{\infty}\frac{a_{n+1}}{n!}x^n=\sum_{n=1}^{\infty}\frac{na_n}{n!}x^{n-1}=f'(x).
$$

==== 性质 2 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\displaystyle \{a_{n+k}\}_{n=0}^{\infty}$ 的指数型生成函数是 $\displaystyle D^kf$。

==== 例 3 ====

回忆 Fibonacci 数列 $\{f_n\}_{n=0}^{\infty}$，满足 $f_{n+2}=f_{n+1}+f_n$，初始条件为 $f_0=0,f_1=1$。用生成函数的方法再次求解 $f_n$。

解 令 $f(x)$ 为 $\{f_n\}_{n=0}^{\infty}$ 的指数型生成函数。性质 2 立即给出 $$
f''(x)=f'(x)+f(x).
$$ 解此常系数线性齐次微分方程，得到 $$
f(x)=C_1e^{\frac{1+\sqrt5}{2}x}+C_2e^{\frac{1-\sqrt5}{2}x},
$$ 其中 $C_1,C_2$ 是待定系数。初始条件转化为 $f(0)=0,f'(0)=1$，代入解得 $\displaystyle C_1=\frac{1}{\sqrt5},C_2=\frac{-1}{\sqrt5}$，从而 $$
f(x)=\frac{e^{\frac{1+\sqrt5}{2}x}-e^{\frac{1-\sqrt5}{2}x}}{\sqrt5}.
$$ 最后，得 $$
f_n=\left[\frac{x^n}{n!}\right]f(x)=\frac{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt5}
$$

==== 事实 4 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\{na_n\}_{n=0}^{\infty}$ 的指数型生成函数是 $xDf.$

==== 性质 5 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\{P(n)a_n\}_{n=0}^{\infty}$ 的指数型生成函数是 $P(xD)f.$

==== 性质 6 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n,g(x)=\sum_{n=0}^{\infty}\frac{b_n}{n!}x^n$（即 $f(x),g(x)$ 分别是数列 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的指数型生成函数），则 $f(x)g(x)$ 是数列 $\displaystyle \left\{\sum_{k=0}^n\binom{n}{k}a_kb_{n-k}\right\}_{n=0}^{\infty}$ 的指数型生成函数。

==== 例 7 ====

回忆 Bell 数。令 $B_n$ 表示 $[n]$ 上所有划分的个数，则有 $$
B_n=\sum_{k=1}^{n}\binom{n-1}{k-1}B_{n-k}=\sum_{i=0}^{n-1}\binom{n-1}{n-i-1}B_i.(i=n-k)
$$ 所以 $$
B_{n+1}=\sum_{k=0}^{n}\binom{n}{n-k}B_k=\sum_{k=0}^{n}\binom{n}{k}B_k.
$$ 初始条件为 $B_0=1,B_1=1$，利用上述指数型生成函数的性质，再次求解 $B_n$。

解 考虑 $\{B_n\}_{n=0}^{\infty}$ 的指数型生成函数 $B(x)$。利用递推关系及上述指数型生成函数的性质，又 $\{1\}_{n=0}^{\infty}$ 的指数型生成函数为 $e^x$，立即有 $$
B'(x)=e^xB(x),
$$ 且 $B(0)=1$。解此微分方程，得 $$
B(x)=e^{e^x-1}.
$$ 从而 $$
\begin{align}
B(x)&=\frac{1}{e}\sum_{k=0}^{\infty}\frac{(e^x)^k}{k!}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{1}{k!}\sum_{n=0}^{\infty}\frac{k^nx^n}{n!}\\
&=\frac{1}{e}\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\infty}\frac{k^n}{k!}\right)\frac{x^n}{n!}.
\end{align}
$$ 因此 $$
B_n=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{k!}.
$$ $\Box$

==== 例 8 ====

考虑符合下面要求的“合法”括号串：$n$ 个左括号与 $n$ 个右括号从左至右排成一排，要求在任何一个位置，其左边的左括号不比右括号少。令 $f_n$ 表示这样的合法括号串总数。显然 $f_1=1,f_2=2,f_3=5$。定义 $f_0=1$。求 $\{f_n\}_{n=0}^{\infty}$ 的生成函数。

解 令 $g_n$ 表示 $n$ 对括号能形成的本原括号串的总数。本原括号串不仅合法，而且在到达尽头之前任何一个位置，其左边的左括号始终比右括号多。因为每一个本原括号串去掉第一个左括号和最后一个右括号必为一个合法括号串，反之亦然，从而 $g_1=f_1,g_n=f_{n-1}$。设 $k$ 为一合法括号串从左开始第一次达到左、右括号数相等的左、右括号数，则 $1\le k\le n$，且有递推关系 $$
f_n=\sum_{k=1}^{n}g_kf_{n-k}=\sum_{k=1}^{n}f_{k-1}f_{n-k},~~~n\ge 1
$$ 注意 $n=0$ 时递推不成立。等号右边的形式让我们自然想到应该利用普通生成函数，而不是指数型生成函数。令 $f(x)$ 表示 $\{f_n\}_{n=0}^{\infty}$ 的普通生成函数。令 $b_0=0$，且当 $k\ge 1$ 时，$b_k=f_{k-1}$，则 $$
f_n=\sum_{k=1}^nf_{k-1}f_{n-k}=\sum_{k=1}^nb_kf_{n-k}=\sum_{k=0}^nb_kf_{n-k}.
$$ 这说明 $$
\begin{align}
f(x)-1&=\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n}b_kf_{n-k}\right)x^n+b_0f_n\\
&=\sum_{n=0}^{\infty}\left(\sum_{k=0}^nb_kf_{n-k}\right)x^n=\left(\sum_{n=0}^{\infty}b_nx^n\right)f(x)\\
&=\left(\sum_{n=1}^{\infty}f_{n-1}x^n\right)f(x)=xf^2(x),
\end{align}
$$ 从而 $$
f(x)=\frac{1\pm\sqrt{1-4x}}{2x}.
$$ 由初值 $f(0)=1$ 可知，应有 $$
f(x)=\frac{1-\sqrt{1-4x}}{2x}.
$$ 进一步计算可得 $$
f(x)=\sum_{n=1}^{\infty}2^{n-1}\frac{1\cdot3\cdot5\cdots(2n-3)}{n!}x^{n-1}=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n.
$$ 所以 $\displaystyle f_n=\frac{1}{n+1}\binom{2n}{n}$，此即 Catalan 数。

==== 例 9 ====

置换 $\sigma\in S_n$ 称为 **错位排列**，如果对任意 $1\le i\le n$，均有 $\sigma(i)\ne i$。令 $d_n$ 表示 $S_n$ 中错位排列的总数。易见 $$
n!=\sum_{k=0}^n\binom{n}{k}d_{n-k}.
$$ 这促使我们考虑 $d_n$ 的指数型生成函数 $\displaystyle D(x)=\sum_{n=0}^{\infty}d_n\frac{x^n}{n!}$。由于 $\{1\}_{n=0}^{\infty}$ 的指数型生成函数为 $e^x$，而 $\{n!\}_{n=0}^{\infty}$ 的指数型生成函数为 $$
\sum_{n\ge 0}\frac{n!}{n!}x^n=\sum_{n\ge 0}x^n=\frac{1}{1-x},
$$ 由前面的递推关系可得 $\displaystyle \frac{1}{1-x}=e^xD(x)$，即 $\displaystyle D(x)=\frac{e^{-x}}{1-x}$。

展开得到 $$
D(x)=\frac{e^{-x}}{1-x}=\frac{1}{1-x}\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}x^i=\sum_{n=0}^{\infty}\left(\sum_{i=0}^n\frac{(-1)^i}{i!}\right)x^n,
$$ 所以 $$
d_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.
$$ 这表明，在 $S_n$ 中任取一个置换，它是错位排列的概率为 $\displaystyle \frac{d_n}{n!}$，其极限是 $e^{-1}(n\rightarrow\infty)$。

==== 性质 10 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n,\displaystyle g(x)=\sum_{n=0}^{\infty}\frac{b_n}{n!}x^n\displaystyle h(x)=\sum_{n=0}^{\infty}\frac{c_n}{n!}x^n$（即 $f(x),g(x),h(x) $ 分别是数列 $\{a_n\}_{n=0}^{\infty},\{b_n\}_{n=0}^{\infty},\{c_n\}_{n=0}^{\infty}$ 的指数型生成函数），则 $f(x)g(x)h(x)$ 是数列 $$
\left\{\sum_{i+j+k=n\\~~i,j,k\ge 0}\binom{n}{i,j,k}a_ib_jc_k\right\}_{n=0}^{\infty}
$$ 的指数型生成函数。

==== 性质 11 ====

若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$（即 $f(x)$ 是数列 $\{a_n\}_{n=0}^{\infty}$ 的指数型生成函数），则 $f^k(x)$ 是数列 $$
\left\{\sum_{n_1+n_2+\cdots+n_k=n\\~~n_i\ge0,i=1,\cdots,k}\binom{n}{n_1,n_2,\cdots,n_k}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=0}^{\infty}
$$ 的指数型生成函数。

==== 定理 12 ====

令 $h_n$ 表示多重集 $S=\{n_1\cdot t_1,n_2\cdot t_2,\cdots,n_k\cdot t_k\}$ 的满足某种选取规则 $P$ 的 n-排列数，其中 $n_i\ge 0(1\le i\le k)$。记仅由 $t_i$ 组成的满足性质 $P$ 的 n-排列数为 $a_n^{(i)}$，数列 $\{a_n^{(i)}\}_{n=0}^{\infty}$ 的指数型生成函数为 $f_i(x)(1\le i\le k)$，则数列 $\{h_n\}_{n=0}^{\infty}$ 的指数型生成函数为 $$
h(x)=\prod_{i=1}^kf_i(x).
$$ 证明 设 $\displaystyle f_i(x)=\sum_{j=0}^{\infty}\frac{a_j^{(i)}}{j!}x^j(1\le i\le k)$，则 $$
\begin{align}
h_n&=\sum_{m_1+m_2+\cdots+m_k=n\\~~~~~~~0\le m_i\le n_i}\binom{n}{m_1,m_2,\cdots,m_k}\prod_{i=1}^ka_{m_i}^{(i)}\\
&=\sum_{m_1+m_2+\cdots+m_k=n\\~~~~~~~0\le m_i\le n_i}n!\frac{\prod_{i=1}^ka_{m_i}^{(i)}}{\prod_{i=1}^km_i!}=\left[\frac{x^n}{n!}\right]\prod_{i=1}^kf_i(x),
\end{align}
$$ 从而 $$
h(x)=\prod_{i=1}^kf_i(x)
$$ $\Box$

==== 注 ====

一般地，若 $n_i=\infty$，且所循规则 $P$ 对元素 $t_i$ 的选取没有限制，则 $$
f_i(x)=e^x;
$$ 若 $n_i<\infty$，且规则 $P$ 对元素 $t_i$ 的选取没有限制，则 $$
f_i(x)=\sum_{j=0}^{n_i}\frac{x^j}{j!}.
$$ 有时元素 $t_i$ 的选取受到限制，例如 $t_i$ 只能有大于 $1$ 的奇数个，此时 $t_i$ 满足该规则的 n-排列数即为 $$
a_j^{(i)}=
\begin{cases}
1,&j=3,5,7,9,\cdots,\\
0,&其他,
\end{cases}
$$ 于是 $$
f_i(x)=\sum_{j=1}^{\infty}\frac{x^{2j+1}}{(2j+1)!}=\frac{e^x-e^{-x}-2x}{2}.
$$ $\Box$

==== 例 13 ====

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

解 用 $h_n$ 表示这样的涂色方法数，且设数列 $\{h_n\}_{n=0}^{\infty}$ 的指数型生成函数为 $h(x)$。易见 $$
\begin{align}
h(x)&=\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\right)\left(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots\right)^2\\
&=\frac{1}{2}(e^x+e^{-x})(e^x)^2=\frac{1}{2}(e^{3x}+e^x)\\
&=\frac{1}{2}\left(\sum_{n=0}^{\infty}\frac{(3x)^n}{n!}+\sum_{n=0}^{\infty}\frac{x^n}{n!}\right)\\
&=\frac{1}{2}\sum_{n=0}^{\infty}(3^n+1)\frac{x^n}{n!},
\end{align}
$$ 因此 $$
h_n=\frac{3^n+1}{2}.
$$ $\Box$

==== 例 14 ====

确定每位数字都是奇数且 $1$ 和 $3$ 出现偶数次的 $n$ 位数个数 $h_n$。

解 设 $\{h_n\}_{n=0}^{\infty}$ 的指数型生成函数为 $h(x)$，则 $$
\begin{align}
h(x)&=\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\right)^2\left(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots\right)^3\\
&=\left(\frac{e^x+e^{-x}}{2}\right)^2e^{3x}=\frac{1}{4}(e^{5x}+2e^{3x}+e^x)\\
&=\sum_{n=0}^{\infty}\frac{5^n+2\cdot 3^n+1}{4}\cdot\frac{x^n}{n!}.
\end{align}
$$ 因此 $$
h_n=\frac{5^n+2\cdot 3^n+1}{4}.
$$
CVBB ACM Team

用户工具

站点工具

页面工具
