最后更新: 2025-01-22 09:05 查看: 184 次纠错评论(0) 课件开VIP

幂级数型生成函数

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

定义 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$ 。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：容斥原理

下一篇：指数型生成函数

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