组合数学第四版卢开澄标准答案-第四章
习题四
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) 。 作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明： 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 组合数学课后标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?????=4 1(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=2 1 1x -. （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ? ???????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1)x x -=0 k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= () 1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得 李凡长版-组合数学课后习题答案-习题3 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17 组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k 4.1证明所有的循环群是ABEL 群 证明： n n ,,**×x ,x m n m n a b G G a b b a x x a b b a ++∈==∴=m m m 循环群也是群，所以群的定义不用再证，只需证明对于任意是循环群，有成立，因为循环群中的元素可写成a=x 形式所以等式左边x 等式右边x ＝，，即所有 的循环群都是ABEL 群。4.2 x 是群G 的一个元素，存在一最小的正整数m ，使x m =e ，则称m 为x 的阶，试证： C=｛e,x,x 2, …,x m-1｝ 证： x 是G 的元素，G 满足封闭性所以，xk 是G 中的元素 C ∈G 再证C 是群： 1、x i , x j ∈C , x i ·x j = x i+j 若i+j<=m-1,则x i+j ∈C 若i+j>m,那么x i+j =x m+k =x m ·x k =x k ∈C 所以C 满足封闭性。 2、存在单位元e. 3、显然满足结合性。 4、存在逆元， 设x a ·x b =e=x m x b =x m-a x a ∈C, (x a )-1= x b =x m-a 4.3设G 是阶为n 的有限群，则G 的所有元素的阶都不超过n. 证明：设G 是阶为n 的有限群，a 是G 中的任意元素，a 的阶素为k ， 则此题要证n k ≤ 首先考察下列n+1个元素 a a a a a n 1 432,.... ,,,+ 由群的运算的封闭性可知，这n+1个元素都属于G ,，而G 中仅有n 个元素，所 以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为 a a j i i += （n j ≤≤1） a a a j i i *= 由群的性质3可知，a j 是单位元，即a j =e ，又由元素的阶数的定义可知，当a 为k 阶元素时a k =e ，且k 是满足上诉等式的最小正整数，由此可证n j k ≤≤ 4.4 若G 是阶为n 的循环群，求群G 的母元素的数目，即G 的元素可表示a 的 第二章 容斥原理与鸽巢原理 1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000. 记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有： |A 1| = L 10000/4」=2500, |A 2| = L 10000/5」=2000, |A 3| = L 10000/7」=1428, 于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为 | A 1∩A 2|=L 10000/20」=500； 同理， | A 1∩A 3|=L 10000/28」=357, | A 2∩A 3|=L 10000/35」=285, A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为 | A 1∩A 2∩A 3|=L 10000/140」= 71. 由容斥原理知，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 5143 2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除 的整数集合，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - ||321A A A ?? - 2 = 10000 - L 10000/140」- 2 = 9927 3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多 少个？ 解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除， 也能被7整除的整数集。则： |A 1| = L 10000/20」= 500, |A 2| = L 10000/140」= 71, 所以1与10000之间能被4和5整除但不能被7整除的整数的个数为：500-71=429。 4、计算集合{2·a, 3·b, 2·c, 4·d }的5组合数. 解 令S ∞={∞·a, ∞·b,∞·c,∞·d}，则S 的5组合数为()1455 -+ = 56 设集合A 是S ∞的5组合全体，则|A|＝56，现在要求在5组合中的a 的个数小于等 于2，b 的个数小于等于3，c 的个数小于等于2，d 的个数小于等于4的组合数. 定义性质集合P={P 1,P 2,P 3,P 4},其中： P 1：5组合中a 的个数大于等于3； P 2：5组合中b 的个数大于等于4； P 3：5组合中c 的个数大于等于3； P 4：5组合中d 的个数大于等于5. 将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由 S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142 2 -+ = 10. 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 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 除尽。 第五章 P ólya 计数理论 1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类. 解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|S n |＝5。 ??? ? ?????? ?????? ??=512345432152431543215413254321) 23)(14)(5)(234)(123( ??? ? ?????? ??=51234543215214354321 ??? ? ??=5341254321 )5)(34)(12(= （5）（12）（34）的置换的型为1122而S n 中属于1122型的元素个数为15 21!1!2! 52 1=个其共轭类为 （5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24） 2. 设D 是n 元集合,G 是D 上的置换群.对于D 的子集A 和B ,如果存在G ∈σ, 使得}|)({A a a B ∈=σ,则称A 与B 是等价的.求G 的等价类的个数. 解：根据Burnside 引理∑= =n i i a c G l 1 1)(1，其中c 1(a i )表示在置换a i 作用下保持不变的元素个数，则有 c 1(σI )=n; 设在σ的作用下，A 的元素在B 中的个数为i ，则 c 2(σ)=n －2i ； 若没有其他置换，则G 诱出来的等价类个数为l=i n i n n -=-+)]2([2 1 3. 由0,1,6,8,9组成的n 位数,如果把一个数调转过来读得到另一个数,则称这两 个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n 位数有多少个？ 解：该题可理解为相当于n 位数，0，1，6，8，9这5个数存在一定的置换关系 习题四 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 (0k 1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5) 组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right? 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2,a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。 a n可以有两种情况： 1）不管上述序列中是否有2，因为a n的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 f(n+1)= (2n+4n)/2-2f(n), f(1)=2. 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(n)=f(n-3)+2f(n-2) f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 组合数学 双卢 答案 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组合数学课后答案
(完整word版)组合数学课后答案
组合数学课后标准答案
组合数学习题4(共5章)
李凡长版-组合数学课后习题答案-习题3
组合数学题目及标准答案
组合数学(第4板)第四章
李凡长版组合数学课后习题标准答案习题
组合数学 课后答案
组合数学参考答案(卢开澄第四版) - 修改版
李凡长版 组合数学课后习题答案 习题5
组合数学第四卢开澄标准答案第四章Word版
李凡长版 组合数学课后习题答案 习题1
组合数学与图论复习题及参考答案
李凡长版组合数学课后习题答案习题3
组合数学参考答案(卢开澄第四版)60页