下载文档原格式
组合数学引论课后习题答案组合数学引论课后习题答案组合数学是一门研究离散结构和计数问题的数学学科，它在计算机科学、密码学、统计学等领域中有着广泛的应用。
在学习组合数学的过程中，课后习题是巩固知识、提高技能的重要环节。
本文将为大家提供一些组合数学引论课后习题的答案，希望能对大家的学习有所帮助。
1. 问题：有6个不同的球，要将其放入3个不同的盒子中，每个盒子至少放一个球，一共有多少种放法？解答：这是一个将球放入盒子的问题，可以使用组合数学中的排列组合方法求解。
首先，我们可以确定每个盒子中至少放一个球，所以可以将问题转化为将剩下的3个球放入3个盒子中的问题。
对于每个球来说，都有3个选择，即放入第一个盒子、放入第二个盒子或放入第三个盒子。
因此，总的放法数为3^3=27种。
2. 问题：有8个人，其中4个人是男性，4个人是女性，要从中选出一个小组，要求男性人数和女性人数相等，一共有多少种选法？解答：这是一个选择问题，可以使用组合数学中的组合方法求解。
首先，我们需要确定男性和女性的人数必须相等，所以可以将问题转化为从4个男性和4个女性中各选取相同数量的人的问题。
对于男性来说，可以从4个人中选择0个、1个、2个、3个或4个。
对于每种选择，女性也需要选择相同数量的人。
因此，总的选法数为C(4,0) * C(4,0) +C(4,1) * C(4,1) + C(4,2) * C(4,2) + C(4,3) * C(4,3) + C(4,4) * C(4,4) = 1 + 16 + 36 + 16 + 1 = 70种。
3. 问题：有10个人，要从中选出一个小组，要求这个小组中至少有3个人，一共有多少种选法？解答：这是一个选择问题，可以使用组合数学中的组合方法求解。
首先，我们需要确定小组中至少有3个人，所以可以将问题转化为从10个人中选取3个、4个、5个...直到10个人的问题。
对于选取3个人的情况，可以从10个人中选择3个，即C(10,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=333.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 ml 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）从n 个不同元素中取k ，使得其中必含有m 个特定元素的方案数为)()(kn m n mk m n --=--。
设这m 个元素为a 1,a 2,…,a m , Ai 为包含a i 的组合（子集），i=1,…,m.1212|...|(...)12 =(...(1))1 2 =(1) m m m ln A A A A A A k n m n m n m n m k k k m k m n l l k ⎛⎫=- ⎪⎝⎭---⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭-⎛⎫⎛- ⎪⎝⎭ 0ml =⎫⎪⎝⎭∑（2）把l 个无区别的球放到n 个不同的盒子，但有m 个空盒子的方案数为11n l m n m -⎛⎫⎛⎫⎪ ⎪--⎝⎭⎝⎭令k=n-m ，设A i 为第i 个盒子有球，i=1，2，…k12k 121|...|(...)1k 11211 =(...(1)) 1 2 k kk l A A A A A A k k l k l k k l k k k l k l l k l +-⎛⎫=- ⎪⎝⎭+--+--+--+-⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭kj j 0k k-j+1 =(1)j l l =-⎛⎫⎛⎫- ⎪ ⎪⎝⎭⎝⎭∑（3）设A i 为m+l 个元素中去m+i 个，含特定元素a 的方案集；N i 为m+l 个元素中取m+i个的方案数。
第2章 鸽巢原理2.4 练习题1、关于本节中的应用4，证明对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋（情形=k 21是在应用4中处理的情况）。
能否判断：存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？证明：设i a 表示在前i 天下棋的总数若正好有i a =k ,则命题得证。
若不然,如下：∵共有11周，每天至少一盘棋，每周下棋不能超过12盘∴有 771≤≤i ，且13217721≤<<<≤a a a {}21,,2,1 ∈∀k 有kk a k a k a k +≤+<<+<+≤+13217721 观察以下154个整数：ka k a k a a a a +++77217721,,,,,,, 每一个数是1到k +132之间的整数，其中153132≤+k 由鸽巢原理，这154个数中至少存在两个相等的数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了k 盘棋。
综上所述，对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋。
□当k =22时，132+k =154，那么以下154个整数22,,22,22,,,,77217721+++a a a a a a在1到154之间。
ⅰ）若这154个数都不相同则它们能取到1到154的所有整数，必然有一个数是22∵2222>+i a ，771≤≤i ∴等于22的数必然是某个i a ，771≤≤i则在前i 天，这位国际象棋大师总共下了22盘棋。
ⅱ）若这154个数中存在相同的两个数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了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)!-17. 用数学归纳法易证。
8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn 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(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。
当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。
故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。
组合数学参考答案（卢开澄第四版）60页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对序列总数=94+96+5201.2题5个女生，7个男生进行排列，(a)若女生在一起有多少种不同的排列？(b)女生两两不相邻有多少种不同的排列？(c)两男生a和b之间正好有3个女生的排列是多少？解决方案：（a）五个女孩可以被视为一个单元，总共八个单元可以全部安排。
安排号码是：8！×5！，（b）男孩用X，空缺用y。
把男孩放在第一位。
总共有8个空缺在其中任取5个得到女生两两不相邻的排列数：c（8，5）×7！×5！（c）先取两个男生和3个女生做排列，情况如下：6.若a，b之间存在0个男生，a，b之间共有3个人，所有的排列应为p6=c(5,3)*3!*8!*21．若a，b之间存在1个男生，a，b之间共有4个人，所有的排列应为p1=c(5,1)*c(5,3)*4!*7!*22．若a，b之间存在2个男生，a，b之间共有5个人，所有的排列应为p2=c(5,2)*c(5,3)*5!*6!*23．若a，b之间存在3个男生，a，b之间共有6个人，所有的排列应为p3=c(5,3)*c(5,3)*6!*5!*24．若a，b之间存在4个男生，a，b之间共有7个人，所有的排列应为p4=c(5,4)*c(5,3)*7!*4!*25．若a，b之间存在5个男生，a，b之间共有8个人，所有的排列应为p5=c(5,5)*c(5,3)*8!*3!*2因此，排列的总数是上述六种情况的总和。
3.1题（宗传玉）某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议解:设A i为甲与第i个朋友相遇的会议集，i＝1，…，6．则故甲参加的会议数为:28+5=33.3.2题（宗传玉）求从1到500的整数中被3和5整除但不被7整除的数的个数.解:设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合所以3.3.题（宗传玉）n个代表参加会议，试证其中至少有2人各自的朋友数相等。
解:每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种可能．，所以至少有２人的朋友数相等．3.4题（宗传玉）试给出下列等式的组合意义.解:(a) 从n 个元素中取k 个元素的组合，总含有指定的m 个元素的组合数为)()(kn mn m k m n --=--。
设这m 个元素为a 1,a 2,…,a m ,Ai 为不含a i 的组合（子集），i=1,…,m.()∑∑∑==∈⊄==⎪⎪⎭⎫⎝⎛-⎪⎪⎭⎫ ⎝⎛-=-+⎪⎪⎭⎫ ⎝⎛==⎪⎪⎭⎫⎝⎛--⎪⎪⎭⎫⎝⎛-=ml l m l l m i i lj i lk l n k m A k n k n m n k l n l j 01),(),...,(1m1i i i i i 1)1(A A A A 111213.5题（宗传玉）设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．试证存在整数i 和j，1≤i≤j≤7，使得下列之一必定成立：a i=a j=b i=b j，a i=a j=c i=c j，b i=b j=c i=c j．证：显然，每列中必有两数字相同，共有种模式，有０或１两种选择．故共有·2种选择．·2=6．现有7列，．即必有２列在相同的两行选择相同的数字，即有一矩形，四角的数字相等．3.6题（宗传玉）在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于证：把１×１正方形分成四个(1/2)×.则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于．3.7题（王星）在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．证：把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．3.8题（王星）任取11个整数，求证其中至少有两个数它们的差是10的倍数。
作业习题答案习题二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)行112mm+⎛⎫+⎪⎝⎭列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。
证明：（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。
（2）每列中两个单元格的不同位置组合有12m+⎛⎫⎪⎝⎭种，这样一列中两个同色单元格的位置组合共有12mm+⎛⎫⎪⎝⎭种情况（3）现在有112m m +⎛⎫+⎪⎝⎭列，根据鸽巢原理，必有两列相同。
第三章递推关系1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系.解： f(n)=f(n-1)+2f(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 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），可得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”的可能；依此类推，有f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2f(2)=1,f(3)=1,f(4)=2.6.求n 位0,1序列中“010”只出现一次且在第n 位出现的序列数f(n).解：最后三位是“010”的序列共有2n-3个。
