组合数学习题解答

第一章：1.2.求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。1.4.10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一起的方式共有10！-2*9！。1.5.10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？解：这是一组圆排列问题，10个人围圆就坐共有10!10种方式。两人坐在一起的方式数为9!92,故两人不坐在一起的方式数为：9！-2*8！。1.14.求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？解：(1)在1到9999中考虑，不是4位数的整数前面补足0，例如235写成0235,则问题就变为求：x1+x2+x3+x4=5的非负整数解的个数，故有F（4，5）515456(2)分为求：x1+x2+x3+x4=4的非负整数解，其个数为F（4，4）=35x1+x2+x3+x4=3的非负整数解，其个数为F（4，3）=20x1+x2+x3+x4=2的非负整数解，其个数为F（4，2）=10x1+x2+x3+x4=1的非负整数解，其个数为F（4，1）=4x1+x2+x3+x4=0的非负整数解，其个数为F（4，0）=1将它们相加即得，F（4，4）+F（4，3）+F（4，2）+F（4，1）+F（4，0）=70。第二章：2.3.在边长为1的正三角形内任意放置5个点，则其中至少有两个点的距离1/2。解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离1/2。1/21/21/22.5.在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。解：每列着色的方式只可能有224种，现有5列，由鸽笼原理知，至少有二列着色方式相同。2.7.一个学生打算用37天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样按排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时。解：设1a是第一天自学的时数，2a是第一，二天自学的时数的和，ja是第一，二，…，第j天自学时数的和，1,2,,37j于是，序列1237,,,aaa是严格递增序列(每天至少一学时)，而且，1371,60aa于是序列13713,,13aa也是严格递增的序列，故371373a因此74个数137137,,13,,1373aaaa都在1和73两个整数之间，由鸽笼原理知，这74个数中必有两个是相等的，由于1237,,,aaa中任何两数都不相等，故13713,,13aa中任何两个数也是不相等的，因此，一定存在两个数,ij使得1313ijijaaaa因此，在1,2,,jji这些天中，这个学生自学总时数恰好为13。2.10.证明：在任意52个整数中，必存在两个数，其和或差能被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或ri+rj=100,这就是说ai—aj可100整除，或ai+aj可被100整除。第三章3.2.求1到1000中既非完全平方又非完全立方的整数个数。解：设S＝{1,2,…,1000};1A表示1到1000中完全平方数的集合，则1A表示1到1000中不是完全平方数的集合；2A表示1到1000中完全立方数的集合，则2A表示1到1000中不是完全立方数的集合。故__2__1AA表示1到1000中既非完全平方又非完全立方的整数的集合，由容斥原理（（3.5）式）知：212121AAAASAA(3.5)其中||S＝1000，1||100031A,32||100010A21AA表示1到1000中既是完全平方又是完全立方的数的集合，故21AA=61000=3,将以上数值代入(3.5)式得21AA＝1000－(31+10)+3=962故1到1000中既非完全平方又非完全立方的整数个数为962。3.8.在所有的n位数中，包含数字3，8，9但不包含数字0，4的数有多少？解：除去0，4，则在1，2，3，5，6，7，8，9这8个数字组成的n位数中，令S表示由这8个数字组成的所有n位数的集合。则|S|=8n.P1表示这样的性质：一个n位数不包含3；P2表示这样的性质：一个n位数不包含8；P3表示这样的性质：一个n位数不包含9；并令Ai表示S中具有性质Pi的元素构成的集合（i=1,2,3）。则AAA321表示S中包含3，又包含8，又包含9的所有n位数的集合。由容斥原理（（3.5）式）得|321AAA|=||||||||32131AAAAAASjijiii（3.5）而777321,,nnnAAA666323121,,nnnAAAAAA5321nAAA，代入（3.5）式得123837365nnnnAAA故所求的n位数有nnnn563738个。3.10.求重集3,4,5Babc的10-组合数。解：构造集合B′=},,{cba。令集合B′的所有10-组合构成的集合为S。由第一章的重复组合公式(1.11)有||S＝F（3，10）＝101103=66。令p1表示S中的元素至少含有4个a这一性质，令p2表示S中的元素至少含有5个b这一性质，令p3表示S中的元素至少含有6个c这一性质，并令Ai(i=1,2,3)表示S中具有性质pi(i=1,2,3)的元素所构成的集合，于是B的10-组合数就是S中不具有性质p1,p2,p3的元素个数。由容斥原理（（3.5）式）有：|321AAA|=||||||||32131AAAAAASjijiii(3.5)由于已经求得||S=66，下面分别计算(3.9)式右端其他的项。由于A1中的每一个10-组合至少含有4个a，故将每一个这样的组合去掉4个a就得到集合B′的一个6-组合。反之，如果取B′的一个6-组合并加4个a进去，就得到了A1的一个10-组合。于是A1的10-组合数就等于B′的6-组合数。故有||1A=F（3，6）＝6163＝28同样的分析可得||2A=F（3，5）＝5153＝21||3A=F（3，4）＝4143＝15用类似的分析方法可分别求得||21AA＝F（3，1）＝1113＝3||31AA＝F（3，0）＝0103＝1||32AA＝0（因为5＋6＝1110）||321AAA＝0（同上）将以上数值代人(3.9)式得到：|321AAA|＝66－（28＋21＋15）＋（3＋1＋0）－0＝6故所求的10-组合数为6。3.14.求由数字1，2，8所组成的全排列中，恰有4个数字在其自然位置上的全排列个数。解：4个数在其自然位置共有48种方式，对某一种方式，均有4个数字不在其自然位置，这正好是一个错排，其方式数为4D（见定理3.2），由乘法规则有，恰有4个数字在其自然位置上的全排列数为484D＝630。第四章4.6求重集}7,5,3,{dcbaB的10-组合数。解：设重集B的n-组合数为na，则序列{na}的普通母函数为2232345()(1)(1)(1)fxxxxxxxxxxx234567(1)xxxxxxx=xxxxxxx11111111864=(1-x4-x6-x8+x10+x12+x14-x18)033kkxk所以a10=3033233433633103=286-84-35-10+1=158故重集B的10－组合数为158。4.9.设重集123456,,,,,Bbbbbbb,并设ra是B满足以下条件的r-组合数，求序列01,,,,raaa的普通母函数。a.每个Ib出现3的倍数次。1,2,3,4,5,6Ib.1b,2b至多出现1次，34,bb至少出现2次，56,bb最多出现4次。c.1b出现偶数次，6b出现奇数次，3b出现3的倍数次，4b出现5的倍数次。d.每个Ib1,2,3,4,5,6I至多出现8次。解：a.3696()(1)fxxxx30(6,)()kkFkxb.223422342()(1)()(1)fxxxxxxxxxc.2435369510()(1)()(1)(1)fxxxxxxxxxxx(1xxx232++++)d.2386()(1)fxxxx4.10有两颗骰子，每个骰子六个面上刻有1，2，3，4，5，6个点。问掷骰子后，点数之和为r，两颗骰子的点数有多少种搭配方式？解：每个骰子是不同的，但讨论点数之和的时候不考虑顺序，故该问题是组合问题。设有满足条件的搭配方式有ra种，则其普通母函数为262()()fxxxx其中rx的系数ra即为所求的搭配方式数。4.14求由数字2，3，4，5，6，7组成的r位数中，3和5都出现偶数次，2和4至少出现一次的r位数的个数。解：这是一个排列问题。设满足条件的r位数的个数为ra，则序列12(,,,,)raaa对应的指数母函数为：24223222()(1...)(...)(1...)2!4!2!2!3!exxxxxxxxf22221()(1)2xxxxeeee=11(6253443322)4!rrrrrrrxr所以，0),2233443526(410,0rrarrrrrr5.2.如果用an表示没有两个0相邻的n位三元序列（即由0，1，2组成的序列）的个数。求an所满足的递归关系并解之。解：对n位三元序列的第一位数有三种选择方式:1)第一位选1，则在剩下的n-1位数中无两个0相邻的个数为an-1;2)第一位选2，则在剩下的n-1位数中无两个0相邻的个数为an-1;3)第一位选0,则在第二位又有两种选择方式：(1)第二位选1，则在剩下的n-2位数中无两个0相邻的个数为an-2；(2)第二位选2，则在剩下的n-2位数中无两个0相邻的个数为an-2显然有a1=3,a2=8∴由加法规则得an所满足的递归关系为：8,3)3(222121aanaaannn其特征方程为x2-2x-2=0∴特征根为x1=1+3,x2=1-3由定理5.3知其通解为an=c1(1+3)n+c2(1-3)n由初始条件有8)31()31(3)31()31(222121cccc解以上方程组得63231c，63232c∴