目录第一章离散数学笔记课堂测试一课堂测试二二项式系数的组合证明

Size: px

Start display at page:

Download "目录第一章离散数学笔记课堂测试一课堂测试二二项式系数的组合证明"

榔杖东方
7 years ago
Views:

1 离散数学课程习题与解答 (2015 级使用 ) 周晓聪 (isszxc@mail.sysu.edu.cn) 中山大学计算机科学系, 广州年 4 月 18 日

2 目录第一章离散数学笔记课堂测试一课堂测试二二项式系数的组合证明非齐次递推式的求解递推式的构建课堂测试三

3 第一章离散数学笔记 1.1 课堂测试一讨论 1.1 第二章补充习题第 9 题 : 证明或反证 (A B) (C D) (A C) (B D) 是否成立解答 : 不成立, 例如设 A B {a, b}, C, D {a}, 则 (A B) (C D), 但是 (A C) (B D) {a} 点评 1.1 (1) 有不少同学认为等式是成立的 ;(2) 有不少同学没有举反例说明等式不成立, 而是试图证明等式过程中得到左边等于 S T, 右边等于 S W, 然后说由于 W T, 因此左边不等于右边, 这是错误的, 因为由 W T 不能得到 S T S W;(3) 有的同学使用成员表来说明这两个集合不相同, 这是可以的 ( 虽然有点繁琐 ) 讨论 1.2 第二章补充习题第 13 题 : 设 f 和 g 分别是从集合 {1, 2, 3, 4} 到集合 {a, b, c, d} 和从集合 {a, b, c, d} 到集合 {1, 2, 3, 4} 的函数,f(1) d, f(2) c, f(3) a 和 f(4) b, 而 g(a) 2, g(b) 1, g(c) 3 和 g(d) 2 (a) f 是否是单函数?g 是否是单函数? (b) f 是否是满函数?g 是否是满函数? (c) f 或 g 是否有逆? 如果有则给出该函数的逆解答 : (a) f 是单函数, 因为 f(1), f(2), f(3), f(4) 的值都不相同 ;g 不是单函数, 因为 g(a) g(d) 2; (b) f 是满函数, 因为其共域的每个元素 a, b, c, d 都分别有原像 3, 4, 2, 1;g 不是满函数, 因为其共域中的元素 4 没有源像 (c) 由于 g 不是单函数, 也不是满函数, 所以不是双函数, 所以没有逆 ; 而 f 既是单函数又是满函数, 即是双函数, 所以有逆, 它的逆 f 1 是从 {a, b, c, d} 到 {1, 2, 3, 4} 的函数, 且 f 1 (a) 3, f 1 (b) 4, f 1 (c) 2, f 1 (d) 1 点评 1.2 这题很简单, 但仍然有人判断错, 需要好好复习有关单函数满函数双函数逆函数的概念有解 1.2 课堂测试二讨论 1.3 第四章补充习题第 37 题 : 给出同余方程组 x 4( mod 6) 和 x 13( mod 15) 的所 2

4 解答一 : 由 x 4( mod 6) 可知, 存在 u 使得 x 6 u + 4, 代入第二个方程得到 (6 u + 4) 13( mod 15), 从而 6 u 9( mod 15), 也即 2 u 3( mod 5), 不难得到 u 4( mod 5), 即存在 v 使得 u 5 v + 4, 从而 x 6(5 v + 4) v + 28, 即 x 28( mod 30) 解答二 : 由下面补充习题 41 题的证明我们知道, 若 p 和 q 是不相等的两个素数时, 对任意正整数 a, 有 :p a 且 q a, 当且仅当 pq a 因此 x 4( mod 6) 6 (x 4) 2 (x 4) 且 3 (x 4) 2 x 且 3 (x 1) // 假定 x 4 x 0( mod 2) 且 x 1( mod 3) 类似地有 : x 13( mod 15) 15 (x 13) 3 (x 13) 且 5 (x 13) 3 (x 1) 且 5 (x 3) // 假定 x 13 x 1( mod 3) 且 x 3( mod 5) 因此上面同余方程组与下面的同余方程组有完全相同的解 : x 0( mod 2) x 1( mod 3) x 3( mod 5) 这个同余方程组可使用中国剩余定理求解 M 30,m 1 2, m 2 3, m 3 5,a 1 0, a 2 1, a 3 3,m 30,M 1 15, M 2 10, M 3 6, 求解 M 2 y 2 1( mod 3), 即 10y 2 ( mod 3), 得到 y 2 1, 求解 M 3 y 3 1( mod 5), 即 6y 3 1( mod 5), 也得到 y 3 1, 从而 x (a 1 M 1 y 1 + a 2 M 2 y 2 + a 3 M 3 y 3 )( mod 30) ( )( mod 30) 28( mod 30) 点评 1.3 (1) 这一题不能直接使用中国剩余定理求解, 因为 6 和 15 不是互质的, 所以最好使用教材 4.4 节例子 6 的后向代换法 (bac substitution) (2) 有些同学也想到了类似解法二的方法, 但没有很好地说明第二个同余方程组与题中的同余方程组有相同的解 (3) 有不少同学完全不会解, 思路完全是混乱的讨论 1.4 第四章补充习题第 41 题 : 证明若 p 和 q 是两个不相同的素数, 则 (p q 1 + q p 1 ) 1( mod pq) 证明根据费马小定理有 p q p 1 1, 显然有 p p q 1, 因此 p [(p q 1 + q p 1 ) 1], 类似地有 q [(p q 1 + q p 1 ) 1] 而不难得到对任意正整数, 若素数 p a, 则 a 的算术分解中质数 p 的指数大于等于 1, 而若还有与 p 不同的素数 q a, 则在 a 的算术分解中指数 q 的指数也大于等于 1, 从而 pq a, 也即我们有 pq [(p q 1 + q p 1 ) 1], 即 (p q 1 + q p 1 ) 1( mod pq) 点评 1.4 (1) 这题绝大多数人没有做 ( 或没有做对 ), 因此算作附加题, 没有扣分, 而是视解答情况给与了 1 到 5 分的加分 (2) 这题的关键是要用到费马小定理 ;(3) 第二个关键需要说明为什么 p a 且 q a 时 (p q) 有 pq a (4) 根据第四章补充练习题的答题效果可知道, 多数学生课后没有花时间去复习与看教材, 以及选做教材中习题 3

5 讨论 1.5 Vandermonde s Identity: 设 m, n 和 r 是非负整数,r m 且 r n, 则 : ( ) m + n r ( )( ) m n r r 证明令 : A {w w 是长为 m + n 的二进制串, 且含有 r 个 1} A { s, t s 是长为 m 的二进制串, 且含有 r 个 1, t 是长为 n 的二进制串, 且含有个 1}, 0 r n 显然 : ( ) m + n A r ( )( ) m n A r 且对任意的 0 i r, 0 j r, i j,a i A j 因此, r A A 0 A 1 A r A 0 + A A r 定义函数 : φ : A 对任意的 w A, 设 w s t, 且 s m, t n, 则不难证明 φ 是双函数 : r φ(w) s, t A r A r ( m )( ) n r (1) 首先 φ 是单函数, 对任意的 w 1, w 2 A, 设 w 1 s 1 t 1, s 1 m, t 1 n, 而 w 2 s 2 t 2, s 2 m, t 2 n, 则 φ(w 1 ) s 1, t 1, φ(w 2 ) s 2, t 2, 若 φ(w 1 ) φ(w 2 ), 则 s 1 s 2 且 t 1 t 2, 显然这时也有 w 1 w 2 又令 (2) 其次, 对于任意的 0 r, 以及任意的 s, t A, 显然有 w s t A, 且 φ(w) s, t 由 φ 是双函数有定理要证的等式成立讨论 1.6 设 n 和 r 是非负整数, 且 r n, 则 : ( ) n + 1 r + 1 证明对任意 r j n, 定义 : n jr ( ) j r A j {w w j 且 w 中含有 r 个 1} A {w w n + 1 且 w 中含有 r + 1 个 1} 显然, 对任意的 r i, j n, i j 有 A i A j, 从而 n n A j A j jr A jr ( ) n + 1 r + 1 n jr ( ) j r 4

6 定义函数 : 对任意的 r j n, 以及任意的 w A j, 下面证明 φ 是双函数 φ : n A j A jr φ(w) w }{{} n j 个 0 (1) 对任意的 r i n 和 w 1 A i, 以及 r j n 和 w 2 A j, 若 φ(w 1 ) φ(w 2 ), 即 : w }{{} n i 个 0 从而显然必有 i j, 且 w 1 w 2, 因此 φ 是单函数 w }{{} n j 个 0 (2) 对任意的 w A, 设 w 中最后一个 1 出现在第 i 个位置, 由于 w 中含有 r + 1 个 1, 因此 r < i n + 1, 从而 r i 1 n, 且 w w }{{} n i+1 个 0 显然 w i 1, 且 w 中含有 r 个 1, 因此 w A i 1, 从而 w n jr A j 且 φ(w ) w, 因此 φ 是满函数显然 1.3 二项式系数的组合证明讨论 1.7 设 n 和是整数且 1 n, 则 ( ) ( n n n 1 1) 证明定义 : A { p, w p Z +, 1 p 而 w 是二进制串 w n 且含有个 1} B { q, w q Z +, 1 p n 而 w 是二进制串 w n 1 且含有 1 个 1} ( ) n A ( ) n 1 B n 1 定义 φ : A B, 对任意的 p, w A, 设 w a 1 a n, 由于 1 p 且 w 中含有个 1, 因此 w 至少有 p 个 1, 设其第 p 个 1 为 a j, 则令不难证明 φ 是双函数 φ( p, w ) φ(a 1 a n ) j, a 1 a j 1 a j+1 a n B 讨论 1.8 证明 Hoceystic identity: 设 n 和 r 是正整数, r ( ) ( ) n + n + r + 1 r 证明实际上, 这个等式可有前面证明的如下等式得到 : ( ) n + 1 n ( ) j r + 1 r 5 jr

7 因为我们有 : r ( ) n + r ( ) n + n+r ( ) n + n n n+n n+r ( ) ( ) ( ) j n + r + 1 n + r + 1 n n + 1 r jn 显然 )( n ( 讨论 1.9 设 0 r n, 证明 n r ( r)( ) n r ) 证明对任意的二进制串 w {0, 1}, 我们记 w 为 w 的长度, w 1 为 w 中包含的 1 的个数定义 : A { w, u w n, w 1 r, u r, u 1 } B { s, t s n, s 1, t n, t 1 r } A ( )( ) n r r B ( )( ) n n r 定义函数 φ : A B, 对任意的 w, u A, 令 φ( w, u ) s, t, 其中 s 是将 w 中的第 i 个 1 用 u 中的第 i 个字符替换得到的串,1 i r, 而 t 是 w 删除个 1 得到的串, 删除的规则是, 若 u 中第 i 个位置是 1, 则将 w 中的第 i 个 1 删除,1 i 显然 s, t B 例如, 设 n 8, r 6, 4,w , u , 则 s , t 0101 下面证明 φ 是双函数为此我们定义函数 ψ : B A, 对任意的 s, t B, 令 ψ( s, t ) w, u, 其中 w 是将 s 中第 i 个 0 用 t 中的第 i 个字符替换得到的串,1 i n, 而 u 是 s 删除 n r 个 0 得到的串, 删除的规则是, 若 t 中的第 i 个位置是 0, 则将 s 中的第 i 个 0 删除,1 i n 显然 w, u A 例如, 设 n 8, r 6, 4, s , t 0101, 则 w , u 非齐次递推式的求解讨论 1.10 教材 8.2 节例子 12 补充求递推式 a n 6a n 1 9a n 2 + F (n) 的特解, 其中 F (n) 分别是 :(1) F (n) 3 n ;(2) F (n) n3 n ;(3) F (n) n 2 2 n ;(4) F (n) (n 2 + 1)3 n 解答 : 教材已经给出了特解的形式, 这里要进一步求其中待定系数 p 0, p 1, p 2 的值 (1) 这时特解的形式是 p 0 n 2 3 n, 代入递推式, 我们有 : 整理我们有 : p 0 n 2 3 n 6p 0 (n 1) 2 3 n 1 9p 0 (n 2) 2 3 n n 9p 0 n 2 18p 0 (n 2 2n + 1) 9p 0 (n 2 4n + 4) + 9 9p 0 n 2 18p 0 n 2 36p 0 n + 18p 0 (9p 0 n 2 36p 0 n + 36p 0 ) p 0 从而得到 p 0 1 2, 1 也即这时的特解是 2 n2 3 n (2) 这时特解的形式是 n 2 (p 1 n + p 0 )3 n, 代入递推式, 我们有 : n 2 (p 1 n + p 0 )3 n 6(n 1) 2 (p 1 (n 1) + p 0 )3 n 1 9(n 2) 2 (p 1 (n 2) + p 0 )3 n 2 + n3 n 6

8 整理我们有 : 9n 2 (p 1 n + p 0 ) 18(n 1) 2 (p 1 (n 1) + p 0 ) 9(n 2) 2 (p 1 (n 2) + p 0 ) + 9n 9n 3 p 1 + 9n 2 p 0 18(n 1) 3 p (n 1) 2 p 0 (9(n 2) 3 p 1 + 9(n 2) 2 p 0 ) + 9n 9n 3 p 1 + 9n 2 p 0 18(n 3 3n 2 + 3n 1)p (n 2 2n + 1)p 0 (9(n 3 6n n 8)p 1 + 9(n 2 4n + 4)p 0 ) np 1 18p 1 36np p 0 (108np 1 72p 1 36np p 0 ) + 9n 0 n(54p 1 36p 0 108p p 0 + 9) 18p p p 1 36p 0 0 n( 54p 1 + 9) + (54p 1 18p 0 ) 从而得到 (9 54p 1 ) 0, 以及 (54p 1 18p 0 ) 0, 即 p 1 1 6, p 0 1 ( ) n 3 2, + 3n 2 也即这时的特解是 3 n 6 (3) 这时特解的形式是 (p 2 n 2 + p 1 n + p 0 )2 n, 代入递推式, 我们有 : (p 2 n 2 + p 1 n + p 0 )2 n 6(p 2 (n 1) 2 + p 1 (n 1) + p 0 )2 n 1 9(p 2 (n 2) 2 + p 1 (n 2) + p 0 )2 n 2 + n 2 2 n 这次我们不再全部展开既然上述等式要对所有的 n 2 成立, 我们可考虑取 n 2, 我们应该有 : (p p p 0 )2 2 6(p 2 + p 1 + p 0 )2 9(p 0 ) 即 4p 2 4p 1 + p 0 16 再取 n 3, 我们应该有 : (p p p 0 )2 3 6(p p p 0 )2 2 9(p 2 + p 1 + p 0 ) 即即 36p p 1 + 4p 0 48p p p 0 9(p 2 + p 1 + p 0 ) p 2 3p 1 + p 0 36 再取 n 4, (p p p 0 )4 6(p p p 0 )2 9(p p p 0 ) 即即 64p p 1 + 4p 0 108p p p 0 (36p p 1 + 9p 0 ) p 2 2p 1 + p 0 64 我们解下面的方程组 : 4p 2 4p 1 + p p 2 3p 1 + p p 2 2p 1 + p

9 我们得到 p 2 4, p 1 48, p 0 192, 从而特解为 :(4n n + 192)2 n 代入递推式验算, 可知这确实是一个特解 (4) 这时特解的形式是 n 2 (p 2 n 2 + p 1 n + p 0 )3 n, 代入递推式得到 : n 2 (p 2 n 2 +p 1 n+p 0 )3 n 6(n 1) 2 (p 2 (n 1) 2 +p 1 (n 1)+p 0 )3 n 1 9(n 2) 2 (p 2 (n 2) 2 +p 1 (n 2)+p 0 )3 n 2 +(n 2 +1)3 n 即 n 2 (p 2 n 2 +p 1 n+p 0 ) 2(n 1) 2 (p 2 (n 1) 2 +p 1 (n 1)+p 0 ) (n 2) 2 (p 2 (n 2) 2 +p 1 (n 2)+p 0 )+(n 2 +1) 我们同样分别取 n 2, 3, 4, 有 : 2 2 (p p p 0 ) 2(p 2 + p 1 + p 0 ) + ( ) 3 2 (p p p 0 ) (p p p 0 ) (p 2 + p 1 + p 0 ) + ( ) 4 2 (p p p 0 ) (p p p 0 ) 2 2 (p p p 0 ) + ( ) 整理得到 : 14p 2 + 6p 1 + 2p p p 1 + 9p 0 32p p 1 + 8p 0 (p 2 + p 1 + p 0 ) p p p 0 162p p p 0 (16p 2 + 8p 1 + 4p 0 ) + 17 即 : 14p 2 + 6p 1 + 2p p p 1 + 2p p p 1 + 2p 0 17 解得 p , p 1 1 3, p , 即特解为 : n2 12 (n2 + 4n + 11) 3 n 代入递推式验算, 可知这确实是一个特解 1.5 递推式的构建讨论节习题 7 找到关于长度为 n 含有两个连续 0 的二进串个数的递推公式解答 : 我们记 A n 是长度为 n 含有两个连续 0 的二进制串构成的集合,a n A n 我们要找到关于 a n 的递推式, 这需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 1u, 则必有 u A n 1 ; (2) 否则, 若 w 0u, 则又分两种情况 :(a) 若 u 1v, 即 w 01v, 则有 v A n 2 ;(b) 否则若 u 0v, 即 w 00v, 则 v 可以是任意长度为 n 2 的二进制串因此 a n a n 1 + a n n 2, 对任意的 n 2, 而 a 0 0, a 1 0 讨论节习题 8 找到关于长度为 n 含有三个连续 0 的二进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 含有三个连续 0 的二进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : 8

10 (1) 若 w 1u, 则必有 u A n 1 ; (2) 否则, 若 w 0u, 则又分两种情况 :(a) 若 u 1v, 即 w 01v, 则有 v A n 2 ;(b) 否则若 u 0v, 即 w 00v, 则又分两种情况 :(i) v 1s, 即 w 001s, 则 s 必有 s A n 3 ;(ii) 否则 v 0s, 则 w 000s, 则 s 可以是任意长度为 n 3 的二进制串因此 a n a n 1 + a n 2 + a n n 3, 对任意的 n 3, 而 a 0 0, a 1 0, a 2 0 讨论节习题 9 找到关于长度为 n 不含三个连续 0 的二进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 不含三个连续 0 的二进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 1u, 则必有 u A n 1 ; (2) 否则, 若 w 0u, 则又分两种情况 :(a) 若 u 1v, 即 w 01v, 则有 v A n 2 ;(b) 否则若 u 0v, 即 w 00v, 则必有 v 1s, 其中 s A n 3 因此 a n a n 1 + a n 2 + a n 3, 对任意的 n 2, 而 a 0 1, a 1 2, a 2 4 讨论节习题 10 找到关于长度为 n 含 01 的二进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 含 01 的二进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 1u, 则必有 u A n 1 ; (2) 否则, 若 w 0u, 则 u 可以是除了全 0 串之外的任意串, 也即只要 u 中至少含有一个 1 即可, 这是因为当 u 含有至少一个 1 时, 这个 1 跟它前面的 0( 对于 w 而言, 前面肯定有 0) 就构成了 w 中的 01 子串因此这样的 u 可以有 2 n 1 1 个因此 a n a n n 1 1, 对任意的 n 2, 而 a 0 0, a 1 0 讨论节习题 13 找到关于长度为 n 不含连续两个 0 的三进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 不含连续两个 0 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 2u, 则必有 u A n 1 ; (2) 若 w 1u, 则必有 u A n 1 ; (3) 若 w 0u, 则 u 必是 1v 或 2v, 其中 v A n 2, 也即 u 可以有 2a n 2 个因此 a n 2(a n 1 + a n 2 ), 对任意的 n 2, 而 a 0 1, a 1 3 讨论节习题 14 找到关于长度为 n 含连续两个 0 的三进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 含连续两个 0 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 2u, 则必有 u A n 1 ; (2) 若 w 1u, 则必有 u A n 1 ; (3) 若 w 0u, 则分两种情况 : 若 u 1v 或 u 2v, 则必有 v A n 2, 而若 u 0v, 则 w 00v, 从而 v 可以是任意的三进制串, 即 v 的可能数目是 3 n 2 个因此 a n 2(a n 1 + a n 2 ) + 3 n 2, 对任意的 n 2, 而 a 0 0, a 1 0 讨论节习题 15 找到关于长度为 n 不含连续两个 0 或连续两个 1 的三进串个数的递推公式 9

11 解答 : 同样, 记 A n 是长度为 n 不含连续两个 0 或两个 1( 即既不含连续两个 0, 也不含连续两个 1) 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构对于任意的 w A n : (1) 若 w 2u, 则必有 u A n 1 ; (2) 若 w 1u, 则若 (i) u 2v, 则必有 v A n 2 ;(ii) 若 u 0v, 则 v 不能取所有 A n 2 中的串, 因为 v 还可能以 0 开头这提示我们应该进一步区分 A n 的结构, 我们记 : A 0 n 长度为 n 不含连续两个 0 或连续两个 1, 且以 0 开头的三进制串构成的集合 a 0 n A 0 n A 1 n 长度为 n 不含连续两个 0 或连续两个 1, 且以 1 开头的三进制串构成的集合 a 1 n A 1 n A 2 n 长度为 n 不含连续两个 0 或连续两个 1, 且以 2 开头的三进制串构成的集合 a 2 n A 2 n 显然 : A n A 0 n A 1 n A 2 n a n a 0 n + a 1 n + a 2 n 这时 : (1) 对于任意的 w A 2 n, 即 w 2u, 则 u A n 1, 这意味着 a 2 n a n 1 a 0 n 1 + a 1 n 1 + a 2 n 1 (2) 对任意的 w A 1 n, 即 w 1u, 则必有 u A 0 n 1 或 u A 2 n 1, 这意味着 a 1 n a 0 n 1 + a 2 n 1 (3) 类似地, 对任意的 w A 0 n, 即 w 0u, 则必有 u A 1 n 1 或 u A 2 n 1, 这意味着上面三式相加, 我们有 : a 0 n a 1 n 1 + a 2 n 1 a n a 0 n + a 1 n + a 2 n a 1 n 1 + a 2 n 1 + a 0 n 1 + a 2 n 1 + a n 1 a 1 n 1 + a 0 n 1 + a 2 n 1 + a 2 n 1 + a n 1 a n 1 + a n 2 + a n 1 2a n 1 + a n 2 也即, 我们有 :a n 2a n 1 + a n 2, 对任意的 n 2, 且 a 0 1, a 1 3 讨论节习题 16 找到关于长度为 n 含连续两个 0 或连续两个 1 的三进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 含连续两个 0 或两个 1 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构基于上一题的经验, 我们细分 A n 的构成, 记 : A 0 n 长度为 n 含连续两个 0 或连续两个 1, 且以 0 开头的三进制串构成的集合 a 0 n A 0 n A 1 n 长度为 n 含连续两个 0 或连续两个 1, 且以 1 开头的三进制串构成的集合 a 1 n A 1 n A 2 n 长度为 n 含连续两个 0 或连续两个 1, 且以 2 开头的三进制串构成的集合 a 2 n A 2 n 10

12 显然 : A n A 0 n A 1 n A 2 n a n a 0 n + a 1 n + a 2 n 这时 : (1) 对于任意的 w A 2 n, 即 w 2u, 则必有 u A n 1, 这意味着 a 2 n a n 1 a 0 n 1 + a 1 n 1 + a 2 n 1 (2) 对任意的 w A 1 n, 即 w 1u, 则必有以下三种情况之一成立 :(i) u A 0 n 1;(ii) u A 2 n 1;(iii) u 是任意的以 1 开头的长度为 n 1 的三进制串, 这时 u 可能有 3 n 2 个, 这意味着, a 1 n a 0 n 1 + a 2 n n 2 (3) 类似地, 对任意的 w A 0 n, 即 w 0u, 则必有一下三种情况之一成立 :(i) u A 1 n 1;(ii) u A 2 n 1;(iii) u 是任意的以 0 开头的长度为 n 1 的三进制串, 这时 u 可能有 3 n 2 个, 这意味着, a 0 n a 1 n 1 + a 2 n n 2 上面三式相加, 我们有 : a n a 0 n + a 1 n + a 2 n a 1 n 1 + a 2 n n 2 + a 0 n 1 + a 2 n n 2 + a n 1 2a n 1 + a n n 2 也即, 我们有 :a n 2a n 1 + a n n 2, 对任意的 n 2, 且 a 0 0, a 1 0 讨论节习题 17 找到关于长度为 n 不含连续两个相同字符的三进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 不含连续两个相同字符( 即既不含连续两个 0, 也不含连续两个 1, 也不含连续两个 2) 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构基于上面题目的经验, 我们细分 A n 的构成, 记 : A 0 n 长度为 n 不含连续两个相同字符, 且以 0 开头的三进制串构成的集合 a 0 n A 0 n A 1 n 长度为 n 不含连续两个相同字符, 且以 1 开头的三进制串构成的集合 a 1 n A 1 n A 2 n 长度为 n 不含连续两个相同字符, 且以 2 开头的三进制串构成的集合 a 2 n A 2 n 显然 : A n A 0 n A 1 n A 2 n a n a 0 n + a 1 n + a 2 n 这时, 对任意的 n 2: (1) 对于任意的 w A 2 n, 即 w 2u, 则必有 u A 0 n 1 或 u A 1 n 1, 这意味着 a 2 n a 0 n 1 + a 1 n 1 (2) 对任意的 w A 1 n, 即 w 1u, 则必有 u A 0 n 1 或 u A 2 n 1, 这意味着 a 1 n a 0 n 1 + a 2 n 1 11

13 (3) 对任意的 w A 0 n, 即 w 0u, 则必有 u A 1 n 1 或 u A 2 n 1, 这意味着上面三式相加, 我们有 : a 2 n a 1 n 1 + a 2 n 1 a n a 0 n + a 1 n + a 2 n a 1 n 1 + a 2 n 1 + a 0 n 1 + a 2 n 1 + a 0 n 1 + a 1 n 1 2(a 0 n 1 + a 1 n 1 + a 2 n 1) 2a n 1 也即, 我们有 :a n 2a n 1, 对任意的 n 2, 且 a 0 1, a 1 3 讨论节习题 18 找到关于长度为 n 含连续两个相同字符的三进串个数的递推公式解答 : 同样, 记 A n 是长度为 n 含连续两个相同字符 ( 即含连续两个 0, 或者含连续两个 1, 或者含连续两个 2) 的三进制串构成的集合,a n A n 要找到关于 a n 的递推式, 需要考虑 A n 的结构基于上面题目的经验, 我们细分 A n 的构成, 记 : A 0 n 长度为 n 含连续两个相同字符, 且以 0 开头的三进制串构成的集合 a 0 n A 0 n A 1 n 长度为 n 含连续两个相同字符, 且以 1 开头的三进制串构成的集合 a 1 n A 1 n A 2 n 长度为 n 含连续两个相同字符, 且以 2 开头的三进制串构成的集合 a 2 n A 2 n 显然 : A n A 0 n A 1 n A 2 n a n a 0 n + a 1 n + a 2 n 这时, 对任意的 n 2: (1) 对于任意的 w A 2 n, 即 w 2u, 则必有以下三种情况之一成立 :(i) u A 0 n 1;(ii) u A 1 n 1;(iii) u 是以 2 开头的任意的长度为 n 1 的三进制串这意味着 : a 2 n a 0 n 1 + a 1 n n 2 (2) 对任意的 w A 1 n, 即 w 1u, 则必有以下三种情况之一成立 :(i) u A 0 n 1;(ii) u A 2 n 1;(iii) u 是以 1 开头的任意的长度为 n 1 的三进制串这意味着 : a 1 n a 0 n 1 + a 2 n n 2 (3) 对任意的 w A 0 n, 即 w 0u, 则必有以下三种情况之一成立 :(i) u A 1 n 1;(ii) u A 2 n 1;(iii) u 是以 0 开头的任意的长度为 n 1 的三进制串这意味着 : a 2 n a 1 n 1 + a 2 n n 2 上面三式相加, 我们有 : a n a 0 n + a 1 n + a 2 n 2a n n 1 也即, 我们有 :a n 2a n n 1, 对任意的 n 2, 且 a 0 0, a

14 点评 1.5 实际上, 我们使用 Java 语言编写了程序, 验证了上面所有的递推式都是正确的这个程序中有如下几个类 : (1) 类 RecurrenceCaculator 为每个递推式编写了一个公有静态方法, 计算 a n ; (2) 类 StringCounter 生成某种进制串的全部, 并进行遍历, 然后利用实现了接口 StringFilter 的类的对象提供的过滤条件, 统计符合条件的串的个数因此, 这里使用过滤器这种设计模式, 使得类 StringCounter 具有了很好的扩充性和重用性 ; (3) 文件 DefaultStringFilter.java 为每个练习都实现了一个实现接口 StringFilter 的类, 以提供合适的过滤条件 ; (4) 最后类 ChecRecurrenceRelation 编写了一系列公有静态方法, 分别使用类 RecurrenceCaculator 利用递推式计算 a n, 以及使用类 StringCounter 利用遍历 + 过滤计算 a n, 两者进行比较以验证递推式的正确性 1.6 课堂测试三 n 作业节习题 38 给出等式 2( n ) n(n + 1)2 n 2 的证明组合证明 : 考虑从 n 位教师中选取一些教师组成代表团, 然后再从这些教师中两次选取主席 ( 两次选取可以选取同一位教师作为主席 ) 的选取方法这种选取方法有两种方式进行计数 : (1) 第一步从 n 位教师中选取位教师组成代表团, 然后再从这位教师中两次选取主席第一步 ( 有 n ) 种选取方法, 两次从为教师中选取主席, 由于允许重复, 因此每次都有种选取方法, 因此若选教师组成代表团, 并两次选取主席的方法数根据乘法原则有 2( n ) 代表团的人数可从 0 位到 n 位, n 因此总共的方法是 2( n ), 即上述等式的左边公式 ; (2) 另一种方法则是先确定两次的主席人选, 然后再从剩下的教师中选取若干位组成代表团这时分两种情况 :(i) 若两次确定的主席人选不同, 则第一次确定主席人选方法数有 n 种, 第二次有 n 1 种, 而剩下的 n 2 位教师都有可能成为或不成为代表, 因此总共的方法数为 n(n 1)2 n 2 ;(ii) 若两次确定的主席人选相同, 则确定主席人选的方法数有 n 种, 而剩下的 n 1 位教师都有可能成为或不成为代表, 因此总共的方法数为 n2 n 1 这种情况总共有 n(n 1)2 n 2 + n2 n 1 n(n + 1)2 n 2 代数证明 : 我们已经证明, 当 n 和都是整数, 且 1 n 时有 ( ) ( n n n 1 1), 从而 : n ( ) n n ( ) n 1 2 n 1 1 n 1 ( ) n 1 n ( + 1) n 1 ( ) n 1 n 1 ( ) n 1 n + n 1 n 1 ( ) n 2 n(n 1) + n2 n n 2 ( ) n 2 n(n 1) + n2 n 1 n(n 1)2 n 2 + n2 n 1 n(n + 1)2 n 2 13

15 点评 1.6 这一题比较简单, 大多数都能够证明, 区别在于用组合证明时能否表达得比较清楚, 而代数证明能否说明所基于的基本等式 ( ) ( n n n 1 1), 以及求和指标进行变换时是否写清楚和正确字符串? 作业节习题 32 8 个字母 AARDV ARK 能构成多少不同的有连续 3 个 A 的 ( 长度为 8 的 ) 解答 : 因为 3 个 A 必须连续, 我们不妨将其看作一个字母 a, 因此此问题可看作一个 a, 两个 R 和 D, V, K 共六个字母的允许重复的排列, 因此总共不同的字符串数为 6!/2! 360 点评 1.7 这一题更简单, 但有些人没有理解是 8 个字符的排列, 而错误认为可以是 0 个字符,1 个字符等等, 更多人没有指出是重复排列问题作业 1.3 有多少以 000 开头或以 1111 结尾的长度为 10 的二进制串? 解答 : 设 A 是以 000 开头的长度为 10 的二进制串构成的集合, 而 B 是以 1111 结尾的长度为 10 的二进制串构成的集合, 则显然有 A 2 7, 而 B 2 6, 而 A B 是以 000 开头且以 1111 结束的二进制串, 从而 A B 2 3, 而题目中所求的二进制串数为 A B A + B A B 点评 1.8 这一题也很简单, 但不少同学没有引入集合, 并且明确使用容斥原理作业 1.4 习题 8.5 第 6 题 : 若是有 100 个元素在 A 1 中,1000 个元素在 A 2 中,10000 个元素在 A 3 中, 求分别满足下列条件时集合 A 1 A 2 A 3 中的元素个数 a) A 1 A 2 且 A 2 A 3 ; b) 集合两两不相交 ; c) 每一对集合中有两个相同的元素, 有一个元素在三个集合中作业 1.5 习题 8.5 第 12 题 : 求不超过 1000 且是平方数或立方数的正整数的个数作业 1.6 习题 8.6 第 4 题 : 求以下不定方程解的个数, 其中 x i (i 1, 2, 3, 4) 是非负整数, 且 x 1 3, x 2 4, x 3 5, x 4 8 x 1 + x 2 + x 3 + x 4 17 作业 1.7 习题 8.6 第 8 题 : 从 7 元素集合到 5 元素集合有多少个映上函数? 14

求出所有的正整数 n 使得 20n + 2 能整除 2003n n 20n n n 20n n 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y =

求出所有的正整数 n 使得 20n + 2 能整除 2003n + 2002 n 20n + 2 2003n + 2002 n 20n + 2 2003n + 2002 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y = y x y 对于任意正整数 n, 记 n 的所有正约数组成的集合为 S n 证明 : S n 中至多有一半元素的个位数为

目录 第一章 离散数学笔记 课堂测试一 课堂测试二 二项式系数的组合证明

目录第一章离散数学笔记课堂测试一课堂测试二二项式系数的组合证明