习题四
4.1.若群G的元素a均可表示为某一元素x的幂，即a= x m，则称这个群为循环群。若群的
元素交换律成立，即a , b∈G满足
a⋅b = b⋅a
则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。
[证].设循环群(G, ⋅)的生成元是x0∈G。于是，对任何元素a , b∈G，∃m，n∈N，使得a= x0m , b= x0n ,从而
a⋅b = x0m⋅x0n
= x0m +n (指数律)
= x0n +m (数的加法交换律)
= x0n⋅x0m(指数律)
= b⋅a
故⋅运算满足交换律；即(G, ⋅)是交换群。
4.2.若x是群G的一个元素，存在一个最小的正整数m，使x m=e，则称m为x的阶，试证：
C={e,x,x2, ⋯,x m-1}
是G的一个子群。
[证].(1)非空性C ≠∅：因为∃e∈G；
(2)包含性C⊆G：因为x∈G，根据群G的封闭性，可知x2, ⋯,x m-1,(x m=)e∈G，故C⊆G；
(3)封闭性∀a , b∈C⇒ a ⋅b∈C：∀ a , b∈C，∃k，l∈N (0≤k a ⋅ b = x k⋅ x l = x(k+l) mod m∈C(因为0 ≤ (k+l) mod m < m) ； (4)有逆元∀a ∈C⇒ a -1∈C：∀ a ∈C，∃k∈N (0≤k a -1= x m-k∈C(因为0 ≤m-k < m) 。 综合(1) (2) (3) (4)，可知(C, ⋅)是(G, ⋅)的一个子群。 4.3.若G是阶为n的有限群，则G的所有元素的阶都不超过n。 [证].对任一元素x∈G，设其阶为m，并令C={e,x,x2, ⋯,x m-1}，则由习题4.2.可知(C, ⋅)是(G, ⋅)的一个子群，故具有包含性C⊆G。因此有 m = |C| ≤ | G | = n 所以群G的所有元素的阶都不超过n。 4.4.若G是阶为n的循环群，求群G的母元素的数目，即G的元素可以表示成a的幂： a,a2, ⋯,a n 的元素a的数目。 [证].设(G, ⋅)是循环群，a是其一个母元素(生成元)，a的阶为n(也是G的阶)，则 G ={a,a2, ⋯,a n(=e) }。 (1).我们来证：对任何自然数r∈N (0< r 为此，只需证a r的阶为n即可。 首先，设a r的阶为k，因此有a r⋅k = (a r)k= e，由于a的阶为n，故根据引理*可得n | r⋅k 。已知0< r 其次， (a r)n= a r⋅n(指数律) = a n⋅r (数的加法交换律) =(a n)r (指数律) = e r = e 。 因而，由k是元素a r的阶，具有最小性，所以k ≤n。 综合这两方面，可得k = n。 (2).根据(1)的结论，可得，群G的母元素的数目为ϕ(n) (欧拉函数，小于n且与n互素的数的个数)。 注.引理*.设(G,⋅)是群。∀x∈G，若x的阶为k，从而x k =e。则∀m∈N, x m＝e⇔k | m。 [证].先证⇒)： 若x m＝e，则必有k | m。 否则k∤m，于是，由带余除法，可设m=kq+r(0< r x r＝x m-kq ＝x m+(-kq) ＝x m⋅ (x k)-q(指数律) ＝e ⋅e-q(x m＝e, x k =e) ＝e ⋅e ＝e 故与x的阶为k，具有最小性，矛盾。 次证⇐): 若k | m，则m = kq。于是 x m ＝x kq ＝(x k)q(指数律) ＝e q(x k =e ) =e。 4.5.试证循环群G的子群仍是循环群。 [证].设(H, ⋅)是循环群(G, ⋅)=的一个子群，则H中的元素都可表示成a的一些正方幂。设a m是H中指数最小的正方幂，我们来证(H, ⋅)=。为此只要证明H中任一元素都可表示成a m的正方幂即可。 任取H中一个元素a k，根据带余除法，可知有非负整数q及r，使 k=qm+r且0≤r 于是由(H, ⋅)构成群，可知(a m)q∈H，从而(a m)-q∈H，于是 a r=a k⋅ (a m)-q∈H 由m的选择(最小性)必须有r=0，所以a k=(a m)q，这说明(H, ⋅)=，因而(H, ⋅)循环群。4.6.若H是G的子群，x和y是G的元素，试证xH⋂yH或为空，或xH = yH。 [证].对任何x,y∈G，若xH⋂yH=∅，则问题已证。 否则若xH⋂yH≠∅，则必至少有一元素x0∈xH⋂yH，从而 x0∈ xH⋂yH ⇒x0∈ xH∧ x0∈yH ⇒ x0=x⋅h1∧ x0 =y⋅h2(这里h1, h2∈H) ⇒x⋅h1 = y⋅h2 ⇒x = y⋅h2⋅h1-1∧y = x⋅h1⋅h2–1(*) 下面我们来证：xH = yH。为此，要分证： (1)xH⊆yH； (2)yH⊆xH； 我们只证(1) ；(2)同理可证； 对任何元素a， a∈ xH ⇒a =x⋅h'(这里h'∈H) ⇒a = y⋅h2⋅h1-1⋅h'(由(*)：x = y⋅h2⋅h1-1 ) ⇒a =y⋅h''(由H的封闭性：h''= h2⋅h1-1⋅h'∈H) ⇒a∈ yH 所以 xH ⊆ yH ； 所以，由包含关系的反对称性，我们得到 xH = yH 。 4.7. 若H 是G 的子群，|H |=k ，试证： |xH |=k 其中x ∈G 。 [证].建立自然映射 f : H →xH ，使得 对任何h ∈H ， f (h )=x ⋅h 。于是 (1)后者唯一：由⋅运算的结果唯一性可得； (2)满射：对任何 b ∈xH ，有a = h ∈H ，使得b = x ⋅h 。于是，有 f (a )= f (h )= x ⋅h = b ； (3)单射： f (h 1)= f (h 2) ⇒ x ⋅h 1 = x ⋅h 2 ⇒ h 1 = h 2 (群的消去律 )。 所以，f 是从H 到的双射，因此 |xH |=|H |=k 。 4.8.有限群G 的阶为n ，H 是G 的子群，则H 的阶必除尽G 的阶。 [证].这即是著名的拉格郎日(Lagrange 法国著名数学家、力学家1736-1814)定理。 设G 的子群},,,,{121-=r h h h e H 。 于是令},,,,{121-⋅⋅⋅=⋅=r h a h a h a a e a aH ，这里G a ∈，并且我们定义R 是G 上的二元关系，即G G R ⨯⊆ ∀G y x ∈,，))((::aH y aH x G b xRy ∈∧∈∈∃=。 从而R 是G 上的等价关系，其等价块的形式为aH ，设其代表元为k a a a ,,,21 ，则 H a H a H a k ,,,21 是所有的等价块，构成对G 的一个划分(参见习题4.6.)。即 H a H a H a G k +++ = 21 根据习题4.7.可得r H H a H a H a k ===== 21。 因此n kr H k G ===，所以r 必能整除n ，即H 的阶必除尽G 的阶。 4.10. 若x 和y 在群G 作用下属于同一等价类，则x 所属的等价类E x ，y 所属的等价类E y 有 |E x | = |E y | 。 [证].设底基X ={1,2,⋯,n}。对任一个元素a ∈X ，E a ={b ∈X | ∃p ∈G , (a )p =b }。 因为已知x 和y 在群G 作用下属于同一等价类，因此，存在z ∈X ，使得x , y ∈E z ，于是∃p 1, p 2∈G , 使得 (z )p 1=x , (z )p 2=y 。 我们来证：E x = E y 。为此，要分证： (1) E x ⊆ E y ； (2) E y ⊆ E x ； 我们只证(1) ；(2)同理可证 ； 对任何元素a ∈X ， a ∈ E x ⇒ a = (x )p ' (这里p '∈G ) ⇒ a = (z )p 1p ' (由 (z )p 1=x ) ⇒ a = (y )p 2-1p 1p ' (由(z )p 2=y , 得 (y )p 2-1=z (群G 有逆元)) ⇒ a = (y ) p '' (由群G 的封闭性 ： p ''= p 2-1p 1p '∈G ) ⇒ a ∈ E y 所以 E x ⊆ E y 。 所以，由包含关系的反对称性，我们得到 E x = E y 。 所以得证 |E x | = |E y | 。 4.11. 有一个3⨯3的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色， 其余染蓝色，问有多少种着色方案？ [解]. 一个3⨯3的正方形棋盘，只能旋转，不能翻转，其详细的置换群为: 不动0︒： P 1=(1)(2)(3)(4)(5)(6)(7)(8)(9) 逆时针旋转90︒: P 2=(5)(1793)(2486) 顺时针旋转90︒: P 3=(5)(1397)(26 84) 旋转180︒: P 4=(5)(19)(28)(37)(46) 将2个格着以r 色，7个格着以b 色，相当于用b ，r 二种颜色对3⨯3的正方形棋盘进行染色。 于是根据母函数形式的Pólya 定理，方案枚举： P(b ,r )= 4 1 [(b +r )9+2(b +r )(b 4+r 4)2+(b +r )(b 2+r 2)4] 其中b 7r 2的系数即为所求染色方案数： ]140229[41⎪⎪⎭⎫ ⎝⎛+⋅+⎪⎪⎭⎫ ⎝⎛ =]! 3!1! 4!7!2!9[ 41+ =[36+4]/4 =10(种) 。 4.12. 试用贝恩塞特引理解决n 个人围一圆桌坐下的方案问题。 [解].(参见ppt 第四章§6. 例4.6.7.)目标集： n 个坐位；图象集：n!个着色方案(排坐)。转动群的2n 个置换(参见第7题(第二版)，即第4.17题(第三版))，只有幺元有n!个不动点(图象)，其他2n-1个置换没有不动点(因为没有两个坐位坐同一人)，即 c 1(e)= c 1(P 1)= n!，c 1(P 2)= c 1(P 3)=…= c 1(P 2n )=0。 故由Burnside 引理有 l =[c 1(e)]/2n =n!/ 2n =(n-1)!/2 个方案。 4.13. 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转使之重 合作为相同处理。 [解]. 见第4.13题 图，使之重合的刚体运动群，它含有关于正六角形中心轴旋转±60︒，± 120︒， 180︒的置换，绕过2个对角的轴翻转180o 的置换，以及绕过2个对凹的轴翻转180o 的置换： 不动0︒：(1)(2)(3)(4)(5)(6) 旋转 ±60︒：(1 2 3 4 5 6)，(6 5 4 3 2 1) 旋转 ±120︒：(1 3 5)(2 4 6)，(5 3 1)(6 4 2) 旋转180︒：(1 4)(2 5)(3 6) 翻转(角-角) 180︒：(1)(2 6)(3 5)(4)，(2)(1 3)(4 6)(5)，(3)(1 5)(2 4)(6) 1 2 3 4 5 6 7 8 9 翻转(凹-凹) 180︒：(1 4)(2 3)(5 6)，(1 2)(3 6)(4 5)，(1 6)(2 5)(3 4)。 于是根据Pólya 定理，可得不同的染色方案数为： l = ]5353552525[121343216 ⋅+⋅++⋅+⋅+ =)3751875125501015625(121 +++++ =12 1⋅18060 =1505(种) 。 4.2 5. 若G 和G '是两个群 G ⨯G '≜{(g ,g ')|g ∈ G , g '∈ G ' }, (g 1,g '1) (g 2,g '2)≜(g 1g 2,g '1g '2), G ⨯G '的单位元素是(e ,e ')。试证G ⨯G '成群。 [证]. 1︒封闭性：∀(g 1,g '1) , (g 2,g '2) ∈ G ⨯G ' ⇒( g 1 , g 2 ∈ G )∧ (g '1 , g '2 ∈ G ') ⇒( g 1 g 2 ∈ G )∧ (g '1 g '2 ∈ G ') (群G 和G '的封闭性) ⇒(g 1g 2,g '1g '2) ∈ G ⨯G ' ⇒(g 1,g '1) (g 2,g '2) ∈ G ⨯G ' 因而封闭性成立。 2︒结合律：∀(g 1,g '1) , (g 2,g '2) , (g 3,g '3)∈ G ⨯G ' ((g 1,g '1)(g 2,g '2))(g 3,g '3) =(g 1g 2,g '1g '2)(g 3,g '3) =((g 1g 2)g 3,(g '1g '2)g '3) =(g 1(g 2g 3),g '1(g '2g '3)) (群G 和G '的结合律) =(g 1,g '1)(g 2g 3,g '2g '3) =(g 1,g '1)((g 2,g '2)(g 3,g '3)) 因而结合律成立。 3︒有幺元：(e ,e ')∈ G ⨯G '，这里e 是群 G 的幺元，e '是群G '的幺元。 ∀(g , g ')∈ G ⨯G '，(e ,e ')(g , g ') = (eg , e 'g ') = (g , g ') (eg =g ，e 'g '=g ') = (ge , g 'e ') (g =ge ，g '=g 'e ') = (g , g ')(e ,e ') 因而(e ,e ')是幺元。 4︒有逆元：∀(g , g ')∈ G ⨯G ' ⇒( g ∈ G )∧ (g '∈ G ') ⇒( g -1∈ G )∧ (g '-1∈ G ') (群G 和G '有逆元) ⇒(g -1, g '-1) ∈ G ⨯G ' 使得 (g , g ')(g -1, g '-1) = (gg -1 , g 'g '-1) = (e ,e ') (gg -1= e ，g 'g '-1= e ') = (g -1g , g '-1g ') (g -1g = e ，g '-1g '= e ') = (g -1, g '-1)(g , g ') 因而有逆元。 所以G ⨯G '构成群。 4.26. 若G 是关于X ={x 1, x 2,⋯, x n }的置换群，G '是关于X ' ={x '1, x '2,⋯, x 'm }的置换群，对于G ⨯G '的每一对元素 (g ,g ')(v )≜⎩⎨ ⎧' ∈'∈X v v g X v v g ), (),( 证G ⨯G '是关于X ⋃X '的置换群。 [证].将题中G ⨯G '中的置换的前置定义换为如下等价的后置定义： (v )(g ,g ')≜⎩⎨ ⎧' ∈'∈X v g v X v g v , )(, )(。 因而G ⨯G '={(g ,g ')|g ∈ G , g '∈ G ' }。 于是，我们可定义G ⨯G '上的二元“乘法”运算如下： (g 1,g '1) (g 2,g '2)≜(g 1g 2,g '1g '2)。 由于置换群G 和G '也是群，故根据习题4.25.，可知G ⨯G '是群。又由于G ⨯G '是X ⋃X '上置换的集合，所以G ⨯G '是关于X ⋃X '的置换群。 4.27. 一个项链由7颗珠子装饰而成的，其中两颗珠子是红的，3颗是蓝的，其余两颗是绿 的，问有多少种装饰方案？试列举之？ [解]. 见第4.27题 图，使之重合的刚体运动群，令α= 7 3 51， 它含有关于圆环中心轴旋转 3607 1⋅±=±α， 36072⋅±=±2α， 3607 3⋅±=±3α，以及绕过一个顶点及其对弧中点的轴翻转180o 的置换： 不动0︒：(1)(2)(3)(4)(5)(6)(7) 旋转±α：(1 2 3 4 5 6 7)，(7 6 5 4 3 2 1) 旋转±2α：(1 3 5 7 2 4 6)，(7 5 3 1 6 4 2) 旋转±3α：(1 4 7 3 6 2 5) ，(7 4 1 5 2 6 3) 翻转(点-弧) 180︒：(1)(2 7)(3 6)(4 5)，(2)(1 3)(4 7)(5 6)，(3)(1 5)(2 4)(6 7)，(4)(1 7)(2 6)(3 5)，(5)(1 2)(3 7)(4 6)，(6)(1 2)(3 7)(4 6)，(7)(1 6)(2 5)(3 4)。 将2颗r 色,2颗g 色,3颗b 色的珠子装饰在圆环的7个等分点上的问题，相当于用b ，g ， r 三种颜色对正七边型进行染色。 第4.27题图1 于是根据母函数形式的Pólya 定理，染色方案枚举： P(b ,g ,r )= 14 1 [(b +g +r )7+6(b 7+g 7+r 7)1+7(b +g +r )1(b 2+g 2+r 2)3] 其中b 3g 2r 2的系数即为所求项链串珠方案数： ]111317062237[141⎪⎪⎭ ⎫ ⎝⎛⋅⋅+⋅+⎪⎪⎭⎫ ⎝⎛ =]!1!1!1! 37!2!2!3!7[ 141+ =]42210[141 + =25214 1 ⋅ =18(种)。 所求18种项链串珠方案枚举如下： 4.28.一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜色对8个面进行染 色，试求其中4个顶点为红, 两个顶点为蓝, 黄和绿的面各四面的方案数。 注. 正八面体可以看作是正方体的对偶,每一面用中心代表一个顶点,相交于一个顶点的3个面对应过3个 中心的三角形,由此构成的6个顶点, 8个面的几何图形。 [解].(参见第二版第17题)本题相当于把正八面体的6个顶点、8个面合并起来作为目标集；6个顶点、8个面,共14个元素的置换群。 于是根据母函数形式的Pólya 定理，染色方案枚举： P(r ,b ,y ,g )= 24 1 [(r +b )6(y +g )8+6(r +b )2(r 4+b 4)1(y 4+g 4)2+3(r +b )2(r 2+b 2)2(y 2+g 2) 4 +8(r 3+b 3)2(y +g )2 (y 3+g 3)2+6(r 2+b 2) 3(y 2+g 2)4] 其中r 4b 2 y 4g 4的系数即为所求项链串珠方案数： ]2413608 24)02221202(31 212264826[241⎪⎪⎭ ⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⋅+⋅+⎪⎪⎭⎫ ⎝⎛⋅⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅⋅⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛ 题图2 1 A 2 3 4 5 6 (1) (2) (3) (4) (5) (6) (7) (8) B 1 E 2 3 4 6 (2) (3) (4) (6) (7) (8) F 1 D 2 3 4 5 6 (1) (2) (3) (4) (5) (6) (7) (8) C 第4.28题 图 = ]6366)12(3267015[241 ⨯⨯+⨯+⨯+⨯+⨯ =]10854121050[241 +++ =122424 1 ⋅ =51(种)。 详细的点-面混合的置换群为: 不动 0︒:(1)(2)(3)(4)(5)(6)-(1)(2)(3)(4)(5)(6)(7)(8) 绕外接正方体 面心-面心轴旋转 90︒: (1)(2345)(6)-(1234)(5678) (2)(1563)(4)-(1485)(2376) (3)(1264)(5)-(1562)(3487) -90︒: (1)(5432)(6)-(4321)(8765) (2)(3651)(4)-(5841)(6732) (3)(4621)(5)-(2651)(7843) 180︒: (1)(24)(35)(6)-(13)(24)(57)(68) (2)(16)(35)(4)-(18)(45)(27)(36) (3)(16)(24)(5)-(16)(25)(38)(47) 绕外接正方体 棱中-棱中轴旋转180︒ : (16)(25)(34)-(17)(26)(35)(48) (16)(23)(45)-(15)(28)(37)(46) (24)(15)(36)-(17)(28)(34)(56) (24)(13)(56)-(12)(35)(46)(78) (35)(12)(46)-(14)(28)(35)(67) (35)(14)(26)-(17)(23)(46)(58) 绕外接正方体 顶-顶轴旋转 120︒:(123)(456)-(1)(245)(386)(7) (134)(265)-(2)(163)(457)(8) (145)(236)-(3)(168)(274)(5) (152)(346)-(4)(138)(275)(6) -120︒:(321)(654)-(1)(542)(683)(7) (431)(562)-(2)(631)(754)(8) (541)(632)-(3)(861)(472)(5) (251)(643)-(4)(831)(572)(6) 。 组合数学卢开澄课后习题答案 组合数学是一门研究离散结构和组合对象的数学学科，它广泛应用于计算机科学、统计学、密码学等领域。卢开澄是中国著名的组合数学家，他的教材《组合数学》是该领域的经典之作。在学习组合数学的过程中，课后习题是巩固知识、提高能力的重要途径。下面我将为大家提供一些卢开澄课后习题的答案。第一章：集合与命题逻辑 1.1 集合及其运算 习题1：设集合A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。 答案：A∪B={1,2,3,4}，A∩B={2,3}。 习题2：证明若A∩B=A∩C，且A∪B=A∪C，则B=C。 答案：首先，由A∩B=A∩C可得B⊆C，同理可得C⊆B，因此B=C。然后，由A∪B=A∪C可得B⊆C，同理可得C⊆B，因此B=C。综上所述，B=C。 1.2 命题逻辑 习题1：将下列命题用命题变元表示： （1）如果今天下雨，那么我就带伞。 （2）要么他很聪明，要么他很勤奋。 答案：（1）命题变元P表示今天下雨，命题变元Q表示我带伞，命题可表示为P→Q。 （2）命题变元P表示他很聪明，命题变元Q表示他很勤奋，命题可表示为 P∨Q。 习题2：判断下列命题是否为永真式、矛盾式或可满足式： （1）(P∨Q)→(P∧Q) （2）(P→Q)∧(Q→P) 答案：（1）该命题为可满足式，因为当P为真，Q为假时，命题为真。 （2）该命题为永真式，因为无论P和Q取何值，命题都为真。 第二章：排列与组合 2.1 排列 习题1：从10个人中选取3个人，按照顺序排成一队，有多少种不同的结果？答案：根据排列的计算公式，共有10×9×8=720种不同的结果。 习题2：从10个人中选取3个人，不考虑顺序，有多少种不同的结果？ 答案：根据组合的计算公式，共有C(10,3)=120种不同的结果。 2.2 组合 习题1：证明组合恒等式C(n,k)=C(n,n-k)。 答案：根据组合的计算公式可得C(n,k)=C(n,n-k)，因此组合恒等式成立。 习题2：证明组合恒等式C(n,0)+C(n,1)+...+C(n,n)=2^n。 答案：根据二项式定理可得(1+1)^n=2^n，展开后可得 C(n,0)+C(n,1)+...+C(n,n)=2^n，因此组合恒等式成立。 通过以上习题的解答，我们可以巩固和加深对组合数学的理解。组合数学在实际应用中有着重要的作用，例如在密码学中，组合数学的知识可以用于设计安全的密码算法；在计算机科学中，组合数学的知识可以用于解决图论、优化等问题。希望大家在学习组合数学的过程中能够坚持做习题，提高自己的解题能力和应用能力。 组合数学卢习题答案 组合数学是数学的一个分支，研究的是离散的对象之间的组合方式和计数方法。它在解决实际问题中有着广泛的应用，例如密码学、图论、组织管理等领域。 本文将为读者提供一些卢习题的答案，帮助读者更好地理解和掌握组合数学的 知识。 1. 卢习题一：从一个有10个字母的字母表中选取3个字母，可以有多少种不同的选择方式？ 解答：根据组合数学的知识，从n个不同元素中选取k个元素的组合数可以用 C(n,k)表示。在这个问题中，n=10，k=3，所以答案为C(10,3) = 10! / (3! * (10-3)!) = 120 种不同的选择方式。 2. 卢习题二：一个班级有20名学生，其中10名男生和10名女生。如果要从 这个班级中选取5名学生组成一个小组，其中至少有2名男生和2名女生，有 多少种不同的选取方式？ 解答：这个问题可以用组合数学中的排列组合原理来解决。首先，我们可以分 两种情况来考虑：一种是选取3名男生和2名女生，另一种是选取2名男生和 3名女生。 对于第一种情况，选取3名男生的方式有C(10,3) = 120种，选取2名女生的方 式有C(10,2) = 45种，所以总共有120 * 45 = 5400种不同的选取方式。 对于第二种情况，选取2名男生的方式有C(10,2) = 45种，选取3名女生的方 式有C(10,3) = 120种，所以总共有45 * 120 = 5400种不同的选取方式。 将两种情况的结果相加，总共有5400 + 5400 = 10800种不同的选取方式。 3. 卢习题三：有一个由0和1组成的8位二进制数，其中至少有3个1。问这 样的二进制数有多少个？ 解答：这个问题可以用组合数学中的排列组合原理来解决。首先，我们可以分两种情况来考虑：一种是有3个1，另一种是有4个1、5个1、6个1、7个1和8个1。 对于第一种情况，选取3个位置放置1的方式有C(8,3) = 56种。 对于第二种情况，选取4个位置放置1的方式有C(8,4) = 70种，选取5个位置放置1的方式有C(8,5) = 56种，选取6个位置放置1的方式有C(8,6) = 28种，选取7个位置放置1的方式有C(8,7) = 8种，选取8个位置放置1的方式有 C(8,8) = 1种。 将所有情况的结果相加，总共有56 + 70 + 56 + 28 + 8 + 1 = 219种不同的二进制数。 通过以上几个习题的解答，读者可以看到组合数学在解决实际问题中的应用。它不仅能够帮助我们计算不同选择方式的数量，还能够提供一种思维方式，帮助我们更好地理解和分析问题。希望读者通过这些习题的答案，能够对组合数学有更深入的了解和认识。 １.１ 从{}5021，，，???中找两个数{}b a ,，使其满足 （1） 5||=-b a ； （2）5||≤-b a 解：（1）根据5||=-b a 可得 5 5-=-=-b a b a 或 则有 种 种4545 共有90种。 （2）根据5||≤-b a 得 ) 50,,2,1(,5 5{???∈+≤≤-b a b a b 则：当5≤b 时，有 1=b ， 61≤≤a ， 则有 6种 2=b ， 71≤≤a ， 则有7种 3=b ， 81≤≤a ， 则有8种 4=b ， 91≤≤a ， 则有 9种 5=b ， 101≤≤a ， 则有10种 当455≤ 第一章答案 第二章答案 第三章答案 第四章答案 第一章答案 1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} ) (b) 45?5+(4+3+2+1) = 235 ( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 48→49~50, 49→50 ) 2．(a) 5!8! (b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)! (c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20! 5. 因首数字可分别为偶数或奇数，知结果为 2?5?P(8,2)+3?4?P(8,2). 6. (n+1)!-1 7. 用数学归纳法易证。 8. 两数的公共部分为240530, 故全部公因数均形如2m 5n ,个数为41?31. 9. 设有素数因子分解 n=p 1n 11p 2 n 22…p k n k k , 则n 2的除数个数为 ( 2n 1+1) (2n 2+1) …(2n k +1). 10．1）用数学归纳法可证n 能表示成题中表达式的形式； 2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。 11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。 组合意义： 右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数； 左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。 12．考虑,)1(,)1(10 10 -=-=+=+=∑∑n n k k k n n n k k k n x n x kC x x C 求导数后有 令x=1, 即知.210 -==∑n n k k n n kC 13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。当第二组最大数 为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。故符合要求的不同分组共有12)2()12(2111 1+-=-----=∑n k n k n k n 种。 （另解：设两组共含k 个数(k=2,3,…,n)，则分组数为 ∑2≤k ≤n C(n,k) (k-1) = n 2n-1- 2n +1 . ） 14. 3?2?2. 15. 用k 表示数的位数，用i 表示k 位数中零的个数，则0出现的次数 为 . 15940945924959 )15954910391029519()149439629419()139329319()2929(9 99 9234523452342321 621 1 11 621 1 ?+?+?+?+?=??+??+??+??+??++??+??+??+??+??+??+??+?+?+==--=-=---=-=∑∑∑∑i k i k k k i i k i k k k i C i i C 16. C (n-1, r-1) (每盒中先放一个，再r 中取n-r(可重复)) 17. 易用P(m,n)=m!/(m-n)! 验证等式成立。 第三章 3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通 过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。 [解].令：A 1={通过中文考试的学生} A 2={通过英语考试的学生} A 3={通过数学考试的学生} 于是 |Z| =100，|A 1|=92，|A 2|=75，|A 3|=65 |A 1∩A 2|=65，|A 1∩A 3|=54，|A 2∩A 3|=45 此题没有给出： 有多少人通过三门中至少一门； 有多少人一门都没通过。 但是由 max{ |A 1|,|A 2|,|A 3| }=max{92,75,65}=92 故可以认为： 至少有92人通过三门中至少一门考试，即100≥|A 1∪A 2∪A 3|≥92 至多有8人没通过一门考试，即0≤|1A ∩2A ∩3A | ≤8 于是，根据容斥原理，有 |A 1∪A 2∪A 3|=(|A 1|+|A 2|+|A 3|)-(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)+|A 1∩A 2∩A 3| 即 |A 1∩A 2∩A 3|=|A 1∪A 2∪A 3|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|) =|A 1∪A 2∪A 3|-(92+75+65)+(65+54+45) =|A 1∪A 2∪A 3|-232+164 =|A 1∪A 2∪A 3|-68 从而由 92-68≤|A 1∪A 2∪A 3|-68≤100-68 即 24≤|A 1∪A 2∪A 3|-68≤32 可得 24≤|A 1∩A 2∩A 3| ≤32 故此，通过3门学科考试的学生数在24到32人之间。 也可用容斥原理，即 |1A ∩2A ∩3A |=|Z|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)-|A 1∩A 2∩A 3| =100-(92+75+65)+(65+54+45)-|A 1∩A 2∩A 3| =100-232+164-|A 1∩A 2∩A 3| 3.1 某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议? 解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28 甲参加的会议数为 28+5=33 3.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。 解： 设 A 3：被3整除的数的集合 A 5：被5整除的数的集合 A 7：被7整除的数的集合 所以 || =| |-| | = -=33-4=29 3.3 n 个代表参加会议，试证其中至少有2个人各自的朋友数相等 解：每个人的朋友数只能取0，1，…，n －1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n －2．故这n 个人的朋友数的实际取数只 有 n －1种可能．，根据鸽巢原理所以至少有２人的朋友数相等． ×3.4试给出下列等式的组合意义 0j j 0 (1)=(1), 1n-m -j+1(2)(1)1 j 1(3)...(1) 1 12m l l n m l n m m n l n k m n k l k l n m l n m l m l m l m l m l m l m m m m m l =-=--⎛⎫⎛⎫⎛⎫-≥≥ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭ ---⎛⎫⎛ ⎫⎛⎫= - ⎪ ⎪ ⎪ --⎝⎭ ⎝⎭⎝⎭ +-++++⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫ =-+-+- ⎪ ⎪ ⎪ ⎪ ⎪-+++⎝⎭⎝⎭⎝⎭⎝⎭ ⎝⎭ ∑∑ 证明： 1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？ 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！ n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１ 1.7题 试证：)2()2)(1(n n n ++被2n 除尽。 证明：因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。 第1章 排列与组合 1.1 从{1,2,…,50}中找一双数{a,b}.使其满足： ()5;() 5. a a b b a b -=-≤ [解] (a) 5=-b a 将上式分解.得到55 a b a b -=+⎧⎨ -=-⎩ a = b –5.a=1.2.….45时.b ＝6.7.….50。满足a=b-5的点共50-5=45个点. a = b+5.a=5.6.….50时.b ＝0.1.2.….45。满足a=b+5的点共45个点. 所以.共计2×45=90个点. (b) 5≤-b a (610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。 1.2 5个女生.7个男生进行排列. (a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？ (c) 两男生A 和B 之间正好有3个女生的排列是多少？ [解] (a) 女生在一起当作一个人.先排列.然后将女生重新排列。 （7＋1）!×5!=8!×5!＝40320×120=4838400 (b) 先将男生排列有7!种方案.共有8个空隙.将5个女生插入.故需从8个空中选5个空隙.有5 8C 种选择。将女生插入.有5!种方案。故按乘法原理.有： 7!×58C ×5!=33868800(种)方案。 (c) 先从5个女生中选3个女生放入A.B 之间.有3 5C 种方案.在让3个女生排列.有3!种排列.将这5个人看作一个人.再与其余7个人一块排列.有 (7+1)! = 8! 由于A.B 可交换.如图 **A***B** 或 **B***A** 故按乘法原理.有： 2×3 5C ×3!×8!=4838400（种） 1.3 m 个男生.n 个女生.排成一行.其中m.n 都是正整数.若 (a) 男生不相邻(m ≤n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案. [解] (a) 先将n 个女生排列.有n!种方法.共有n+1个空隙.选出m 个空隙.共有m n C 1+种方法. 习题四 4.1.若群G的元素a均可表示为某一元素x的幂，即a= x m，则称这个群为循环群。若群的 元素交换律成立，即a , b∈G满足 a?b = b?a 则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。 [证].设循环群(G, ?)的生成元是x0∈G。于是，对任何元素a , b∈G，?m，n∈N，使得a= x0m , b= x0n ,从而 a?b = x0m?x0n = x0m +n (指数律) = x0n +m (数的加法交换律) = x0n?x0m(指数律) = b?a 故?运算满足交换律；即(G, ?)是交换群。 4.2.若x是群G的一个元素，存在一个最小的正整数m，使x m=e，则称m为x的阶，试证： C={e,x,x2, ?,x m-1} 是G的一个子群。 [证].(1)非空性C ≠?：因为?e∈G； (2)包含性C?G：因为x∈G，根据群G的封闭性，可知x2, ?,x m-1,(x m=)e∈G，故C?G； (3)封闭性?a , b∈C? a ?b∈C：? a , b∈C，?k，l∈N (0≤k 习题四 4.1.若郡G的元素。均可表示为某一元素X的幕，即« = r,则称这个群为循环郡。若群的元索 交换律成立，W a ,b wG满足 ab = b-a 则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。 ［证］•设循环群(G,・)的生成元是兀owG o于是,对任何元素a,bwG, 3m, nwN,使得*席, b= xo，从而 a b = x()n• X Q =xo/z，+W(指数衛 =xo?，+W(数的加法交换律) =鼎・霸”(指数律) =ba 故•运算满足交换律；即(G,・)是交换群。 4.2.若x是群G的一个元素，存在一个最小的正整数加，使x m=e f则称加为x的阶，试 证: C={e^c,x2, ...y N 1} 是G的一个子群。 ［证］.⑴非空性CH0:因为BeeG； (2)包含性CUG：因为x G G,根据群G的封闭性，可知G,故CgG； (3)封闭性X/d , b G C=>a • b eC： P ci, b G C,3k> IwN (0< k 组合数学第五版答案 【篇一：组合数学参考答案(卢开澄第四版)60页】 使其满足（1）|a-b|=5；（2）|a-b|?5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。所以这样的序列有90对。（2）：由题意知，|a-b|?5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4 或|a-b|=5或|a-b|=0；由上题知当|a-b|=5时有90对序列。当|a- b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。当此类推当 |a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对， 当|a-b|=4时，序列有46*2=92对，当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生a 和b之间正好有3个女生的排列是多少？ 所以总的排列数为上述6种情况之和。 1.3题 m个男生，n个女生，排成一行，其中m,n都是正整数，若 (a)男生不相邻(m?n?1); (b)n个女生形成一个整体；(c)男生a和女生b排在一起；分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n个女生先排成一排，形成n+1个空。因为m?n?1正好m个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 pp n n n?1m (b) n个女生形成一个整体有n！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。因此，共有n!?(m?1)!种可能。 第1章 排列与组合 经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解答： 1.8 1.9 1.16 1.41（答案略） 1.42（答案略） 1.1 从{1,2,…,50}中找一双数{a,b}，使其满足： ()5;() 5. a a b b a b -=-≤ [解] (a) 5=-b a 将上式分解，得到55 a b a b -=+⎧⎨ -=-⎩ a = b –5，a=0时，b ＝5，6，7，…,50。满足a=b-5的点共50-4=46个点. a = b+5，a=5时，b ＝0，1，2，…,45。满足a=b+5的点共45-0+1=46个点. 所以，共计92462=⨯个点. (b) 5≤-b a (610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。 1.2 5个女生，7个男生进行排列， (a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？ (c) 两男生A 和B 之间正好有3个女生的排列是多少？ [解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。 （7＋1）!×5!=8!×5!＝40320×120=4838400 (b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空 中选5个空隙，有5 8C 种选择。将女生插入，有5!种方案。故按乘法原理，有： 7!×58C ×5!=33868800(种)方案。 (c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生 排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有 (7+1)! = 8! 由于A ，B 可交换，如图 **A***B** 或 **B***A** 故按乘法原理，有： 2×3 5C ×3!×8!=4838400（种） 1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若 (a) 男生不相邻(m ≢n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.组合数学卢开澄课后习题答案
组合数学 卢 习题答案
组合数学+卢开澄版++答案第一章
组合数学-卢开澄-习题答案
组合数学第四版卢开澄标准答案-第三章资料
组合数学+卢开澄版++答案第三章
组合数学习题答案卢开澄
组合数学第四版卢开澄标准答案_第一章
组合数学版卢开澄标准答案
组合数学第四版卢开澄标准答案-第四章.docx
组合数学第五版答案
组合数学第三版+卢开澄+习题答案
相关主题
文本预览