组合数学 第四版 (Richard A[1]Brualdi 著) 机械工业出版社作业答案

第二章作业答案7.证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。证明用100分别除这52个整数，得到的余数必为0,1,…,99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则ba能被100整除。若a和b被100除余数之和是100，则ba能被100整除。11.一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。证明设从第一天到第i天她共学习了小时。因为她每天至少学习1小时，所以和ia133721,,,aaa,,13,133721aaa37都是严格单调递增序列。因为总的学习时间不超过60小时，所以60a，731337a。,是1和73之间的74个整数，由鸽巢原理知道，它们中存在相同的整数，有和使得3721,,,aaa13,37a13ja,13,1321aaia13jiaa，13jaia，从第1j天到第i天她恰好学习了13小时。14.一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？解由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。17.证明：在一群个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。1n证明因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到的整数。若有两个人的熟人的数目分别是0和1n1n，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n个人的熟人的数目是1n个整数之一，必有两个人有相同数目的熟人。第三章作业答案6.有多少使下列性质同时成立的大于5400的整数？(a)各位数字互异。(b)数字2和7不出现。解因为只能出现数字0,1,3,4,5,6,8,9，所以整数的位数至多为8。①考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P个。②考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P个。③考虑6位整数。最高位不能为0，因此8位整数有)5,7(7P个。④考虑5位整数。最高位不能为0，因此8位整数有)4,7(7P个。⑤考虑4位整数。若千位数字大于5，有)3,7(3P个。若千位数字等于5，则百位数字必须大于等于4，有个。)2,6(4P根据加法原理，符合条件的整数的个数为94830)2,6(4)3,7(3)4,7(7)5,7(7)6,7(7)7,7(7PPPPPP8.15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右侧，又有多少种围坐方式？解15人围坐一个圆桌，有种围坐方式。若B固定坐在A的左侧，则可将!14BA看作一个整体，有种围坐方式。若B固定坐在A的右侧，则可将看作一个整体，有种围坐方式。因此，B不挨着A坐的围坐方式有!13AB1312!13!!132!14种，B不坐在A的右侧的围坐方式有种。!13!13!141311.从15个球员的集合中选人组成11个球员的足球队，其中5人只能踢后卫，8人只能踢边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。解设甲和乙既能踢后卫又能踢边卫。若甲和乙均不入选，组队方法数为。7845若甲和乙均入选，组队方法数为++。782568355845若甲入选且乙不入选，组队方法数为+。78356845若乙入选且甲不入选，组队方法数也为+。78356845因此，组队方法数总共为7845++++=112078256835584545683578221.一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行16个街区去上班。(a)对他来说可能有多少不同的路线？(b)如果在他家以东4个街区、以北3个街区开始向东方向的街区在水下（而他又不会游泳），则有多少条不同的路线？解(a)用E表示向东步行1个街区，用N表示向北步行1个街区。因为该秘书需要向东步行9个街区，向北步行7个街区，总共步行16个街区，因此他的上班路线是多重集的排列。这样的排列的个数为}7,9{NE!7!9!1611440。(b)若他从水下的街区走过，则他先要走到离家以东4个街区、以北3个街区的地方，再向东走一个街区，最后走到工作的大楼。他从家走到离家以东4个街区、以北3个街区的地方的路线的数目是多重集的排列数，即}3,4{NE!3!4!735。他从离家以东5个街区、以北3个街区的地方走到工作的大楼的路线的数目是多重集}4,4{NE的排列数，即!4!4!870。所以，如果他从水下的街区走过，则他可能有的路线数是。因此，如果他不从水下的街区走过，则他可能有的路线数是114402450703589902450。26.确定多重集}5,4,3{cbaS的10-排列的个数。解S的有1个a，4个b，5个c的10-排列的个数为1260!5!4!1!10。S的有3个a，2个b，5个c的10-排列的个数为2520!5!2!3!10。S的有3个a，4个b，3个c的10-排列的个数为4200!3!4!3!10。S的有2个a，3个b，5个c的10-排列的个数为2520!5!2!3!10。S的有2个a，4个b，4个c的10-排列的个数为3150!4!4!2!10。S的有3个a3个b4个c的10-排列的个数为4200!3!4!3!10。S的10-排列的个数为17850315042002252021260。31.方程有多少满足，，304321xxxx21x02x53x，的整数解？84x解进行变量代换：211xy，22xy，533xy，844xy则方程变为254321yyyy原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为3276!32627283282528251425第五章作业答案8.用二项式定理证明knnkknkn3)1(20证明由二项式定理知道nkkknnyxknyx0)(令，得3x1ynkknknkkknnnknkn003)1()1(3))1(3(218.求和nnnnnnn11)1(3412311211解法1对任意非负整数n和k，，即knnknk)1(11)1(knkknn111111，因此，nnnnnnn11)1(3412311211111001)1(11111)1(1)1(nkknkknkkknnknnknk11110111)1(111)1(111011nnnknnknnnkknkk解法2由二项式定理知道nkkknxknx0)1()1(两边分别求积分得111)01(1)11()1(1110nnndxxnnnnkknkkkknkdxxkn01001)1()1(所以1111)1(3412311211nnnnnnnn20.求整数a，b和c，使得对所有的m1233mcmbmam求级数的和。3333321n解令，，因为，所以。1m11213113cba021311c令，，因为，所以2m12223223cba032628cb。令，，所以3m13233333cba63327cba。nmnmnmnmmmmmn000033333126363212142621316416nnnnn4)1(2)1(!4)1()1)(2(622nnnnnnnn25．应用组合学论证方法，证明二项式系数的Vandermonde卷积：对所有的正整数，和n，1m2mnmmknmkmnk21021作为特殊情形，推导恒等式（5-11）。证明设，，BASBA1||mA，2||mB，则21||mmS。我们可以从集合A中取出k个元素，再从集合B中取出kn个元素，把它们合起来构成S的有n个元素的子集。因为A的有k个元素的子集有个，因为B的有个元素的子集有个，所以S的有n个元素的子集个数为。km1m1nnxx2121141(nxknnm2133)2(nknm221(xxxx322x322xx33231xxxxnkkkmnm02nnxx4343243222)1nnnnxxx37.在的展开式中的系数是什么？943)22xx2433231xxxx解由多项式定理知道nnnnnnnnnnnxx4321432141)(令为，为，为，n为9，得到2x3x32x4x42x94321941432149)2(nnnnnnnnnxx因此，的系数是24!39)2(2)1(213392340320!2!1!3)8(!42.用牛顿二项式定理近似计算。3/110解3/13/1)25.01(2)28(3/110)16416135323116121323141311(2412031kkkkk4431k1547.2)6416135323116121323141311(2103/1第六章作业答案3.求出从1到10000既不是完全平方数