下载文档原格式
第一章答案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 种。
组合数学基础答案及讲稿（陶平生）基本内容与方法：组合计数；组合构造；组合结构；映射与对应；分类与染色；归纳与递推；容斥原理；极端原理；调整法；补集法；数形结合法，等等．1、设M 为n 元集，若M 有k 个不同的子集12,,,k A A A ，满足：对于每个{},1,2,,i j k ∈ ，i j A A ≠∅ ，求正整数k 的最大值．解：正整数k 的最大值为12n -．()01、先证明，存在M的12n -个子集，两两之交不空；设{}12,,,n M a a a = ，而1122,,,n A A A - 为集合{}121,,,n a a a - 的全部12n -个子集，令{}1,1,2,,2n i i n B A a i -== ，则M 的12n -个子集1122,,,n B B B - ，两两之交不空；()02、再证，对于M的任何121n -+个子集，其中必有两个子集不相交．设1122,,,n B B B - 是M 的12n -个不同子集，其中每个皆含n a ；用i B 表示子集i B 在M 中的补集，1(\),1,2,,2n i i B M B i -== ，则对于任意i j ≠，,i j i j B B B B ≠≠，并且j i B B ≠， （因前者含n a 而后者不含），故1122,,,n B B B - ，1122,,,n B B B - 为M 的全部2n个不同子集，现将上述集合搭配成为12n -对：()()()11122122,,,,,,n n B B B B B B -- ；任取M 的121n -+个子集，必有两个子集属于同一对，则这两个子集不相交．2、将前九个正整数1,2,,9 分成三组，每组三个数，使得每组中的三数之和皆为质数；求出所有不同分法的种数．证：()01、由于在1,2,,9 中，三个不同的数之和介于6和24之间，其中的质数有7,11,13,17,19,23这六个数，今将这六数按被3除的余数情况分为两类：{}7,13,19A =，其中每个数被3除余1；{}11,17,23B =，其中每个数被3除余2；假若所分成的,,A B C 三组数对应的和,,a b c p p p 为互异质数，则因12945a b c p p p ++=+++= 被3整除，故三个和数,,a b c p p p 必为同一类数，因为A 类三数和713193945++=<，B 类三数和1117235145++=>，矛盾！ 故三个和数中必有两个相等．()02、据()01知，将45表成7,11,13,17,19,23中的三数和（其中有两数相等），只有四种情况：()119197++；()2171711++；()3131319++；()4111123++．由于在1,2,,9 中有5个奇数，故分成的三组中必有一组，三数全为奇数，另两组各有一个奇数．对于情形()1，和为7的组只有{}1,2,4，剩下六数3,5,6,7,8,9，分为和为19的两组，且其中一组全为奇数，只有唯一的分法：{}3,7,9与{}5,6,8；对于情形()2，若三奇数的组为{}1,7,9，则另两组为 {}{}4,5,8,2,3,6；或{}{}3,6,8,2,4,5；若三奇数的组为{}3,5,9，则另两组为 {}{}2,8,7,1,4,6，或{}{}4,6,7,1,2,8； 若三奇数的组为{}1,3,7，则另两组为 {}{}2,6,9,4,5,8；共得分法5种；对于情形()3，若三奇数的组为{}3,7,9，则另两组为 {}{}1,4,8,2,5,6； 若三奇数的组为{}1,3,9，则另两组为 {}{}2,4,7,5,6,8或{}{}2,5,6,4,7,8； 若三奇数的组为{}1,5,7，则另两组为 {}{}3,4,6,2,8,9或{}{}2,3,8,4,6,9； 共得分法5种；对于情形()4，和为23的组只有{}6,8,9，则另两组为 {}{}1,3,7,2,4,5； 据以上，共计得到155112+++=种分法．3、设正整数a 的各位数字全由1和2组成，由其中任意() 2k k ≥个连续数位上的数字所组成的k 位数，称为数a 的一个“k 段”；若数a 的任两个“k 段”都不相同．证明：对于具有这种性质的最大正整数a ，其开初的一个“1k -段”和最后的一个“1k -段”必定相同.证：设12n a x x x = 是一个具有这种性质的最大正整数，由a 的最大性，在其后面无论添加1或2，所得到的1n +位数1121n a x x x = 以及2122n a x x x = 中，都有两个相同的“k 段”. 设在1a 中有 1121i i i k n k n x x x x x ++--+= ；在2a 中有1122j j j k n k n x x x x x ++--+= . 显然i j ≠，（因为11i k j k x x +-+-≠），且11i n k ≤≤-+，11j n k ≤≤-+，如果1i =或1j =，则直接去掉相应“k 段”中的末位数，可知结论成立；如果2i ≥且2j ≥，因 12212i i i k n k n j j j k x x x x x x x x ++--+++-== ，考虑各自的前一位数字111, , i j n k x x x ---+，它们只取1和2两个值，其中必有两数相同，于是数a 中有两个相同的“k 段”，矛盾. 因此,i j 中必有一个为1，故结论得证.4、将数集},...,,{21n a a a A =中所有元素的算术平均值记为)(A P ，（na a a A P n+++=...)(21）. 若B 是A 的非空子集，且)()(A P B P =，则称B 是A的一个“均衡子集”．试求数集}9,8,7,6,5,4,3,2,1{=M 的所有“均衡子集”的个数． 解：由于()5P M=，令{}{}54,3,2,1,0,1,2,3,4M x x M '=-∈=----，则()0P M '=, 依照此平移关系，M 和M '的均衡子集可一一对应．用()f k 表示M '的k 元均衡子集的个数，显然有(9)(1)1f f ==(M '的9元均衡子集只有M '，一元均衡子集只有{}0)．M '的二元均衡子集共四个，为{,},1,2,3,4i B i i i =-=, 因此(2)4f =． M '的三元均衡子集有两种情况：（1）含有元素0的为{0}{,0,},1,2,3,4i B i i i =-= , 共四个；（2）不含元素0的，由于等式312,413=+=+可表示为3120,3120-++=--=以及4130,4130-++=--=，得到4个均衡子集{3,1,2},{3,1,2},{4,1,3},{4,1,3}------，因此(3)448f =+=．M '的四元均衡子集有三种情况：（1）每两个二元均衡子集之并：,14i j B B i j ≤<≤ , 共6个集； （2）不含元素0的三元均衡子集与{}0的并集，共4个集；（3）以上两种情况之外者，由于等式1423+=+可表为14230--++=以及14230+--=得2个均衡子集{1,4,2,3}--与{1,4,2,3}--，因此()464212f =++=． 又注意到，除M '本身外，若B '是M '的均衡子集，当且仅当其补集''M C B 也是M '的均衡子集，二者一一对应. 因此(9)(),1,2,3,4f k f k k -==．从而M '的均衡子集个数为9411()(9)2()12(14812)51k k f k f f k ===+=++++=∑∑．即M 的均衡子集有51个．5、某校有2010名新生，每人至少认识其中n 人，试求n 的最小值，使得其中必存在彼此认识的16个人.解：记这2010个人的集合为{}122010,,,M v v v = ，i v 所认识的人的集合记为, 1,2,2010i A i = ，则i A n ≥，且 1,2,2010i i v A i ∉= ，若12,v v 是M 中相识的两人，则有121222010A A A A A B n =+-≥- ， 当220101n -≥，则有312v A A ∈ ，且123,,v v v 两两相识，而()123123123322010A A A A A A A A A n =+-≥-⋅ .当3220101n -⋅≥，则有4123v A A A ∈ ，且1234,,,v v v v 两两相识，而()123412341234432010A A A A A A A A A A A A n =+-≥-⋅ ，如此继续，得1215,,,v v v 两两相识，而151414151511115142010i i i i i i A A A A A n ===⎛⎫=+-≥-⋅ ⎪⎝⎭. 当151420101n -⋅≥，则有15161, i i v A =∈ 且1216,,,v v v 两两相识,而由151420101n -⋅≥，得142010115n ⋅+≥，n 为整数，则1877n ≥.再说明1877n =是最小的；若1876n =，我们可构造一种情形，使得M 中不存在相互认识的16个人．为此，将2010个人均分为1215,,,B B B 等15组，每组134个人，令同组的人互不相识，而异组的任两人皆相识，则M 中任一人v 所认识的人的个数皆为()141341876d v =⨯=，从M 中任取16个人，必有两个人属于这15组中的同一个组，于是这两人互不相识，因此M 中不存在相互认识的16个人.从而n 的最小值为1877.6、有()2nn ≥名运动员，其编号分别是1,2,,n ，在一次活动中，他们以任意方式站成了一排. 如果每次允许将其中一些人两两对换位置，但在同一轮操作过程中,任一人至多只能参与一次这种对换.证明：至多只需两轮这样的操作，可使队列变成1,2,,n 的顺序排列. 证明：对n 归纳，2≤n 时显然. 设n k ≤时结论成立；今证1n k =+时情形，设121,,...,k a a a +是1k +名运动员1,2,,1k + 的任一排法, （i ） 如果其中存在一组运动员()12,, (1)i i i a a a m k ≤≤，他们的编号恰好就是其位置序号组k i i i ,...,,21的一个排列，则由归纳假设，这组运动员可经至多两轮操作，分别到位于自然位置（使i 号运动员到位于i 位），而剩下的1k m +-个运动员，显然也是其所处位置号的排列，他们也可经过至多两轮对换到位于自然位置，这样，队列121,,...,k a a a +可经两轮对换化为1,2,,1k +（ii ） 若（i ）中的情形不出现，为叙述方便，设1号位置上所站的运动员编号为1b ， （11≠b ），1b 号位置上的运动员编号为2b ，（{}12,1b b ∉），2b 号位置上的运动员编号为3b ，（{}213,,1b b b ∉），...，j b 号位置上的运动员编号为1+j b ，（{}j j b b b ,...,,111∉+），...，k b 号位置上的运动员编号为1。
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 m n mk 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)×(1/2)的正方形．如上图.则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于．3.7题（王星）在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．证：把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．3.8题（王星）任取11个整数，求证其中至少有两个数它们的差是10的倍数。
第三章递推关系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个。
