习题 10

本节对应原书 PDF 第 263–266 页。习题题干逐字取自教材；答案逐字取自《离散数学习题解答与学习指导（第 3 版）》第 10 章「习题解答与分析」（PDF 第 172–184 页，印刷第 160–172 页）。AI 补充的中间步骤单独放在 details 折叠块中。

10.1 设有递推方程 L_n=L_{n-1}+L_{n-2}，n\geqslant 2，且 L_0=2，L_1=1，求 L_{2n+2}-(L_1+L_3+\cdots+L_{2n+1}).

10.2 求解递推方程.

（1）

（2）

（3）

（4）

（5）

10.3 求解下述递推方程.

（1）

（2）

10.4 已知方程 C_0H_n+C_1H_{n-1}+C_2H_{n-2}=6 的解是 3^n+4^n+2，求 C_1.

10.5 求以凸 n 边形的顶点为顶点，以内部对角线为边的不同三角形的个数.

10.6 有 n 条封闭的曲线，两两相交于两点，并且任意三条都不交于一点，求这 n 条封闭曲线把平面划分成的区域个数.

10.7 某公司有 n 千万元可以用于对 a,b,c 三个项目的投资.假设每年投资一个项目，投资的规则是：或者对 a 投资 1 千万元，或者对 b 投资 2 千万元，或者对 c 投资 2 千万元.问用完 n 千万元有多少种不同的方案？

10.8 求 n 位 0-1 串中相邻两位不出现 11 的串的个数.

10.9 一个质点在水平方向运动，每秒钟它走过的距离等于它前一秒走过距离的 2 倍.设质点的初始位置为 3，并设第一步走了 1 个单位长的距离.求第 t 秒钟质点的位置.

10.10 如图 10.10 所示，T 为 2n 个顶点的树，求 T 的所有点独立集（包含空集在内）的个数 I_n.

10.11 双 Hanoi 塔问题是 Hanoi 塔问题的一种推广，与 Hanoi 塔的不同点在于：2n 个圆盘，分成大小不同的 n 对，每对圆盘完全相同.初始，这些圆盘按照从大到小的次序从下到上放在 A 柱上，最终要把它们全部移到 C 柱，移动的规则与 Hanoi 塔移动规则相同.

（1）设计一个移动的算法；

（2）计算你的算法所需要的移动次数.

10.12 设 A 是 n 个不相等的正整数构成的集合，其中 n=2^k，k 为正整数.考虑下述在 A 中找最大和最小的算法 MaxMin.先将 A 划分成相等的两个子集 A_1 与 A_2.用算法 MaxMin 递归地在 A_1 与 A_2 中找最大与最小.令 a_1 与 a_2 分别表示 A_1 与 A_2 中的最大数，b_1 与 b_2 分别表示 A_1 与 A_2 中的最小数，那么 \max\{a_1,a_2\} 与 \min\{b_1,b_2\} 就是所需要的结果.计算对于规模为 n 的输入，算法 Maxmin 最坏情况下所作的比较次数.

10.13 一个 1\times n 的方格图形用红、蓝两色涂色每个方格，如果每个方格只能涂一种颜色，且不允许两个红格相邻，问有多少种涂色方案？

10.14 已知数列 \{a_n\} 的生成函数是 A(x)=(1+x-x^2)/(1-x)，求 a_n.

10.15 设数列 \{a_n\},\{b_n\},\{c_n\} 的生成函数分别为 A(x),B(x),C(x)，其中 a_n=0(n\geqslant 3)，a_0=1,a_1=3,a_2=2;c_n=5^n,n\in\mathbf{N}.如果 A(x)B(x)=C(x)，求 b_n.

10.16 分别确定下述数列 \{a_n\} 的生成函数，其中

（1）a_n=(-1)^n(n+1)

（2）a_n=(-1)^n2^n

（3）a_n=n+5

（4）a_n=\binom{n}{3}

10.17 证明生成函数的性质.

10.18 使用生成函数求解递推方程 a_k=3a_{k-1}，k=1,2,3,\cdots 且初始条件 a_0=2.

10.19 把 15 个相同的动物玩具分给 6 个孩子使得每个孩子至少得到 1 个但不超过 3 个，使用生成函数确定不同的分法数.

10.20 使用两个不同的信号在通信信道发送信息.传送一个信号需要 2\mu\mathrm{s}，传送另一个信号要 3\mu\mathrm{s}.一个信息的每个信号紧跟着下一个信号.

（1）设 a_n 是在 n\ \mu\mathrm{s} 可以发送的不同信号数，求与 a_n 有关的递推方程.

（2）对于(1)的递推方程，初始条件是什么？

（3）在 12\mu\mathrm{s} 内可以发送多少个不同的信息？

10.21 如果传送信号 A 要 1\mu\mathrm{s}，传送信号 B 和 C 各需要 2\mu\mathrm{s}，一个信息是字符 A，B 或 C 构成的有限长度的字符串（不考虑空串），问在 n\mu\mathrm{s} 内可以传送多少个不同的信息？

10.22 设 a_r 是用 3 元、4 元和 20 元的邮票在邮件上贴满 r 元邮费的方式数.求 \{a_r\} 的生成函数.

（1）假设不考虑贴邮票的次序.

（2）假设邮票贴成一行并且考虑贴的次序.

10.23 把 n 个苹果（n 为奇数）恰好分给 3 个孩子，如果第一个孩子和第二个孩子分的苹果数不相同，问有多少种分法？

10.24 设 n 为自然数，求平面上由直线 x+2y=n 与两个坐标轴所围成的直角三角形内（包括边上）的整点个数，其中整点表示横、纵坐标都是整数的点.

10.25 设三角形 ABC 的边长为整数，且 AB+BC+AC 为奇数 2n+1，其中 n 为给定的正

整数.问这样的三角形有多少个？

10.26 设 \Sigma 是一个字母表且 |\Sigma|=n>1，a 和 b 是 \Sigma 中两个不同的字母.试求 \Sigma 上的 a 和 b 均出现的长为 k>1 的字（或称为字符串）的个数.

10.27 冯·诺依曼邻居问题.某种细胞的增长遵照下述规则，每一次增长都是在上次的图形外面增加一圈方格.图 10.11 的三个图分别表示了初始格局及第 1 次、第 2 次增长后的细胞格局.如果第 n 次增长后阴影部分的方格数记作 T(n)（即 n 阶冯·诺依曼邻居中的元胞数），列出关于 T(n) 的递推方程及初值，求出 T(n).

10.28 设多重集 S=\{\infty\cdot a_1,\infty\cdot a_2,\infty\cdot a_3,\infty\cdot a_4\}，c_n 是 S 的满足以下条件的 n 组合数，且数列 \{c_n\} 的生成函数为 C(x)，求 C(x).

（1）每个 a_i 出现奇数次，i=1,2,3,4.

（2）a_1 不出现，a_2 至多出现 1 次.

（3）每个 a_i 至少出现 10 次.

10.29 分别确定下面数列 \{a_n\} 的指数生成函数，其中

（1）a_n=n!

（2）a_n=2^n\cdot n!

（3）a_n=(-1)^n

10.30 一个 1\times n 的方格图形用红、蓝、绿或橙色 4 种颜色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，问有多少种方案？

10.31 把 n 本不同的书分给 A,B,C,D 4 个人，使得 A 至少得 1 本，C 与 D 得到的书的数目同为奇数或者同为偶数，问这样的方法有多少种？

10.32 由 A,B,C,D,E,F 构成长度为 n 的序列，如果要求在排列中 A 与 B 出现的次数之和为偶数，问这样的排列有多少个？

10.33 设 A=\{1,2,\cdots,2n\}，B=\{1,2,\cdots,5\} 是有穷集.现在构造从 A 到 B 的函数 f:A\to B，如果对于任意 y\in\operatorname{ran}f，都有 |f^{-1}(y)| 等于偶数，其中 f^{-1}(y)=\{x\mid x\in A\wedge f(x)=y\} 表示 y 的完全原像.求满足上述条件的不同的函数 f 有多少个？

10.34 确定由 n 个奇数字组成并且 1 和 3 每个数字出现偶数次的数的个数.

10.35 证明：

10.36 把 5 项任务分给 4 个人，如果每个人至少得到 1 项任务，问有多少种方式？

10.3 习题解答与分析

10.1 解：

解读：第一步把括号拆开重新配对是关键：每层的 L_{2k+2}-L_{2k+1} 正好等于 L_{2k}，于是左端逐层"降阶"，最后只剩 L_2-L_1，而 L_2=L_1+L_0=3，故得 L_0=2.

10.2 （1）特征方程为 x^2-7x+12=0，通解为

代入初值，得到

解得 c_1=10,c_2=-6，从而得到原递推方程的解为

（2）特征方程为 x^2+1=0，通解为

代入初值，得到

解得 c_1=-\mathrm{i},c_2=\mathrm{i}，从而得到原递推方程的解为

于是原方程的解是

（3）特征方程为 x^2+6x+9=0，齐次通解为

设特解为 P，代入方程得到

解得 P=3/16.因此原递推方程的通解为

代入初值，解得 c_1=-3/16,c_2=-1/12.从而得到原递推方程的解为

（4）特征方程为 x^2-3x+2=0，齐次通解为

因为 1 是特征根，设特解为 Pn，代入方程得到 P=-1.因此原递推方程的通解为

代入初值，解得 c_1=1,c_2=3，从而得到原递推方程的解为

（5）特征方程为 x^2-7x+10=0，齐次通解为

设特解为 P3^n，代入方程得到 P=-\frac{9}{2}.因此原递推方程的通解为

代入初值解得 c_1=\frac{8}{3},c_2=\frac{11}{6}，从而得到原递推方程的解为

10.3 （1）令 b_n=na_n，代入原递推方程得

解得 b_n=-\frac{2}{3}(-1)^n+\frac{2^{n+1}}{3}，从而得到

（2）由迭代得到 a_n=n!(n+2)，经归纳法验证，它是原递推方程的解.

解读：10.3(2) 的迭代套路是先把递推式两边同除以 n!，得到 \frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=1，于是 \frac{a_n}{n!}=a_0+n，回代即得 a_n=n!(n+2).

10.4 方法 1 根据题意，递推方程的解为 H_n=3^n+4^n+2，令 n=0,1,2,3，代入得

将上述值代入已知条件，得下述方程组

解得 C_0=\frac{1}{2},C_1=-\frac{7}{2},C_2=6.

方法 2 由已知条件递推方程具有下述形式：

由于它的解是 H_n=3^n+4^n+2，因此上述递推方程的特征根是 3 和 4，特解是 2.从而知道这个递推方程也具有下面的形式：

对比这个方程的两种形式，得到 C_1=-7C_0,C_2=12C_0.

下面计算 C_0.由于特解是 2，因此得到

从而得到 C_0=\frac{1}{2}.再利用前面的结果得到 C_1=-\frac{7}{2},C_2=6.

10.5 方法 1 全部可能的三角形数 C(n,3)，其中以 1 条多边形边作为边的三角形数是 n(n-4)，以 2 条多边形边作为边的三角形数是 n，于是得到

方法 2 建立递推方程.设原来的 n-1 边形的顶点是 1,2,\cdots,n-1.加入顶点 n 以后，n 与 \{2,3,\cdots,n-2\} 中的任何两个顶点都能构成一个新的三角形，这样的新三角形有 C(n-3,2) 个.但是其中 n-4 个三角形含有多边形的 1 条边.因此仅由对角线构成的三角形有 C(n-3,2)-(n-4) 个.此外，原来 n-1 边形的边 \{1,n-1\} 在 n 边形中变成了对角线，由这条对角线与 \{3,4,\cdots,n-3\} 中的任何顶点都可以构成一个新三角形，且这个三角形的三条边都是 n 边形的对角线.因此又增加了 (n-5) 个三角形.令 A_n 表示所有的三角形数，那么 A_n 满足如下递推方程

解得 A_n=n(n-4)(n-5)/6.

10.6 设 a_n 为 n 条封闭曲线把平面划分成的区域个数.假设前 n 条封闭曲线已经存在，当加入第 n+1 条封闭曲线时，这条曲线与前 n 条曲线交于 2n 个点，这些交点将第 n+1 条曲线划分成 2n 段，每段都会增加一个区域，因此得到递推方程

解得 a_n=n^2-n+2.

10.7 设 n 千万元的投资方案数为 f(n)，那么 f(n) 满足如下递推方程

解得 f(n)=\frac{2^{n+1}+(-1)^n}{3}.

10.8 设 a_n 是不含两个连续 1 的 n 位 0-1 字符串的个数，b_n 是以 1 结尾且不含两个连续 1 的 n 位 0-1 字符串的个数，c_n 是以 0 结尾且不含两个连续 1 的 n 位 0-1 字符串的个数，那么 a_n=b_n+c_n，且满足如下递推方程

解得

10.9 设 f(t) 为第 t 秒时质点的位置，则

化简并给出初值

该方程为常系数线性齐次递推方程，解得 f(t)=2^t+2.

10.10 将这个图的点独立集分成两类：含有顶点 n 的和不含有顶点 n 的.如果含有顶点 n，那么一定不含有顶点 2n 和 n-1，但是可以含有或者不含有顶点 2n-1，对其他顶点的取含有 f_{n-2} 种方法.如果不含有顶点 n，那么可以含有或者不含有顶点 2n，对其他顶点的取含有 f_{n-1} 种方法.于是得到递推方程

解得

10.11 （1）算法分三步，具体步骤如下：

① 递归地将上面的 2(n-1) 个盘子从 A 柱移到 B 柱；

② 用 2 次移动将最大的 2 个盘子从 A 柱移到 C 柱；

③ 递归地将 B 柱的 2(n-1) 个盘子从 B 柱移到 C 柱.

（2）设 2n 个圆盘的移动次数是 T(n)，则

通过迭代解得

10.12 设算法对于规模为 n 的输入在最坏情况下的比较次数是 T(n)，那么有

通过迭代解得

10.13 设 a_n 是 n 个方格的涂色方案数，将这些方案按照最后一个方格是红色和蓝色分成两类.如果最后一个方格是红色，那么相邻的方格一定是蓝色，这种方案有 a_{n-2} 种；如果最后一个方格是蓝色，这种方案有 a_{n-1} 种，因此得到递推方程

从而解得

10.14 A(x)=\frac{1+x-x^2}{1-x}=x+\frac{1}{1-x}=x+\sum\limits_{n=0}^{\infty}x^n

从而得到 a_n=1(n\neq 1),a_1=2.

10.15 方法 1 根据题意给出递推方程

将已知条件代入得

解得 b_n=\frac{4}{7}(-2)^n-\frac{1}{6}(-1)^n+\frac{5^{n+2}}{42}.

方法 2 根据已知条件得到

于是得到

从而得到

10.16 （1）A(x)=\sum\limits_{n=0}^{\infty}(-1)^n(n+1)x^n

（2）A(x)=\sum\limits_{n=0}^{\infty}(-1)^n2^nx^n=\sum\limits_{n=0}^{\infty}(-2x)^n=\frac{1}{1+2x}

（3）A(x)=\sum\limits_{n=0}^{\infty}(n+5)x^n=\sum\limits_{n=0}^{\infty}(n+1)x^n+\sum\limits_{n=0}^{\infty}4x^n

令 B(x)=\sum\limits_{n=0}^{\infty}(n+1)x^n，则

从而得到

（4）与前面(1)和(3)小题类似，利用级数积分的性质，最终得到生成函数 \frac{x^3}{(1-x)^4}.

10.17 性质 1 B(x)=\sum\limits_{n=0}^{\infty}b_nx^n=\sum\limits_{n=0}^{\infty}\alpha a_nx^n=\alpha\sum\limits_{n=0}^{\infty}a_nx^n=\alpha A(x)

性质 2 C(x)=\sum\limits_{n=0}^{\infty}c_nx^n=\sum\limits_{n=0}^{\infty}(a_n+b_n)x^n=\sum\limits_{n=0}^{\infty}a_nx^n+\sum\limits_{n=0}^{\infty}b_nx^n=A(x)+B(x)

性质 3 根据条件列出下述等式

将以上各式两边分别相加并化简，得到

性质 4 B(x)=\sum\limits_{n=0}^{\infty}b_nx^n=\sum\limits_{n=l}^{\infty}a_{n-l}x^n=x^l\sum\limits_{n=l}^{\infty}a_{n-l}x^{n-l}=x^l\sum\limits_{n=0}^{\infty}a_nx^n=x^lA(x)

性质 5 B(x)=\sum\limits_{n=0}^{\infty}b_nx^n=\sum\limits_{n=0}^{\infty}a_{n+l}x^n

性质 6 根据已知条件列出下述等式

将上式两边相加，得到

性质 7 因为 A(1) 收敛，所以 b_n=\sum\limits_{i=0}^{\infty}a_i 存在.

将上式两边分别相加并化简，命题得证.

性质 8 B(x)=\sum\limits_{n=0}^{\infty}b_nx^n=\sum\limits_{n=0}^{\infty}a^na_nx^n=\sum\limits_{n=0}^{\infty}a_n(ax)^n=A(ax)

性质 9 A(x)=\sum\limits_{n=0}^{\infty}a_nx^n

对 x 求导得到

于是 B(x)=xA'(x).

性质 10 B(x)=\sum\limits_{n=0}^{\infty}b_nx^n=\sum\limits_{n=0}^{\infty}\frac{a_n}{n+1}x^n

10.18 根据生成函数定义，得到

解得

于是得到 a_k=2\times 3^k.

10.19 设 x_1,x_2,\cdots,x_6 分别表示 6 个孩子得到的玩具数目，因此得到如下不定方程

该方程对应的生成函数是

上述多项式展开式中 y^{15} 的系数就是 (1+y+y^2)^6 的展开式中 y^9 的系数.于是得到

于是得到方程的正整数解有 50 个，即分配玩具有 50 种方法.

10.20 （1）设 a_n 表示 n\mu\mathrm{s} 传送的不同的信息数，那么

（2）a_1=0,a_2=1,a_3=1.

（3）从 a_4=a_2+a_1,a_5=a_3+a_2,\cdots，顺序计算可得 a_{12}=12.

10.21 设 a_n 表示 n\mu\mathrm{s} 送的不同信息数，那么得到递推方程如下

解得 a_n=\frac{2^{n+1}+(-1)^n}{3}.

10.22 （1）如果不考虑邮票的顺序，每种邮票使用的张数不同决定了不同的方案.设 3 元、4 元和 20 元的邮票分别使用 x_1,x_2 和 x_3 张，则得到下述方程

于是，生成函数为

G(y) 的展开式中 y^r 的系数就是方案数.

（2）如果考虑邮票的顺序，那么贴 k 张邮票可能得到的总邮资数值由 (y^3+y^4+y^{20})^k 中 y 的幂指数确定，而对于给定的邮资，其系数则代表了用 k 张邮票贴出这种邮资的方法数.如

这说明用 3 张邮票贴 9 元邮资只有 1 种方法，贴 11 元邮资有 3 种方法，即：3+4+4，4+4+3，4+3+4，\cdots.根据上述分析，考虑邮票顺序情况下的生成函数是

上述展开式中 y^r 的系数就是贴出 r 元邮资的方法数.

10.23 每个孩子至少得到一个苹果的分法数是方程 x_1+x_2+x_3=n-3 的非负整数解的个数，其生成函数为

上述展开式中 y^{n-3} 项的系数为 \frac{(n-1)(n-2)}{2}.

前两个孩子苹果数相等的分法数为方程 2x_1+x_3=n-3 的非负整数解个数.当 n 为奇数时，x_3 为偶数，有 \frac{n-1}{2} 种取法，于是

10.24 整点个数为以下方程非负整数解的个数 a_r

设关于 \{a_r\} 的生成函数为

于是

10.25 方法 1 设 AB,BC,AC 三边的边长分别为 x_1,x_2,x_3，则

以上条件等价于 x_1,x_2,x_3<n+1.

设 N_1 是所有可能的三角形个数，N_2 是一条边长超过 n 的三角形数.考虑不加限制条件的所有正整数解的序列所对应的生成函数 A(y)，则

展开式中 y^{2n+1} 的系数是 N_1=(2n+3)(n+1).

如果一条边长超过 n，这种三角形数 N_2 相当于方程 x_1+x_2+x_3=n 的非负整数解的个数，这个数是 N_2=\frac{1}{2}(n+2)(n+1).由于三条边总长等于 2n+1，不可能两条边同时超过 n，于是所求的三角形数

方法 2 根据题意写出生成函数如下

上述展开式中 y^{2n+1} 项的系数为

10.26 方法 1 设所求的 k 位字符串的个数为 a_k，\{a_k\} 的指数生成函数为

x^k 的系数为

因此所求字符串的个数为 a_k=n^k-2(n-1)^k+(n-2)^k.

方法 2 设 S 表示 \Sigma 上的长为 k 的字符串的集合，构造子集

其中

根据包含排斥原理，所求的字符串的个数为

10.27 根据给定条件列出递推方程如下：

根据迭代解得

10.28 （1）C(x)=(x+x^3+\cdots)^4=\frac{x^4}{(1-x^2)^4}

（2）C(x)=(1+x)(1+x+x^2+\cdots)^2=\frac{1+x}{(1-x)^2}

（3）C(x)=(x^{10}+x^{11}+x^{12}+\cdots)^4=\frac{x^{40}}{(1-x)^4}

10.29 （1）G_e(x)=\sum\limits_{n=0}^{\infty}n!\frac{x^n}{n!}=\sum\limits_{n=0}^{\infty}x^n=\frac{1}{1-x}

（2）G_e(x)=\sum\limits_{n=0}^{\infty}2^nn!\frac{x^n}{n!}=\sum\limits_{n=0}^{\infty}(2x)^n=\frac{1}{1-2x}

（3）G_e(x)=\sum\limits_{n=0}^{\infty}(-1)^n\frac{x^n}{n!}=\mathrm{e}^{-x}

10.30 指数生成函数为

10.31 列出指数生成函数如下：

解得

10.32 方法 1 用指数生成函数

方法 2 设序列数为 a_n，则

解得

10.33 一个函数 f:A\to B 是集合

每个函数对应于序列 \langle y_1,y_2,\cdots,y_{2n}\rangle，其中函数值 y_1,y_2,\cdots,y_{2n} 取自集合 B=\{1,2,\cdots,5\}，可以把 \langle y_1,y_2,\cdots,y_{2n}\rangle 看作 B 的一个有序可重复的选择，并且每个元素 1,2,\cdots,5 在其中都出现偶数次.容易看出，每个元素出现的次数不超过 2n.

设选法数是 a_k，\{a_k\} 的指数生成函数是：

其 x^k/k! 的系数是：

当 k=2n 时，

例如，当 n=1 时，通过 y_1 与 y_2 的选择构成的 \langle y_1,y_2\rangle 只有 5 种，即 \langle 1,1\rangle,\langle 2,2\rangle,\langle 3,3\rangle,\langle 4,4\rangle,\langle 5,5\rangle，而

10.34 设组成 n 位数的个数为 a_n，则

使用指数生成函数，求得

10.35 等式右边对应了将 n 个不同的球放到 x 个不同的盒子且允许空盒的方法数，即 x^n.将这些方法按照含有球的盒子个数进行分类，只放入 k 个盒子的方法数是

因此总方法数需要对 k 求和，这就得到等式左边的公式.

解读：10.35 的证明思路是"数两次同一个集合"：左边把 x^n 按实际用到的盒子个数 k 拆开，\binom{x}{k} 选盒子、\begin{Bmatrix}n\\ k\end{Bmatrix} 分组、k! 给盒子编号，合起来恰好是 \begin{Bmatrix}n\\ k\end{Bmatrix}x(x-1)\cdots(x-k+1).

10.36 方法 1 把工作分配看作从 5 个工作的集合到 4 个雇员的集合的函数.每个雇员至少得到 1 项工作的分配方案，对应于从工作集合到雇员集合的一个满射函数.因此

因此存在 240 种方式来分配工作.

方法 2 设所有的分配方案构成集合 S，雇员 i 没有得到工作的分配方案构成子集 A_i，i=1,2,3,4.那么

代入包含排斥原理，得到