第四章作业答案
第四章作业答案
6.确定{1, 2,…, 8}的下列排列的逆序列。
ⅰ) 35168274
ⅱ) 83476215
解ⅰ) 35168274的逆序列是2, 4, 0, 4, 0, 0, 1, 0。
ⅱ) 83476215的逆序列是6, 5, 1, 1, 3, 2, 1, 0。
7.构造{1, 2,…, 8}的排列，其逆序列是
ⅰ) 2, 5, 5, 0, 2, 1, 1, 0
ⅱ) 6, 6, 1, 4, 2, 1, 0, 0
解ⅰ) □□1□□□□□
□□1□□□2□
□□1□□□23
4□1□□□23
4□1□5□23
4□165□23
4□165723
4 8 1 6
5 7 2 3
逆序列是2, 5, 5, 0, 2, 1, 1, 0的排列是48165723。
ⅱ)□□□□□□ 1 □
□□□□□□ 1 2
□ 3 □□□□12
□ 3 □□□412
□ 3 □5□412
□ 3 65□412
7 3 65□412
7 3 658412
逆序列是6, 6, 1, 4, 2, 1, 0, 0的排列是73658412。
15.对于{x7, x6,…, x1, x0}的下列每一个组合，通过使用基为2的生成
算法确定其直接后继组合：
ⅰ) {x4, x1, x0}
ⅱ) {x7, x5, x3}
ⅲ) {x7, x5, x4, x3, x2, x1, x0}
ⅳ) {x0}
解ⅰ) {x4, x1, x0} 对应0和1的8-元组00010011，使用基为2的生成算法求得j = 2，确定00010011的下一个8-元组是00010100，其对应的组合是{x4, x2}。因此，{x4, x1, x0}的直接后继组合是
{x4, x2}。
ⅱ) {x7, x5, x3}对应0和1的8-元组10101000，使用基为2的生成算法求得j= 0，确定10101000的下一个8-元组是10101001，其对应的组合是{x7, x5, x3, x0}。因此，{x7, x5, x3}的直接后继组合是
{x7, x5, x3, x0}。
ⅲ) {x7, x5, x4, x3, x2, x1, x0}对应0和1的8-元组10111111，使用基为2的生成算法求得j= 6，确定10111111的下一个8-元组是11000000，其对应的组合是{x7, x6}。因此，{x7, x5, x4, x3, x2, x1, x0}
的直接后继组合是{x7, x6}。
ⅳ) {x0}对应0和1的8-元组00000001，使用基为2的生成算法求得j = 1，确定00000001的下一个8-元组是00000010，其对应的组合是{x1}。因此，{x0}的直接后继组合是{x1}。
17.当使用基为2的生成算法时，{x7, x6,…, x1, x0}的哪个组合是S的
组合列表中的第150个组合？第200个组合？第250个组合？（如节4.3所示，表中的这些位置是从0开始计数的）。
解150 = 1 ? 27 + 1 ? 24 + 1 ? 22 + 1 ? 21
150的二进制表示是10010110。因此，第150个组合是
{x7, x4, x2, x1}。
200 = 1 ? 27 + 1 ? 26 + 1 ? 23
200的二进制表示是11001000。因此，第200个组合是{x7, x6, x3}。
250 = 1 ? 27 + 1 ? 26 + 1 ? 25 + 1 ? 24 + 1 ? 23 + 1 ? 21 250的二进制表示是11111010。因此，第250个组合是
{x7, x6, x5, x4, x3, x1}。
19.举出一个3阶非循环Gray码的例子。
解000, 001, 011, 010, 110, 100, 101, 111是3阶非循环Gray码。23.确定下列9阶反射Gray码中9-元组的直接后继。
ⅰ) 010100110
ⅱ) 110001100
ⅲ) 111111111
解ⅰ) σ(010100110) = 4是偶数，所以010100110的直接后继是010100111。
ⅱ) σ(110001100) = 4是偶数，所以110001100的直接后继是110001101。
ⅲ)σ(111111111) = 9是奇数，j= 0，所以111111111的直接后继是111111101。
43.令X = {a, b, c, d, e, f }，并将X上的关系R以aRb, bRc, cRd, aRe,
eRf, fRd定义，证明，R是一个偏序集的覆盖关系，并确定这个偏序集的所有的线性扩张。
证明设R是有限非空集X上的关系。R是一个偏序集的覆盖关系的充分必要条件是：
1)R是反自反的。
2)R是反对称的。
3)若x1Rx2 , x2Rx3,…, x k-1Rx k ，则x1R/x k且x k R/x1，其中k≥ 3。
也就是说，R的关系图满足以下条件：
1)每个顶点上都没有自环。
2)不存在这样的半回路，改变其中至多一条边的方向就能使其成
为有向回路。
R的传递闭包是严格偏序<，< 的自反闭包，即R的自反传递闭包是
偏序≤。画R 的关系图如下：
画偏序集的哈斯图的步骤如下： 1. 画出入度为0的顶点a 。
2. 去掉a 及与其关联的边，入度为0的顶点是b 和e ，将b 和e 画在a 的上方。
3. 再去掉b 和e 及与其关联的边，入度为0的顶点是c 和f ，将c 和f 画在b 和e 的上方。
4. 再去掉c 和f 及与其关联的边，入度为0的顶点是d ，将d 画在c 和f 的上方。
R 是哈斯图如下的偏序集的覆盖关系。
d
a b
e
f c d
该偏序集有6个线性扩张，它们的哈斯图如下。
46. 令m 为正整数并定义所有非负整数的集X 上的关系R ：aRb 当且仅当a 和b 除以m 有相同的余数。证明，R 是X 上的一个等价关系。这个等价关系有多少不同的等价类？
证明 任取非负整数a ，a 和a 除以m 有相同的余数，所以aRa ，R 是自反的。
若aRb ，则a 和b 除以m 有相同的余数，b 和a 除以m 有相同的余数，所以bRa ，R 是对称的。
若aRb 且bRc ，则a 和b 除以m 有相同的余数，b 和c 除以m 有相同的余数，所以a 和c 除以m 有相同的余数，aRc ，R 是传递的。R 是X 上的一个等价关系。
这个等价关系有m 个不同的等价类：[0], [1],…, [m 1]，其中 [i ]是被m 除余数为i 的非负整数集。
a d b
a
c e f a
d b
a
e c
f a d e
a
b c f a d e
a
f b c a d b
a
e f c a
d e
a
b f c