组合数学作业答案解析

1、第二章作业答案7.证明，对任意给定的 52个整数，存在两个整数，要么两者的和能被 100整除，要么两者 的差能被100整除。证明 用100分别除这52个整数，得到白余数必为 0,1，99这100个数之一。将余数 是0的数分为一组，余数是 1和99的数分为一组，余数是 49和51的数分为一组，将 余数是50的数分为一组。这样，将这 52个整数分成了 51组。由鸽巢原理知道，存在两个 整数分在了同一组， 设它们是a和b。若a和b被100除余数相同，则a-b能被100整除。若a和b被100除余数之和是100,则a +b能被100整除。11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要

2、不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间(不过，每天都是整数个小时)，都存在连续的若干天，在此期间她恰好学习了13小时。证明 设从第一天到第i天她共学习了 ai小时。因为她每天至少学习1小时，所以a1,a2,，a37和a1+13,a2 +13,，a37 +13都是严格单调递增序列。因为总的学习时间 不 超 过 60 小 时， 所 以 a37 - 60 , a37 +13M73 。 a1,a21L ,a37 , a1 +13,a2 +13,，a37 +13是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有ai和aj +13使得ai

3、 =aj+13, ai -aj =13,从第j十1天到第i天她恰好 学习了 13小时。14. 一只袋子装了 100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子 里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？解 由加强形式的鸽巢原理知道，如果从袋子中取出4M (12-1)+1=45个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要 45分钟。17.证明：在一群n1个人中，存在两个人，他们在这群人中有相同数目的熟人(假设没 有人与他/她自己是熟人)。证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到n-1的整数。若有两个人的熟

4、人的数目分别是0和n -1,则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n个人的熟人的数目是 n-1个整数之一，必有两个人有相同数目的熟人。第三章作业答案6.有多少使下列性质同时成立的大于5400的整数？(a)各位数字互异。(b)数字2和7不出现。解 因为只能出现数字 0, 1,3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 考虑8位整数。最高位不能为 0,因此8位整数有7mP(7,7)个。考虑7位整数。最高位不能为0,因此8位整数有7mP(7,6)个。考虑6位整数。最高位不能为0,因此8位整数有7mP(7,5)个。考虑5位整数。最高位不能为0,因此8位整数有7mP(

5、7,4)个。 考虑4位整数。若千位数字大于 5,有3mP(7,3)个。若千位数字等于 5,则百位数字必须大于等于4,有4mP(6,2)个。根据加法原理，符合条件的整数的个数为7 P(7,7) 7 P(7,6) 7 P(7,5) 7 P(7,4) 3 P(7,3) 4 P(6,2) =948308. 15人围坐一个圆桌。如果 B拒绝挨着 A坐，有多少种围坐方式？如果 B只拒绝坐在 A 的右侧，又有多少种围坐方式？解15人围坐一个圆桌，有14!种围坐方式。若B固定坐在A的左侧，则可将BA看作一个整体，有13!种围坐方式。若 B固定坐在A的右侧，则可将 AB看作一个整体，有13!种围坐方式。因此，

6、B不挨着 A坐的围坐方式有14!-2M13! = 12M13!种，B不坐在A的右侧的围坐方式有14!13! = 13M13!种。11.从15个球员的集合中选人组成 11个球员的足球队，其中 5人只能踢后卫，8人只能踢 边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。解 设甲和乙既能踢后卫又能踢边卫。若甲和乙均不入选，组队方法数为若甲和乙均入选，组队方法数为若甲入选且乙不入选，组队方法数为若乙入选且甲不入选，组队方法数也为因此，组队方法数总共为8、年、，85、8)5、15、8丫518丫5K，什 + + + ri I l+2x+1 =11200 1

7、6八3)日 16 A4力21. 一位秘书在距离家以东 9个街区、以北 7个街区的一座大楼里工作。每天他都要步行16个街区去上班。(a)对他来说可能有多少不同的路线？(b)如果在他家以东 4个街区、以北3个街区开始向东方向的街区在水下(而他又不会游泳)，则有多少条不同的路线？解(a)用E表示向东步行1个街区，用N表示向北步行1个街区。因为该秘书需要向东步行9个街区，向北步行 7个街区，总共步行 16个街区，因此他的上班路线是多重集9E, 7N的排列。这样的排列的个数为二生=11440。9! 7!(b)若他从水下的街区走过，则他先要走到离家以东4个街区、以北 3个街区的地方，再向东走一个街区，最后

8、走到工作的大楼。他从家走到离家以东 4个街区、以北3个街区的地方的路线的数目是多重集 4*E, 3,N的排列数，即 色-=35。他从离家以东5个街区、4!3!以北3个街区的地方走到工作的大楼的路线的数目是多重集4，E,4,N的排列数，即35M 70= 2450。因8!11440-2450 = 8990。二一=70。所以，如果他从水下的街区走过，则他可能有的路线数是 4! 4!此，如果他不从水下的街区走过，则他可能有的路线数是26.确定多重集S=3*a,4 *b,5c的10-排列J的个数。10!解 S的有1个a , 4个b, 5个c的10-排列的个数为 =1260。1!4!5!10!S的有3个a

9、 , 2个b, 5个c的10-排列的个数为 =2520。3!2!5!10!S的有3个a , 4个b , 3个c的10-排列的个数为 =4200。3!4!3!S的有2个a,. 一，10!3个b, 5个c的10-排列的个数为 = 2520。3!2!5!10!S的有2个a, 4个b, 4个c的10-排列的个数为 = 3150。2! 4! 4!S的有3个a 3个b 4个c的10-排列的个数为10!=4200 。3!4!3!S 的 10-排歹 U 的个数为 1260+2x2520 + 2x4200 + 3150 = 17850。31.方程 x1 +x2 +x3 + x4 =30 有多少满足 x1 2 ,

10、 x2 0 , x3 -5 , x4 之 8 的整数解?解进行变量代换:y1=x12,y2=x2,y3=x3+5, y4=x48则方程变为% y2 y3 y4 =25新方程的非负整数解的个数为原方程满足条件的解的个数等于新方程的非负整数解的个数。攵5+4-3自8、252805.J 28 27 263!= 3276第五章作业答案8.用二项式定理证明n、 !3n*n2n = (-1)kk 二0证明由二项式定理知道n(x y)n 八k=0n xn-kyk2n ! Bn*n2n =(3 (-1)n =k =0fn inBn4(-1)k = (-1)k&18.求和1-12 113 413J(-1)nn+

11、11nj解法1对任意非负整数 n和k, (k +1)n +1 +1=(n 1)n+11k+1,k + 1&因此,1-1(-1)nn+1 W=k =0(-1)k gk+1、k=k T0(-1)kn 1(-1)kk 1(k+1n 1KF1尸,n +1 n 1，(-1)kk=01 c 1二0 解法2由二项式定理知道n(1-x)n =(-1)kk=0两边分别求积分得1 n0(1-x)ndx(1-1)n 1.(1-0)n 1所以1-20jxkdx=工(-1)k =0k+1 1J 3(2 ) 4 (-1)20.求整数a, b和c,使得对所有的 mm3 =aim bim c3 2求级数的和13 +23 +3

12、3 +n3o解令m=1,13 = a因为232、因为333、+b3-31所以n+1lnJ=0,所以 c = 1。=0,所以 b = 82c = 6。a = 27 3b3c = 6。1323 33n3二6、m =0mH 3m=0 Lm=0-1二66(n 2)(n 1)n(n -1) (n 1)n n2(n 1)2， 1 ， ，4!25.应用组合学论证方法，证明二项式系数的Vandermonde 卷积:对所有的正整数m, m2和n,mim1 m2k=01k J作为特殊情形，推导恒等式（5-11)。证明 设 S = A，jB, Ac B =0 , | A| = m1，| B | = m2 ,则 |

13、S | = m1 + m2。我们可以从集合 A中取出k个元素，再从集合 B中取出n-k个元素，把它们合起来构成 S的有n个元素的子集。因为 A的有k个元素的子集有fm1 1个，因为B的有n-k个元素的 k子集有m2个，所以S的有n个元素的子集个数为m2mlm2k=ok 八n-k37.在（玉-x2+2x3 -2x4）9的展开式中乂3乂3乂2的系数是什么?解由多项式定理知道(& =2 =3x4)nn1 -n2 -n3 -n4 =nln1 n2 n3 n4 Jn1 n2 n3 n4x1 x2 x3 x4令 x2为-x2 , x3为 2x3, x4为-2x4 , n 为 9,得到9(x1 -x2 2x

14、3 -2x4)n1加2 4n3 4 9Q n1 n2 n3 n4 /x；1(-1)n2xn22n3x；3(-2)n4x；4因此，x13 x3 x3 x2的系数是3312x(-1)3x 2x(-2)9! (-8)(8) = -403203! 3! 1! 2!42.用牛顿二项式定理近似计算101/3解101/3 =(8 2)1/3 =2(1 0.25)1/3=2、k =0T=2 乂(1 &4k112 1.1.12 5 134 332 16 3336 64 k=4小*3k1/311121112511、10:2 (1 1 , )； 2.15473 4 3 32163 33664第六章作业答案3.求出从

15、1到10000既不是完全平方数也不是完全立方数的整数个数。解 设S是从1到10000的整数的集合，A1是从1到10000的完全平方数的集合，A2是从21到10000的完全立万数的集合。因为1002 =10000 ,所以1Al | = 100。因为213 =9261 10000 10648=223,所以|A2 | = 21。因为一个整数既是完全平方数也是完全立方数的充分必要条件是它是完全六次方数，46 = 4096 10000 15625 = 56 ,所以| A1 c A2 | =4。从1到10000既不是完全平方数也不是完全立方数的整数个数1Al - A21fs | -(| A111A2 |)

16、 1Al - A2 | =10000 -(100 21) 4 =98836.面包店出售巧克力的、肉桂的和素的炸面包圈，并在一特定时刻有6个巧克力、6个肉桂和3个素炸面包圈。如果一个盒子装12个面包圈，那么可能有多少种不同的盒装面包圈组合？解 用a, b, c分别表示巧克力的、肉桂的和素的炸面包圈。本题要求的是多重集 _ _ _ _ _ 一一一.一 一 一 一一 . . . * - - - T = 6,a , 6b, 3,c的12-组合的个数。设 S为T =00a,00b,00c的所有12-，心小人12+31、 114、* 一 ,、,人组合的集合，则|S|=91。设人1为丁的所有至少有7个a的1

17、2-组合 121 1的集合，庆2为丁*的所有至少有7个b的12-组合的集合，人3为丁*的所有至少有4个c的12-组合的集合。每个 T*的5-组合再加上7个a就得到一个至少有 7个a的12-组合，所以T 的至少有 7个a的一 * 一一. 一 - . 一一12-组合的个数等于T 的5-组合的个数，5+3-1 55 j=2 1同样可得到5+3-1巾=211 5 1(8+3-1 110 !*|A3|=1=45。T的至少有 7个a和7个b的12-组合的个数8.-. . . .士 . 一.|A1cA2|=0, T的至少有7个a和4个c的12-组合的个数|A1cA3| = 3, T的至少有7个b和4个c的1

18、2-组合的个数| A2cA3 | =3 , T的至少有7个a、7个b和4个c的12-组合的个数|A1cA2cA3| = 0。因此，T的12-组合的个数1Al - A2 - A31= |S| -(| Ai | | A2 11A3 |) | Ai - A? | | A 一 A3 11A2 - A3 | - 一 A2 - A3 | =91 -(21 21 45) 0 3 3 -0 -109.确定方程x1 x2 x3 x4 : 20满足1 Ex1M6, 0 x2 7 , 4 x3 8 , 2 x4 6的整数解的个数。解引入新变量y1 二 6 - x1 y2 = 7 - x2y3 = 8 - x3 y4

19、=6 - x 4则方程x1 x2 x3 x4 = 20满足1 Ex1M6, 0 x2 7 , 4 x3 8 , 2 x4 6的整数解的个数等于方程y1 y2 y3 y4 =7满足0 y1 5 , 0、2工7,0 y3 4 , 0Ey4 M4的整数解的个数。设S是方程y1十y2+y3 + y4 = 7的所有非负整数解的集合，则=7的所有满足7 十 4-1、0、|S|=1=1 1=120。设 A1 为方程 y1+y2+y3+y417) 77)非负整数解的集合，a2为方程y1 + y2 + y3 + y4 = 7的所有满足y2 8的非负整数解的集合，A3为方程y1 +y2 +y3 +y4 =7的所有

20、满足y3之5的非负整数解的集合， A4为方程w +y2 +y3 +y4=7的所有满足y4之5的非负整数解的集合，则| a | =4,| A21=0,口3|”| 二2 4-12= 10。若i j ,则Aj c Aj =0。因此，方程yi y2y3y4 =7满足0 y1 5, 0 y2 7 , 0y3 4, 0 y4 1)ho = 1解 对应齐次递推关系的特征方程为x-4=0,它的特征根为4。设该非齐次递推关系的特解为 p2n,则 p2n =4p2n+3x2n,因而 p=2p+3,因此 p =-3 o该非齐次递推关系的一般解为hn = c4n -3父2n。令 n=0,得 c3 = 1,解得 c =

21、 4。因此，hn =4n+1 -32no26.求解非齐次递推关系hn =4hn/+4n ( n 1)ho = 3解法一 对应齐次递推关系的特征方程为 x-4 = 0,它的特征根为4。设该非齐次递推关系 的特解为pn4n,则pn4n =4父p(n1)M4n +4n,解得p=1。该非齐次递推关系的一 般解为 hn =c4n +4nn。令 n = 0,得 c = 3。因此，hn =(n + 3)M4n。QO解法二 该序列的生成函数g(x) = hnxnon =0 TOC o 1-5 h z QOoOQO(1 -4x)g(x) = (1 -4x)2： hnxn =、. hnxn二.4hnxn 1n -

22、0n -0n -0oOQOoO= h.二 hnxn - % 4% _1xn = h0，.二(hn -4hn_1)xn n 1n 口n =1=h0 八 4nxn =3 八 4nxn = 2 4n xn = 2 -0,c1-4x2g(x)二 一n 4n 1n =0 x1 -4x = 2 .11 -4x1 -4x (1 -4x)2odoooo=2、4nxn v (n 1)4nxn =，(n 3)4nxnn =0n 4n =0因此，hn=(n+3)x4n。30.确定苹果、桔子、香蕉和梨的袋装水果的袋数hn的生成函数，其中各袋要有偶数个苹果，最多两个桔子,解生成函数3的倍数个香蕉，最多一个梨。然后从该生

23、成函数求出hn的公式。00Q0g(x) x2n)(1 x x2)，x3n)(1 x)n =0n =0ad=% (n 1)xnn =0(1 x x2)(1 x) 1(1 -x2)(1 -x3)(1 -x)2因此，hn = n +1。32.令 h0,h1，h2,，hn，是由 hn定义的序列（n之0）。确定该序列的生成函数。Q0、xnn h011 -x两边求导数得到、. nxn-1n =01(1-x)2两边再求导数得到QOn(n -1)xn-2n =02(1 -x)3两边乘2 x 。得到2Jnnzlxn 2 n =02x2(1-x)3因此，该序列的生成函数g(x)八 4xn n =0QO二zn =0

24、n 1 n xn8nxn2n =02x2(1-x)3八n32.令h0,h1,h2，hn,是由hn =定义的序列（n之0）。确定该序列的指数生成函1no解该序列的指数生成函数g (x)二:,hnn -0 xnn!QO=n -0vnn =2xnn!n!xn1 二 xn1 二 xn 2x2 二 xnx2ex=Z = - / = / = Z =n=22!(n-2)!n!2口/5一2)!2口与川2nn! 241.确定所有的数字至少是 4的n位数的个数，其中 4和6每个都出现偶数次，5和7每个 至少出现1次，但对于数字8和9则没有限制。解 设hn为满足条件的n位数的个数，序列h0 ,%,h2 ,的指数生成

25、函数是 TOC o 1-5 h z 24232xx x 、， x , 9gx)=(1 )2(x)2(1 x)2xx 2(e e)(ex -1)2e2x42!4!2!3!2!(e2x 2 e2x)(e2x -2ex 1)e2x4_ e6x 2e5x 3e4x 4e3x 3e2x 2ex 1一4n nn nn n ：: on n o ：: on nn1 % 6 x1 x 5 x3 % 4 x% 3 x3 % 2 x1 x x1oO=n T4n=0 n!2n=0 n!4n=0 n!nW n!4n=0 n!2n=0n!46n -2 5n 3 4n -4 3n 3 2n -2 xnn!0因此，hn -1)S(n,2) =2n1 -1, (n -2)(c)S(n, n T)=(n-1)(d)证明(a)设n之1,因为将