最后更新: 2025-01-22 09:05 ● 参与者查看: 11 次纠错分享参与项目词条搜索

幂级数型生成函数

递推关系与生成函数都是组合数学中非常重要的工具，常用于求解组合计数问题。特别
是在分析算法复杂性和设计动态规划以及递归算法时，具有强大的功效。由于在求解递推关
系时经常需要用到生成函数，本章将先介绍生成函数的相关理论与应用

定义 7.1 设 $a_1, a_2, \cdots, a_n \cdots$ 是一个数列，构造形式幂级数

$$
f(x)=a_0+a_1 x+a_2 x^2+\cdots+a_n x^n+\cdots
$$

称 $f(x)$ 是数列 $a_1, a_2, \cdots, a_n, \cdots$ 的生成函数，且两个形式幂级数 $\sum_{i=0}^{\infty} a_i x^i$ 和 $\sum_{i=0}^{\infty} b_i x^i$相等，当且仅当对每个 $i$ 有 $a_i=b_i$ 。

对于有限序列，可看成自某项后全为 0 的无穷序列。
定理 7.1 设数列 $\left\{a_n\right\},\left\{b_n\right\},\left\{c_n\right\}$ 的生成函数分别是 $f(x), g(x)$ 和 $h(x), r$ 为常数。
（1）如果 $b_n=r a_n$ ，则 $g(x)=r f(x)$ 。
（2）如果 $c_n=a_n+b_n$ ，则 $h(x)=f(x)+g(x)$ 。
（3）如果 $c_n=\sum_{i=0}^n a_i b_{n-i}$ ，则 $h(x)=f(x) \square g(x)$ 。
（4）如果

$$
b_n=\left\{\begin{array}{ll}
0 & n<l \\
a_{n-1} & n \geqslant l
\end{array} \circ\right.
$$

则 $g(x)=x^l \square f(x)$ 。
（5）如果 $b_n=a_{n+l}$ ，则

$$
g(x)=\frac{f(x)-\sum_{n=0}^{l-1} a_n x^n}{x^l}
$$

（6）如果 $b_n=\sum_{i=0}^n a_i$ ，则

$$
g(x)=\frac{f(x)}{1-x}
$$

（7）如果 $b_n=\sum_{i=0}^{\infty} a_i$ ，且 $f(1)=\sum_{n=0}^{\infty} a_n$ 收敛，则

$$
g(x)=\frac{f(1)-x f(x)}{1-x} \text { 。 }
$$

（8）如果 $b_n=r^n a_n$ ，则 $g(x)=f(r x)$ 。
（9）如果 $b_n=n a_n$ ，则 $g(x)=x f^{\prime}(x)$ 。
（10）如果 $b_n=\frac{a_n}{n+1}$ ，则 $g(x)=\frac{1}{x} \int_0^x f(x) d x$ 。
证明留作习题。
例7．1（1）设有质量分别为 $n_1$ 克，$n_2$ 克，$\cdots, n_k$ 克的 $k$ 个砝码。现要用天平称 $i$ 克的物体，物体放在左边，砝码放在右边，共有多少种不同称法？
（2）用质量分别为 1 克， 2 克， 4 克， 8 克， 16 克的 5 个砝码，在天平上能称几种质量的物体？每种质量的物体有几种不同的称法？
（3）用 2 个质量为 1 克， 3 个质量为 2 克， 2 个质量为 5 克的砝码在天平上能称几种质量的物体？且每种质量的物体有几种不同的称法？

解：（1）设有 $a_i$ 种方法称 $i$ 克物体。下面研究 $k$ 个形式幂级数的积

$$
\left(1+x^{n_1}\right)\left(1+x^{n_2}\right) \cdots\left(1+x^{n_k}\right)
$$

它的展开式中 $x^i$ 幂来源于

$$
x^{m_1} x^{m_2} \cdots x^{m_k}=x^i, \quad m_1+m_2+\cdots+m_k=i, \quad m_j \in\left\{0, n_j\right\}
$$

其中第一个括弧提供 $m_1$ 次幂，第二个括弧提供 $m_2$ 次幂，$\cdots$ ，第 $k$ 个括弧提供 $m_k$ 次幂，$m_j=0$表示 $n_j$ 克砝码没有用上，$m_j=n_j$ 表示 $n_j$ 克砝码用上了，因此展开式中 $x^i$ 的系数恰好是称 $i$ 克物体的方法数，故有

$$
\left(1+x^{n_1}\right)\left(1+x^{n_2}\right) \cdots\left(1+x^{n_k}\right)=\sum_{i=0}^{\infty} a_i x^i
$$

（2）设质量 $r$ 克物体有 $a_r$ 种称法，则数列 $\left\{a_r\right\}$ 的生成函数是

$$
\begin{aligned}
& f(x)=(1+x)\left(1+x^2\right)\left(1+x^4\right)\left(1+x^8\right)\left(1+x^{16}\right) \\
& (1-x) f(x)=(1-x)(1+x)\left(1+x^2\right)\left(1+x^4\right)\left(1+x^8\right)\left(1+x^{16}\right)=1-x^{32}
\end{aligned}
$$

所以

$$
f(x)=\frac{1-x^{32}}{1-x}=1+x+x^2+\cdots+x^{31}
$$

这表明凡是不超过 31 克的物体都能用给定的 5 个砝码称出，且每个恰有一种称法。
（3）设质量 $r$ 克物体有 $a_r$ 种称法，则数列 $\left\{a_r\right\}$ 的生成函数是

$$
\begin{aligned}
& f(x)=\left(1+x+x^2\right)\left(1+x^2+\left(x^2\right)^2+\left(x^2\right)^3\right)\left(1+x^5+\left(x^5\right)^2\right) \\
& =1+x+2 x^2+x^3+2 x^4+2 x^5+3 x^6+3 x^7+2 x^8+2 x^9+2 x^{10}+3 x^{11}+3 x^{12} \\
& +2 x^{13}+2 x^{14}+x^{15}+2 x^{16}+x^{17}+x^{18}
\end{aligned}
$$
这表明凡是质量不超过 18 克的物体都能用给定的砝码称出。其中质量为 $1,3,15,17$ ， 18 克的只有一种称法，质量为 $2,4,5,8,9,10,13,14,16$ 克的物体有 2 种称法，而质量为 $6,7,11,12$ 克的物体有 3 种称法。

从上例中看出用生成函数可比较容易地解决一些计数问题。下面用生成函数来求多重集的 $r$－组合数。

例7．2 设多重集 $S=\left\{\infty \square x_1, \infty \square x_2, \cdots, \infty \square x_k\right\}, S$ 的 $r$－组合数是 $a_r=C(r+k-1, r)$ ，它也是方程 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的个数。现用生成函数的方法求 $a_r$ 。设 $\left\{a_r\right\}$ 的生成函数为 $f(y)$ ，构造幂级数 $\left(1+y+y^2+\cdots\right)^k$ ，把这个式子展开后，$y^r$ 幂来源于

$$
y^{x_1} y^{x_2} \cdots y^{x_k}=y^{x_1}+x_2+\cdots+x_k, \quad x_1+x_2+\cdots+x_k=r
$$

其中 $y^{x_1}$ 来自第一个因式 $\left(1+y+y^2+\cdots\right), y^{x_2}$ 来自第二个因式 $\left(1+y+y^2+\cdots\right), \cdots, y^{x k}$ 来自第 $k$ 个因式 $\left(1+y+y^2+\cdots\right)$ ，且 $x_1+x_2,+\cdots, x_k$ 为非负整数。因此展开式中 $y^r$ 的系数对应了不定方程 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的个数。故所构造的幂级数就是 $\left\{a_r\right\}$ 的生成函数 $f(y)$ 。由推 论 6.4 可得

$$
f(y)=\frac{1}{(1-y)^k}=\sum_{r=0}^{\infty} C(k+r-1, r) y^r
$$

所以 $a_r=C(k+r-1, r)$ 。
设多重集 $S=\left\{n_1 \sqcap a_1, n_2 \sqcap a_2, \cdots, n_k \sqcap a_k\right\}, S$ 的 $r$ 组合数 $a_r$ 就相当于方程 $x_1+x_2+\cdots+x_k=r$ ， $x_1 \leqslant n_1, x_2 \leqslant n_2, \cdots, x_k \leqslant n_k$ 的非负整数解的组数。设 $\left\{a_r\right\}$ 的生成函数 $f(y)$ ，类似可以得到 $f(y)=\left(1+y+y^2+\cdots+y^{n_1}\right)\left(1+y+y^2+\cdots+y^{n_2}\right) \cdots\left(1+y+y^2+\cdots+y^{n_k}\right)$ 则 $f(y)$ 的展开式中 $x^r$ 的系数 $a_r$ 就是所求的 $S$ 的 $r$－组合数。

例 7.3 设 $S=\left\{\infty \square x_1, \infty \square x_2, \cdots, \infty \square x_k\right\}$ ，求 $S$ 的每个元素只出现偶数次的 $r$ 组合数 $a_r$ 。
解：令 $\left\{a_r\right\}$ 的生成函数为 $f(y)$ ，则

$$
\begin{gathered}
f(y)=\left(1+y^2+y^4+\cdots\right)^k=\frac{1}{\left(1+y^2\right)^k} \\
=1+k y^2+C(k+1,2) y^4+\cdots+C(k+n-1, n) y^{2 n}+\cdots
\end{gathered}
$$

所以有

$$
a_r=\left\{\begin{array}{cl}
C\left(k+\frac{r}{2}-1, \frac{r}{2}\right) & r=2 n(n=0,1, \cdots) \\
0 & r=2 n+1(n=0,1, \cdots)
\end{array}\right.
$$

同样地，用生成函数的方法也可求解不定方程的整数解组数。
例 7.4 求 $x_1+x_2+x_3=5\left(0 \leqslant x_1, 0 \leqslant x_2, 1 \leqslant x_3\right)$ 的整数解组数。
解：令 $x_3^{\prime}=x_3-1$ ，则原问题即为求在约束条件下，

$$
0 \leqslant x_1, \quad 0 \leqslant x_2, \quad 1 \leqslant x_3^{\prime}
$$

$x_1+x_2+x_3^{\prime}=4$ 的非负整数解组数。设解的组数为 $a_4,\left\{a_r\right\}$ 的生成函数是

$$
f(y)=\frac{1}{(1-y)^3}=\sum_{r=0}^{\infty} C(r+2, r) y^r
$$

所以有 $a_4=C(4+2,4)=15$ 。

上一篇：容斥原理

下一篇：指数型生成函数

本文对您是否有用？有用 (0) 无用 (0)