已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
Math 475Text: Brualdi, Introductory Combinatorics 5th Ed. Prof: Paul Terwilliger Selected solutions for Chapter 4 1. The permutation 31524 is followed by 35124 and preceded by 31254. To see this, recall the display on page 90. In that display the permutations of (1,2,3,4) are listed in 24 rows. According to the algorithm in Section 4.1, for each row 1,2,.,24 we insert a 5 in the fi ve possible locations of the given permutation, working from right to left for odd numbered rows and left to right for even numbered rows. The permutation 3124 appears on row 9 which is odd, so for this row the 5s are inserted from right to left. 2. The mobile integers are 8, 3, 7. For these integers the arrow points to an adjacent smaller integer. 3. Working from left to right across each row, 1 2 3 4 5 1 2 3 5 4 1 2 5 3 4 1 5 2 3 4 5 1 2 3 4 5 1 2 4 3 1 5 2 4 3 1 2 5 4 3 1 2 4 5 3 1 2 4 3 5 1 4 2 3 5 1 4 2 5 3 1 4 5 2 3 1 5 4 2 3 5 1 4 2 3 5 4 1 2 3 4 5 1 2 3 4 1 5 2 3 4 1 2 5 3 4 1 2 3 5 4 1 3 2 5 4 1 3 5 2 4 1 5 3 2 4 5 1 3 2 5 4 1 3 2 5 1 4 3 2 1 5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 4 3 2 5 1 3 4 2 5 1 3 4 5 2 1 3 5 4 2 1 5 3 4 2 5 1 3 4 2 5 1 3 2 4 1 5 3 2 4 1 3 5 2 4 1 3 2 5 4 1 3 2 4 5 3 1 2 4 5 3 1 2 5 4 3 1 5 2 4 3 5 1 2 4 5 3 1 2 4 5 3 1 4 2 3 5 1 4 2 3 1 5 4 2 3 1 4 5 2 3 1 4 2 5 4. For 1 k n the direction of k changes immediately after we move a mobile integer m (1 m b) or increases this total by one (if a ifor 1 k n; (iii) ik= n k + 1 for 1 k n. Thus n321 is the unique permutation with ?n 2 ? inversions. The permutations of 1,2,.,n that have exactly ?n 2 ? 1 inversions are obtained from n321 by switching a single pair of adjacent terms. There are n 1 such permutations. 3 10. We have 256143 251643 215643 125643 125634 125364 123564 123546 123456 and 436251 436215 436125 431625 413625 143625 143265 142365 124365 123465 123456 11. (a) The set x5,x4,x3 corresponds to coordinate76543210 entry00111000 (b) The set x7,x5,x3,x1 corresponds to coordinate76543210 entry10101010 (c) The set x6 corresponds to coordinate76543210 entry01000000 12. (a) x4,x3,x1,x0; (b) x6,x4,x2,x0; (c) x3,x2,x1,x0. 4 13. The subsets of x4,x3,x2,x1,x0 are listed in the table below. Each row describes a subset. For 0 i 4 we write 1 (resp. 0) below xiwhenever the subset contains (resp. does not contain) xi. rankx4x3x2x1x0 000000 100001 200010 300011 400100 500101 600110 700111 801000 901001 1001010 1101011 1201100 1301101 1401110 1501111 1610000 1710001 1810010 1910011 2010100 2110101 2210110 2310111 2411000 2511001 2611010 2711011 2811100 2911101 3011110 3111111 5 14. The subsets of x5,x4,x3,x2,x1,x0 are listed in the table below. Each row describes a subset. For 0 i 5 we write 1 (resp. 0) below xiwhenever the subset contains (resp. does not contain) xi. rankx5x4x3x2x1x0 0000000 1000001 2000010 3000011 4000100 5000101 6000110 7000111 8001000 9001001 10001010 11001011 12001100 13001101 14001110 15001111 16010000 17010001 18010010 19010011 20010100 21010101 22010110 23010111 24011000 25011001 26011010 27011011 28011100 29011101 30011110 31011111 rankx5x4x3x2x1x0 32100000 33100001 34100010 35100011 36100100 37100101 38100110 39100111 40101000 41101001 42101010 43101011 44101100 45101101 46101110 47101111 48110000 49110001 50110010 51110011 52110100 53110101 54110110 55110111 56111000 57111001 58111010 59111011 60111100 61111101 62111110 63111111 6 15. We convert to binary, add 1, and then convert back: subsetx4,x1,x0x7,x5,x3x7,x5,x4,x3,x2,x1,x0x0 binary rep00010011101010001011111100000001 binary rep + 100010100101010011100000000000010 next subsetx4,x2x7,x5,x3,x0x7,x6x1 16. We convert to binary, subtract 1, and then convert back: subsetx4,x1,x0x7,x5,x3x7,x5,x4,x3,x2,x1,x0x0 binary rep00010011101010001011111100000001 binary rep - 100010010101001111011111000000000 prec. subsetx4,x1x7,x5,x2,x1,x0x7,x5,x4,x3,x2,x1 17. 150 = 128 + 16 + 4 + 2 has the binary representation 10010110 so the 150th subset is x7,x4,x2,x1. 200 = 128 + 64 + 8 has binary representation 11001000 so the 200th subset is x7,x6,x3. 250 = 128 + 64 + 32 + 16 + 8 + 2 has binary representation 11111010 so the 250th subset is x7,x6,x5,x4,x3,x1. 18. Consider the refl ected Gray code of order 4. For 0 m 15 the mth term is g3g2g1g0 where mg3g2g1g0 00000 10001 20011 30010 40110 50111 60101 70100 81100 91101 101111 111110 121010 131011 141001 151000 See the course notes for a 4-cube representation. 7 19. The following is a noncyclic Gray code of order 3: rankcodeword 0000 1001 2011 3010 4110 5100 6101 7111 20. The following is a cyclic Gray code of order 3 that is not the refl ected Gray code: rankcodeword 0000 1001 2011 3111 4101 5100 6110 7010 8 21. Consider the refl ected Gray code of order 5. For 0 m 31 the mth term is g4g3g2g1g0 where mg4g3g2g1g0 000000 100001 200011 300010 400110 500111 600101 700100 801100 901101 1001111 1101110 1201010 1301011 1401001 1501000 1611000 1711001 1811011 1911010 2011110 2111111 2211101 2311100 2410100 2510101 2610111 2710110 2810010 2910011 3010001 3110000 9 22. Consider the refl ected Gray code of order 6. For 0 m 63 the mth term is g5g4g3g2g1g0 where mg5g4g3g2g1g0 0000000 1000001 2000011 3000010 4000110 5000111 6000101 7000100 8001100 9001101 10001111 11001110 12001010 13001011 14001001 15001000 16011000 17011001 18011011 19011010 20011110 21011111 22011101 23011100 24010100 25010101 26010111 27010110 28010010 29010011 30010001 31010000 mg5g4g3g2g1g0 32110000 33110001 34110011 35110010 36110110 37110111 38110101 39110100 40111100 41111101 42111111 43111110 44111010 45111011 46111001 47111000 48101000 49101001 50101011 51101010 52101110 53101111 54101101 55101100 56100100 57100101 58100111 59100110 60100010 61100011 62100001 63100000 10 23.(a) The sum of the entries is 4, which is even, so we change coordinate zero.The successor is 010100111. (b) The sum of the entries is 4, which is even, so we change coordinate zero. The successor is 110001101. (c) the sum of the entries is 9, which is odd. Coordinate zero is 1 so we change coordinate one. The successor is 111111101. 24. (a) The sum of the entries is 4, which is even. The sequence ends with 10 so we change coordinate two. The predecessor is 010100010. (b) The sum of the entries is 4, which is even. The sequence ends with 100 so we change coordinate three. The predecessor is 110000100 (c) The sum of the entries is 9, which is odd. So we change coordinate zero. The predecessor is 111111110. 25. 26. The lexicographic ordering is 12, 13, 14, 15, 23, 24, 25, 34, 35, 45. 27. The lexicographic ordering is 123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456. 28. In the lexicographic order the 6-subset that follows 2,3,4,6,9,10 is 2,3,4,7,8,9 and the 6-subset that precedes 2,3,4,6,9,10 is 2,3,4,6,8,10. 29. In the lexicographic order the 7-subset that follows 1,2,4,6,8,14,15 is 1,2,4,6,9,10,11 and the 7-subset that precedes 1,2,4,6,8,14,15 is 1,2,4,6,8,13,15. 30. In the table below we list the permutations of 1,2,3 according to the lexicographic order of their inversion sequence. permutation123132213312231321 inversion sequence000010100110200210 Below we similarly list the permutations of 1,2,3,4. 123412431324142313421432 000000100100011002000210 213421433124412331424132 100010101100111012001210 231424133214421334124312 200020102100211022002210 234124313241423134214321 300030103100311032003210 11 31. We fi rst generate the 3-subsets of 1,2,3,4,5 in lexicographic order: 123, 124, 125, 134, 135, 145. For each subset we order the elements in all possible ways, using the algorithm from Section 4.1. This yields the following ordering of the 3-permutations of 1,2,3,4,5. Reading left to right, 123132312321231213 124142412421241214 125152512521251215 134143413431341314 135153513531351315 145154514541451415 32. We fi rst generate the 4-subsets of 1,2,3,4,5,6 in lexicographic order. Reading left to right, 12341235123612451246 12561345134613561456 23452346235624563456 For each subset we order the elements in all possible ways, using the algorithm from Section 4.1. This yields an ordering of the 4-permutations of 1,2,3,4,5,6. We omit the details due to length. 33. By convention the fi rst term in the lexicographical order is position 1. The total number of 4-subsets of 1,2,3,4,5,6,7,8,9 is ?9 4 ?. We now count the number of 4-subsets that come after 2489 in the lexicographical order. A 4-subset comes after 2489 if and only if it has the form (i) abcd (3 a b c d 9) or (ii) 2bcd (5 b c d 9). The number of 4-subsets of type (i) is ?7 4 ?. The number of 4-subsets of type (ii) is?5 3 ?. Therefore 2489 is in position ?9 4 ? ?7 4 ? ?5 3 ? . 34. Consider the lexicographical order of r-subsets for 1,2,.,n. (a) The fi rst n r + 1 terms are 1,2,.,r 1,r, 1,2,.,r 1,r + 1, 1,2,.,r 1,n. (b) The last r + 1 terms are n r,n r + 1,.,n 1, n r,n r + 1,.,n 2,n, n r + 1,n r + 2,.,n 1,n. 12 35. Let A and B denote distinct r-subsets of 1,2,.,n. We show that with respect to lexicographic order, A B if and only B A. Recall that A B whenever A contains the minimum element in (AB)(AB). Equivalently A B whenever the minimum element of A B is smaller than the minimum element of B A. From this version we see that A B if and only B A. The result follows. 36.View X = 1,2,.,n.(i) There are 2(n 2) diff erent relations on X.Reason: To construct a relation R on X, for 1 x,y n we must decide whether or not xRy. There are n2choices for (x,y). The result follows by the multiplication principle. (ii) There are 2n(n1) refl exive relations on X. Reason: To construct a refl exive relation R on X, for distinct 1 x,y n we must decide whether or not xRy. There are n(n 1) choices for (x,y). The result follows by the multiplication principle. (iii) Abbreviate N = ?n+1 2 ?. There are 2N symmetric (resp. antisymmetric) relations on X. Reason: To construct a symmetric (resp. antisymmetric) relation R on X, for 1 x y n we must decide whether or not xRy. There are N choices for (x,y). The result follows by the multiplication principle. (iv) Abbreviate M = ?n 2 ?. There are 2M refl exive symmetric (resp. antisymmetric) relations on X. Reason: To construct a refl exive symmetric (resp. antisymmetric) relation R on X, for 1 x y n we must decide whether or not xRy. There are M choices for (x,y). The result follows by the multiplication principle. 37. Recall that a relation on X is a partial order if and only if it is refl exive, antisymmetric, and transitive. We now show that the relation R has these features. R is refl exive: For x X we show xRx. The relations R0and R00 are refl exive so xR0 x and xR00 x. Therefore xRx. R is antisymmetric: For distinct x,y X such that xRy, we show that yRx fails. We assume xRy so xR0y. The relation R0is antisymmetric so yR0 x fails. Therefore yRx fails. R is transitive: For x,y,z X such that xRy and yRz we show xRz. By construction xR0y and yR0z. The relation R0is transitive so xR0z. Similarly xR00z. Therefore xRz. 38. Recall that a relation on a set is a partial order if and only if it is refl exive, antisymmetric, and transitive. We show that the relation T on the set X1 X2has these features. T is refl exive: For x X1X2we show xTx. Write x = (x1,x2). The relation 1 is refl exive so x11x1. Similarly x22x2. Therefore xTx. T is antisymmetric: For distinct x,y X1 X2such that xTy, we show that yTx fails. Write x = (x1,x2) and y = (y1,y2). Since x,y are distinct, there exists i 1,2 such that xi6= yi. Since xTy we have xiiyi. The relation iis antisymmetric so yi6ixi. Therefore yTx fails. T is transitive: For x,y,z X1X2such that xTy and yTz, we show xTz. Write x = (x1,x2) and y = (y1,y2) and z = (z1,z2). Pick i 1,2. Since xTy we have xiiyi, and since yTz we have yiizi. By this and since i is transitive we fi nd xiizi. Therefore xTz. 39. Defi ne the set Jn= J J J (n factors). Thus Jnconsists of the n-tuples of zeros and ones. For x Jnand 1 i n let xidenote the entry in coordinate i of x, so that x = (x1,x2,.,xn ). Defi ne a partial order on Jnsuch that for x,y Jn, x y whenever xi yifor 1 i n. By construction the poset (Jn,) is the direct product of n 13 copies of the poset (J,). We show that the poset (Jn ,) can be identifi ed with the poset (P(X),). View X = 1,2,.,n. Defi ne a function f : Jn P(X) by f(x) = i X|xi= 1,x Jn. The function f is a bijection. We show that for x,y Jn, x y if and only if f(x) f(y). Let x,y be given and note that the following assertions are equivalent: (i) x y; (ii) xi yifor 1 i n; (iii) xi= 1 implies yi= 1 for 1 i n; (iv) i f(x) implies i f(y) for 1 i n; (v) f(x) f(y). We have shown that the poset (Jn ,) can be identifi ed with the poset (P(X),). 40. For each integer r 0 defi ne a poset r as follows.The poset consists of the set 0,1,.,r together with the total order 0 1 r. We will be discussing the direct product n1n2nm. Consider the multiset X = n1a1,n2a2,.,nmam. Let P(X) denote the set of all multisubsets of X. An element x P(X) has the form x = x1 a1,x2 a2,.,xm am,0 xj nj(1 j m). For x,y P(X) the following are equivalent: (i) x y; (ii) xj yjfor 1 j m; (iii) (x1,x2,.,xm) (y1,y2,.,ym) in the poset n1 n2 nm. Therefore the poset n1 n2 nm can be identifi ed with the poset (P(X),). 41. We show that a partial order on a fi nite set X is uniquely determined by its cover relation. This is a consequence of the following lemma. Lemma The following are equivalent for all distinct x,y X: (i) x y; (ii) there exists an integer r 2 and a sequence (x1,x2,.,xr) of elements in X such that x = x1and xr= y and xicovers xi1for 2 i r. 14 Proof: (i) (ii) Consider the set S consisting of the fi nite sequences (x1,x2,.,xr) such that x1= x and xr= y and xi1 xi for 2 i r. The set S is fi nite since X is fi nite. The set S is nonempty since (x,y) S. Pick an element (x1,x2,.,xr) in S with r maximal. By construction r 2. By the maximality of r we see that xicovers xi1for 2 i r. (ii) (i) The relation is transitive. 42. The diagram of the cover relation is essentially the n-cube, where n = |X|. 43. The linear extensions are abecfd,abefcd,aebcfd,aebfcd,abcefd,aefbcd. 44. Recall that a relation is an equivalence relation whenever it is refl exive and symmetric and transitive. We show that R has these features. R is refl exive: For x X, x and x are in the same part of the partition. R is symmetric: For x,y X, x and y are in the same part of the partition if and only if y and x are in the same part of the partition. R is transitive: For x,y,z X, if x,y are in the same part of the partition, and y,z are in the same part of the partition, then x,z are in the same part of the partition. 45. The relation R is an equivalence relation. To verify this, one checks that R is refl exive, symmetric, and transitive. For the equivalence relation R one equivalence class consists of 0. Every other equivalence class consists of a positive integer and its opposite. 46. We show that R is an equivalence relation. R i
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 六年级语文上学期整本书阅读《童年》期末复习教学设计
- 初中语文七年级下册紫藤萝瀑布教学设计与实施
- 高二英语选择性必修二 Unit 5 Reading and Thinking 语篇深度解读与默写训练教学设计
- 初中语文九年级中考作文选材教学设计
- 小学五年级美术《生活中的标志》教学设计
- 高一英语必修第一册Unit 3 Sports and fitness 单元整体教学设计
- 高一体育五步拳教学设计
- 小学四年级劳动教育煎牛排教学设计
- 小学四年级劳动《花瓶罩饰》项目化教学设计
- 八年级语文下册第三单元养性怡情知识清单教学设计
- 抖音直播运营中心薪酬绩效考核实施管理方案
- 2026年学生入团考试题库及参考答案
- 2027届河南省部分城市联考高三上学期11月阶段检测历史试题(含答案)
- 2026年宁夏水务投资集团有限公司招聘笔试参考题库附带答案详解析版
- 2026秋北师大版选择性必修第一册Unit 1-3 句子语法填空练习(备考期中)
- 智能体电脑行业王伟东白皮书
- 秦皇岛市建设现代有轨电车项目调研报告
- 2026秋新教材苏教版五年级上册数学第七单元 用字母表示数量关系(一) 教案(共7课时)
- 《中药炮制技术》教案-13模块十三 其他炮制技术
- 2026年辅警笔试的题库及答案
- 多模式镇痛在加速康复外科中的应用现状
评论
0/150
提交评论