组合数学卢习题答案
组合数学是数学的一个分支，研究的是离散的对象之间的组合方式和计数方法。它在解决实际问题中有着广泛的应用，例如密码学、图论、组织管理等领域。
本文将为读者提供一些卢习题的答案，帮助读者更好地理解和掌握组合数学的
知识。
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章 排列与组合 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!×5 8C ×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+种
第三章 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|
组合数学 例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
填空题 1．将5封信投入3个邮筒，有_____243 _种不同的投法． 2．5个男孩和4个女孩站成一排。如果没有两个女孩相邻，有 43200 方法． 3．22件产品中有2件次品，任取3件，恰有一件次品方式数为__ 380 ______． 4．6()x y +所有项的系数和是_64_ _．答案：64 5．不定方程1232++=x x x 的非负整数解的个数为_ 6 ___． 6．由初始条件f f (0)1,(1)1==及递推关系)()1()2(n f n f n f ++=+确定的数列 f n n {()}(0)≥叫做Fibonacci 数列 7．（3x-2y ）20 的展开式中x 10y 10的系数是 10101020 )2(3-c ． 8．求6的4拆分数P 4(6)= 2 ． 9．已知在Fibonacci 数列中，已知f f f (3)3,(4)5,(5)8===，试求Fibonacci 数f (20)=10946 10．计算P 4(12)= k k P P P P P P 4 412341 (12)(12)(8)(8)(8)(8) ===+++∑k k k k P P P P 34 121 1 (8)(8)(5)(4)145515===+++=+++=∑∑ 11．P 4(9)=（ D ）A ．5 B. 8 C. 10 D. 6 12．选择题 1．集合A a a a 1210{,,,}=的非空真子集的个数为（ A ）A.1022 B.1023 C. 1024 D.1021 2．把某英语兴趣班分为两个小组，甲组有2名男同学，5名女同学；乙组有3名男同学，6名女同学，从甲乙两组均选出3名同学来比赛，则选出的6人中恰有1名男同学的方式数是（ D ） A ．800 B. 780 C. 900 D. 850 3．设x y (,)满足条件x y 10+≤，则有序正整数对x y (,)的个数为（ D ） A. 100 B.81 C. 50 D.45 4．求60123(32)+++x x x x 中x x x 23 012项的系数是（ C ） A.1450 B. 60 C.3240 D.3460 5．多项式40123(24)x x x x +++中项2 2012x x x ??的系数是（ C ） A ．78 B. 104 C. 96 D. 48 6．有4个相同的红球，5个相同的白球，那么这9个球有（ B ）种不同的排列方式 A. 63 B. 126 C. 252 D.378 7．递推关系f n f n f n ()4(1)4(2)=---的特种方程有重根2，则（B ）是它的一般解 A ．n n c c 11222-+ B. n c c n 12()2+ C. n c n (1)2+ D. n n c c 1222+ 8．用数字1,2,3,4（数字可重复使用）可组成多少个含奇数个1、偶数个2且至少含有一个3的n n (1)>位数（ ）运用指数生产定理 A.n n n 43(1) 4 -+- B. n n 4314-+ C.n n 4213 -+ D. n n n 43(1)3-+-
组合数学与图论复习题及答案 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个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入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. 把101本书分给10名学生，则下列说法正确的是（） A.有一名学生分得11本书 B.至少有一名学生分得11本书 C.至多有一名学生分得11本书 D.有一名学生分得至少11本书 2. 8人排队上车，其中A ，B 两人之间恰好有4人，则不同的排列方法是（） A.!63? B.!64? C. !66? D. !68? 3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（） A.()4,11!10 P ? B. ()4,9!10P ? C. ()4,10!10P ? D. !3!14- 4. 把10个人分成两组，每组5人，共有多少种方法（） A.???? ??510 B.??? ? ?????? ??510510 C.??? ? ??49 D.???? ??????? ??4949 5. 设x,y 均为正整数且20≤+y x ，则这样的有序数对()y x ,共有（）个 A.190 B.200 C.210 D.220 6. 仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（） A.128 B.252 C.343 D.192 7. 百位数字不是1且各位数字互异的三位数的个数为（） A.576 B.504 C.720 D.336 8. 设n 为正整数，则∑=???? ??n k k n 02等于（） A.n 2 B. 1 2-n C. n n 2? D. 12-?n n 9. 设n 为正整数，则()k k n k k n 310???? ??-∑=的值是（） A.n 2 B. n 2- C. ()n 2- D.0 10. 设n 为正整数，则当2≥n 时，∑=???? ??-n k k k 22=()
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 除尽。
习题四 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 第一章答案 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, 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. 41⨯31 9. 设 n=p 1 n 1p 2 n 2…p k n k , 则n 2的除数个数为 ( 2p 1 +1) (2p 2 +1) …(2p 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 1 -=-=+=+=∑∑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出现的次数为 1 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 除尽。 组合数学引论第2版答案pdf 题型：选择题 1. 从8个不同的数字中任选3个数字组成的不同三位数的个数为： A. 56 B. 336 C. 504 D. 672 答案：B 2. 俱有10件物品，从中任取4件，则下列说法正确的是： A. 取法种数为10 B. 取法种数为210 C. 取法种数为840 D. 取法种数为5040 答案：C 3. 2n个相同的球放入两个已标相同的盒子中，问每个盒子至少放几个球，使得两个盒子中的球数均不少于n？（n≧2） A. n B. n-1 C. n/2 D. （n+1）/2 答案：D 4. 某学校有30名运动员，其中有17名会游泳，16名会跑步，8名既会游泳又会跑步。那么学校中至少有几名不会游泳也不会跑步的运动员？ A. 0 B. 1 C. 2 D. 3 答案：C 5. 设S是4个不同的字母所组成的集合，则S的一个子集中至少包含1个元素的子集数为： A. 15 B. 16 C. 23 D. 24 答案：D 题型：填空题 6. 用给定的集合中的数填空，使得等式成立。 {1,2,3,6,7,8} _______+_______=16 答案：3、13 7. 一个5位的二进制数中恰好有3个1的数共有_______个。 答案：10 8. 从整数1,2,3,……15中选出5个数，使其和为36的选法有 _______种。 答案：20 9. 由10个相同的小球，放入两个相同的盒子中，使得每个盒子中至少有一个球的方法数为_______。 答案：63 10. 从8个人中选出3人组成一委员会，主席、副主席共有________种选法。 答案：56 题型：解答题 11. 在正方形ABCD中，M、N、P、Q是边AB、BC、CD和DA上的点，试用组合数学的方法证明四边形MNPQ是平行四边形。 答案：证明过程略。 12. 用组合数学的方法计算：\sum_{k=0}^n (-1)^k \cdot \displaystyle{n\choose k} \cdot (m-k)^n 的值。 答案：0 13. 一个凸n边形的顶点用各种不同颜色染色，试求出共有多少种染色方案。 答案：2^n+n-1 14. 一个筒内有10个相同的球，其中有4个黑球，6个白球。将黑球均匀地随机地放回筒内，再将白球均匀随机地放回筒内。设X是白球首次放回筒内前的黑球个数，求X的概率分布列。（请用表格形式列出概率分布列） 答案：略。 15. 已知两组等式：\sum_{k=0}^n \displaystyle{n \choose k} 2^k = 3^n，\sum_{k=0}^n \displaystyle{n \choose k} (-2)^k = (- 1)^n 试用组合数学的方法证明下列等式： \sum_{k=0}^n \displaystyle{n \choose k} (-1)^k 2^{n-k} = (- 李凡长版-组合数学课后习题答案习题4 24 第四章 生成函数 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 -）2. （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 的系数，便得 作业习题答案 习题二 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)行 1 1 2 m m + ⎛⎫ + ⎪ ⎝⎭ 列的网格每个格子涂1种颜色.有m种颜色可以选 择.证明：无论怎么涂色.其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言.有（m+1）行.m种颜色.有鸽巢原理.则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有 1 2 m+ ⎛⎫ ⎪ ⎝⎭ 种.这样一列中两个同色单元格的位置 组合共有 1 2 m m + ⎛⎫ ⎪ ⎝⎭ 种情况 第一章排列组合 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个数为(；卜1 = 14。 (或：2 - 2* 4 = 14) (3)串中有4个1:分两种情况：①3个0单独插入，出去1010101，共3 -1 种；②其中两个0 —组，另外一个单独，则有2 P(2,2)— 4 *2种。 (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。 以a1,a2,a3,a u分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a1+10a2+100a3+1000a4 0 因为个位数字为2, 4, 6的偶数各有60个，故a1 = (2+4+6)*60=720。因为千(百， 十)位数字为1, 3, 5的偶数各有3*P(4,2) = 36个，为2, 4, 6的偶数各有2*P(4,2) = 24个，故 a2 = a3 = a4 = (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相邻：2 3 P(4,4)。故有1和2但它们不相邻的方案数： 5 P(5,5) -2 5 P(4,4) 只有 1 或2： 2 5 P(5,5) 没有1和2：P(5,5)组合数学课后习题答案
(完整版)组合数学习题答案卢开澄
组合数学引论第2版答案pdf
李凡长版-组合数学课后习题答案习题4
组合数学课后答案
李凡长版组合数学课后习题答案习题1
相关主题
文本预览