《离散数学及其应用》第四章第一节习题解

下学期学算法设计与分析，预习了下，发现递推方程十分重要，这本来是大一离散数学的内容，但是我们课程精简掉了这部分… 于是找出大一买的《离散数学及其应用》¹，顺便刷下题。我的这本是精编版，章节和原版可能不同，第四章是 Advanced Counting Techniques（高级计数技巧），第一节是 Applications of Recurrence Relations（递推式的应用）。

习题解

4.1.1

Use mathematical induction to verify the formula derived in Example 2 for the number of moves required to complete the Tower of Hanoi puzzle.

用数学归纳法验证例 2 中导出的解决河内塔问题（汉诺塔问题）所需步数的公式。

解决河内塔问题所需步数的公式为

\[ H_n = 2^n - 1. \]

现在用数学归纳法验证之.

证　当 $n = 1$ 时，$H_1 = 2^1 - 1 = 1$. 原塔柱只有 $1$ 片圆盘时，只需用 $1$ 步将该片圆盘移动到目标塔柱即可，该情况成立.

假设 $n = k \; (k > 1)$ 时公式成立，即有 $H_k = 2^k - 1$.

$n = k + 1 \; (k > 1)$ 时，先用 $H_k$ 步将原塔柱最上面 $k$ 片圆盘移动到辅助塔柱，再用 $1$ 步将原塔柱剩下的 $1$ 片圆盘移动到目标塔柱，最后用 $H_k$ 步将辅助塔柱所有圆盘移动到目标塔柱. 因此有

\[ H_{k+1} = 2 H_k + 1 = 2 \cdot (2^k - 1) + 1 = 2^{k+1} - 1, \]

得证.　$\Box$

4.1.2

A vending machine dispensing books of stamps accepts only one-dollar coins, $\$1$ bills, and $\$5$ bills.

a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, where the order in which the coins and bills are deposited matters.

b) What are the initial conditions?

c) How many ways are there to deposit $\$10$ for a book of stamps?

现有一台贩卖整套邮票的机器，只接收 1 美元硬币、1 美元纸币、5 美元纸币.

1) 求投入 $n$ 美元的不同投法数的递推式，要考虑硬币和纸币投入的顺序.

2) 初始条件是什么？

3) 投入 10 美元购买一套邮票，共有多少种投币方法？

解　1) 投入 $n$ 美元可分为两种情况：其一，先投入 $n - 1$ 美元，再投入 $1$ 美元；其二，先投入 $n - 5$ 美元，再投入 $5$ 美元. 记投入 $n$ 美元的投法数为 $f(n)$，则根据分步计数乘法原理，前者有 $f(n-1) \cdot 2$ 种投法（投入 $1$ 美元有硬币和纸币两种投法），后者有 $f(n-5) \cdot 1$ 种投法. 由分类计数加法原理，递推式为

\[f(n) = 2 f(n-1) + f(n-5), \; n > 1.\]

2) 上述递推式的初始条件为 \[ \begin {equation*} \left\{ \begin {array}{c} f(n) = 0, & \quad n < 0 \\ f(0) = 1, & \\ f(1) = 2. & \\ \end {array} \right. \end {equation*} \] 3) 将 $n = 10$ 代入递推式得 \[ \begin {align*} f(10) & = 2 f(9) + f(5) \\ & = 2 \cdot [2 f(8) + f(4)] + 2 f(4) + f(0) \\ & = 2^2 f(8) + 2^2 f(4) + 1 \\ & = 2^2 \cdot [2 f(7) + f(3)] + 2^2 \cdot [2 f(3) + f(-1)] + 1 \\ & = 2^3 f(7) + 3 \cdot 2^2 f(3) + 1 \\ & = \cdots \\ & = 2^5 \cdot [2^4 f(1) + 1] + 5 \cdot 2^4 f(1) + 1 \\ & = 2^{10} + 6 \times 2^5 + 1 \\ & = 1217. \end {align*} \]

4.1.3

A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. How many ways are there to pay a bill of 17 pesos, where the order in which coins and bills are paid matters?

某国用比索作为货币单位，有面值为 1 比索、2 比索、5 比索、10 比索的硬币，以及面值为 5 比索、10 比索、20 比索、50 比索、100 比索的纸币。现要付 17 比索的账单，有多少种方法？要考虑硬币和纸币的顺序.

解　待解

4.1.4

a) Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive 0s.

b) What are the initial conditions?

c) How many strings of length seven contain two consecutive 0s?

1) 求包含两个连续的 0 且长度为 $n$ 的二进制串个数的递推式。

2) 初始条件是什么？

3) 包含两个连续的 0 且长度为 7 的二进制串有多少个？

解　1) 记这样的二进制串个数为 $f(n)$. 分两种情况：其一，最后一位为 1，则最后一位和前 $n - 1$ 位不可能组成新的 00，所以有 $f(n-1)$ 个这样的串；其二，最后一位为 0，则若倒数第二位为 1，最后两位和前 $n - 2$ 位不可能组成新的 00，所以有 $f(n-2)$ 个这样的串，若倒数第二位为 0，前 $n -2$ 位不管如何组合，结果都是含 00 的串，前 $n - 2$ 位有 $2^{n-2}$ 种可能，最后两位已确定只有一种可能，即有 $2^{n-2} \cdot 1$ 个这样的串. 因此总数为

\[f(n) = f(n-1) + f(n-2) + 2^{n-2}, \; n > 2.\]

2) 上述递推式的初始条件为 \[ \begin {equation*} \left\{ \begin {array}{c} f(1) = 0, \\ f(2) = 1. \\ \end {array} \right. \end {equation*} \] 3) 反复应用递推式可得 \[ \begin {align*} f(3) & = f(2) + f(1) + 2^1 = 3, \\ f(4) & = f(3) + f(2) + 2^2 = 8, \\ f(5) & = f(4) + f(3) + 2^3 = 19, \\ f(6) & = f(5) + f(4) + 2^4 = 43, \\ f(7) & = f(6) + f(5) + 2^5 = 94. \end {align*} \]

4.1.5

a) Find a recurrence relation for the number of bit strings of length $n$ that do not contain three consecutive 0s.

b) What are the initial conditions?

c) How many strings of length seven do not contain three consecutive 0s?

1) 求不包含三个连续的 0 且长度为 $n$ 的二进制串个数的递推式。

2) 初始条件是什么？

3) 不包含三个连续的 0 且长度为 7 的二进制串有多少个？

解　1) 记这样的二进制串个数为 $f(n)$. 若串的最后一位为 1，则 $f(n) = f(n-1)$. 否则（最后一位为 0），若倒数第二位为 1，则 $f(n) = f(n-2)$. 否则（串以 00 结尾），若倒数第三位为 1，则 $f(n) = f(n-3)$. 否则（串以 000 结尾），$f(n) = 0$.

综上，

\[f(n) = f(n-1) + f(n-2) + f(n-3), \; n > 3.\]

2) 上述递推式的初始条件为 \[ \begin {equation*} \left\{ \begin {array} {c} f(1) = 2, \\ f(2) = 4, \\ f(3) = 7. \end {array} \right. \end {equation*} \] 3) 反复应用递推式可得 \[ \begin {align*} f(4) & = f(3) + f(2) + f(1) = 13, \\ f(5) & = f(4) + f(3) + f(2) = 24, \\ f(6) & = f(5) + f(4) + f(3) = 44, \\ f(7) & = f(6) + f(5) + f(4) = 81. \end {align*} \]

4.1.6

a) Find a recurrence relation for the number of ways to climb $n$ stairs if the person climbing the stairs can take one stair or two stairs at a time.

b) What are the initial conditions?

c) In how many ways can this person climb a flight of eight stairs?

1) 一个人一次能爬一级或两级楼梯，求这个人爬 $n$ 级楼梯的不同方法数的递推式。

2) 初始条件是什么？

3) 这个人爬 8 级楼梯有多少种方法？

解　1) 记这样的方法数为 $f(n)$. 分两种情况：先爬 $n - 2$ 级楼梯，再一次爬 $2$ 级楼梯；先爬 $n - 1$ 级楼梯，再爬 $1$ 级楼梯. 因此 $f(n) = f(n-1) + f(n-2), \; n > 2$.

2) 上述递推式的初始条件为 \[ \begin {equation*} \left\{ \begin {array} {c} f(1) = 1, \\ f(2) = 2. \end {array} \right. \end {equation*} \] 3) 反复应用递推式可得 \[ \begin {align*} f(3) & = f(2) + f(1) = 3, \\ f(4) & = f(3) + f(2) = 5, \\ f(5) & = f(4) + f(3) = 8, \\ f(6) & = f(5) + f(4) = 13, \\ f(7) & = f(6) + f(5) = 21, \\ f(8) &= f(7) + f(6) = 34. \end {align*} \]

4.1.7

A string that contains only 0s, 1s, and 2s is called a ternary string.

a) Find a recurrence relation for the number of ternary strings of length $n$ that do not contain two consecutive 0s.

b) What are the initial conditions?

c) How many ternary strings of length six do not contain two consecutive 0s?

只包含 0, 1, 2 的串称为三进制串。

1) 求不包含两个连续的 0 且长度为 $n$ 的三进制串个数的递推式。

2) 初始条件是什么？

3) 不包含两个连续的 0 且长度为 6 的三进制串有多少个？

解　1) 记这样的三进制串个数为 $f(n)$. 分两种情况：其一，最后一位为 1 或 2，则最后一位和前 $n - 1$ 位不可能组成新的 00，所以有 $2 f(n-1)$ 个这样的串；其二，最后一位为 0，则若倒数第二位为 1 或 2，最后两位和前 $n - 2$ 位不可能组成新的 00，所以有 $2 f(n-2)$ 个这样的串，因此总数为

\[f(n) = 2 f(n-1) + 2 f(n-2), \; n > 2.\]

2) 上述递推式的初始条件为 \[ \begin {equation*} \left\{ \begin {array} {c} f(1) = 3, \\ f(2) = 8. \end {array} \right. \end {equation*} \] 3) 反复应用递推式可得 \[ \begin {align*} f(3) & = 2 f(2) + 2 f(1) = 22, \\ f(4) & = 2 f(3) + 2 f(2) = 60, \\ f(5) & = 2 f(4) + 2 f(3) = 164, \\ f(6) & = 2 f(5) + 2 f(4) = 448. \end {align*} \]

4.1.10

Messages are transmitted over a communication channel using two signals. The transmittal of one signal requires 1 microsecond, and the transmittal of the other signal requires 2 microseconds.

a) Find a recurrence relation for the number of different messages consisting of sequences of these two signals, where each signal in the message is immediately followed by the next signal, that can be sent in $n$ microseconds.

b) What are the initial conditions?

c) How many different messages can be sent in 10 microseconds using these two signals?

消息通过两种信号在一条信道上传输。其中一种信号传输耗时 1 微秒，另一种信号传输耗时 2 微秒。

1) 求这两种信号的序列所组成的、传输需时 $n$ 微秒的不同消息数的递推式。

2) 初始条件是什么？

3) 使用这两种信号、传输需时 10 微秒的不同消息有多少种？

解　1) 思路与 4.1.6 完全类似。递推式为 $f(n) = f(n-1) + f(n-2), \; n > 2$.

4.1.11

a) Find the recurrence relation satisfied by $R_n$, where $R_n$ is the number of regions that a plane is divided into by $n$ lines, if no two of the lines are parallel and no three of the lines go through the same point.

b) Find $R_n$ using iteration.

1) 求 $R_n$ 所满足的递推式，$R_n$ 是指 $n$ 条直线可将一个平面分成的区域数（假设任意两条直线不平行，任意三条直线不经过同一点）。

2) 用迭代法求 $R_n$。

解　1) 注意到条件“任意两条直线不平行，任意三条直线不经过同一点”，因此在已有 $n - 1$ 条直线的情况下，再画一条直线，该直线必与现有直线有 $n - 1$ 个交点，且将平面划分出 $n$ 个新区域。因此递推式为 $R_n = R_{n-1} + n, \; n \ge 1$. 初始条件为 $R_0 = 1$.

2) 迭代可得 \[ \begin {align*} R_n & = R_{n-1} + n \\ & = R_{n-2} + (n - 1) + n \\ & = \cdots \\ & = R_0 + 1 + 2 + \cdots + (n - 1) + n \\ & = \frac{1}{2} (n^2 + n) + 1. \end {align*} \]

4.1.13

How many bit sequences of length seven contain an even number of 0s?

包含偶数个 0 且长度为 7 的二进制串有多少个？

解一　先研究包含偶数个 0 且长度为 3 和 4 的二进制串的个数，寻找规律. 长度为 3 的这样的串有 111（0 个 0）、001、010、100（2 个 0）共 4 个，长度为 4 的这样的串有 1111（0 个 0）、0011、0110、1100、0101、1001、1010（2 个 0）、0000（4 个 0）共 8 个。注意到长度为 4 的这样的串有两种：其一，长度为 3 且含偶数个 0 的串接一个 1；其二，长度为 3 且含奇数个 0 的串接一个 0，故长度为 4 的这样的串有 $f(3) + (2^{3} - f(3)) = 2^3 = 8$ 个. 可猜测一般地，长度为 $n$ 的这样的串有 $f(n-1) + (2^{n-1} - f(n-1)) = 2^{n-1}$ 个，并用数学归纳法证明. 因此，包含偶数个 0 且长度为 7 的二进制串有 $f(7) = 2^6 = 64$ 个.

解二　分类讨论：长度为 7，且包含 0、2、4、6 个 0 的二进制串各有多少个？其个数相加即为所求. 容易想到这就相当于 7 个物品里选 0、2、4、6 个有多少种选法，即 $7 \choose 0$、$7 \choose 2$、$7 \choose 4$、$7 \choose 6$. 问题的答案为它们之和 64.

4.1.14

a) Find a recurrence relation for the number of ways to lay out a walkway with slate tiles if the tiles are red, green, or gray, so that no two red tiles are adjacent and tiles of the same color are considered indistinguishable.

b) What are the initial conditions for the recurrences relation in part (a)?

c) How many ways are there to lay out a path of seven tiles as described in part (a)?

1) 用地砖铺一条小径，地砖有红、绿、灰三色，要求红砖彼此不相邻，求铺法数的递推式，假设同色砖都是完全相同的. （题目的意思假设这条小径是由砖块一个个排成一条直线铺成的，即小径视为一维的）

2) (1) 中递推式的初始条件是什么？

3) 按 (1) 所述，铺一条 7 块砖的小径有多少种方法？

解　1) 思路与 4.1.7 完全类似. 递推式为 $f(n) = 2 f(n-1) + 2 f(n-2), \; n > 2.$

4.1.16

a) Use the recurrence relation developed in Example 5 to determine $C_5$, the number of ways to parenthesize the product of six numbers so as to determine the order of multiplication.

b) Check your result with the closed formula for $C_5$ mentioned in the solution of Example 5.

1) 用例 5 中得出的递推式求 $C_5$，即给六个数的乘积加括号以确定乘法顺序的不同方法数.

2) 将你的结果与例 5 的解中提到的 $C_5$ 的闭式解相比较.

解　1) 例 5 中得出的递推式为 \[ \begin {equation*} \left\{ \begin {array} {c} C_0 = 1, \\ C_1 = 1, \\ C_n = \sum\limits_{k=0}^{n-1} C_k C_{n-k-1}, \; n >1. \end {array} \right. \end {equation*} \] 代入 $n = 5$ 得 \[ \begin {align*} C_5 & = \sum\limits_{k=0}^{4} C_k C_{4-k} \\ & = C_0 C_4 + C_1 C_3 + C_2 C_2 + C_3 C_1 + C_4 C_0 \\ & = \cdots \\ & = 14 + 5 + 4 + 5 + 14 \\ & = 42. \end {align*} \] 2) $C_n$ 的闭式解为 \[ C_n = \frac{C(2n,n)}{(n+1)}. \] 代入 $n = 5$ 得 \[ C_5 = \frac{C(10,5)}{6} = 42. \] 这与递推式的解相同.

4.1.24

Let $\{a_n\}$ be a sequence of real numbers. The backward differences of this sequence are define recursively as shown next. The first difference $\nabla a_n$ is \[ \nabla a_n = a_n - a_{n-1}. \] The (k+1)st difference $\nabla^{k+1} a_n$ is obtained from $\nabla^k a_n$ by \[ \nabla^{k+1} a_n = \nabla^k a_n - \nabla^k a_{n-1}. \] Find $\nabla^2 a_n$ for the following sequences.

a) $a_n = 4.$ b) $a_n = 2n.$

c) $a_n = n^2.$ d) $a_n = 2^n.$

设 $\{a_n\}$ 为实数序列. 该序列的后向差分递归定义如下. 一阶差分 $\nabla a_n$ 为 \[ \nabla a_n = a_n - a_{n-1}. \] k+1 阶差分 $\nabla^{k+1} a_n$ 从 $\nabla^k a_n$ 得出 \[ \nabla^{k+1} a_n = \nabla^k a_n - \nabla^k a_{n-1}. \] 对以下序列，求 $\nabla^2 a_n$.

1) $a_n = 4.$ 2) $a_n = 2n.$

3) $a_n = n^2.$ 4) $a_n = 2^n.$

解　按定义有 \[ \begin {align*} \nabla^2 a_n & = \nabla a_n - \nabla a_{n-1} \\ & = (a_n - a_{n-1}) - (a_{n-1} - a_{n-2}) \\ & = a_n - 2 a_{n-1} + a_{n-2}. \end {align*} \] 四小题依次如下

\[ \begin {align*} \nabla^2 a_n & = a_n - 2 a_{n-1} + a_{n-2} = 4 - 2 \times 4 + 4 = 0. \\ \nabla^2 a_n & = a_n - 2 a_{n-1} + a_{n-2} = 2n - 4(n-1) + 2(n-2) = 0. \\ \nabla^2 a_n & = a_n - 2 a_{n-1} + a_{n-2} = n^2 - 2 (n-1)^2 + (n-2)^2 = 2. \\ \nabla^2 a_n & = a_n - 2 a_{n-1} + a_{n-2} = 2^n - 2^n + 2^{n-2} = 2^{n-2}. \end {align*} \]

参考资料

K. H. Rosen, 《离散数学及其应用（英文精编版·第7版）》. 北京：机械工业出版社, 2016.↩