《组合数学》测试题含标准答案

1、组合数学测试题含答案 作者:日期:测试题组合数学一、选择题把101本书分给10名学生，则下列说法正确的是（）A.有一名学生分得11本书B.至少有一名学生分得11本书C.至多有一名学生分得11本书D.有一名学生分得至少11本书8人排队上车，其中A，B两人之间恰好有4人，则不同的排列方法是（）A.3x6!b.4x6!C.6x6!d.8x6!10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）A.10!xP（11,4）b.10!xP（9,4）C.10!xP（10,4）D.14!3!把10个人分成两组，每组5人，共有多少种方法（）10、10丫10A.5丿B.（5人5丿C.D.C

2、.设x,y均为正整数且x+yoA.89B.110C.144D.288递推关系a=3a-4a的特征方程是()nn-1n-3A.x2-3x+4=0B.x2+3x-4=0C.x3-3x2+4=0D.x3+3x2-4=016.已知a=2+3x2n(n=0,1,2,)，则当n2时，annA.3a+2an-1n-2B.3a一2aA.3a+2an-1n-2B.3a一2an-1n-2C.3a+2an-1n-2D.3a2an-1n一217.递推关系a=2a+2n(n1)na=30n-1的解为（）A.a=nx2n+3nB.a=(n+1)x2n+2nC.a=(n+2)x2n+1nD.a=(n+3)x2nD.5D.5

3、(-2x上18.设a=5x2n（n=0,1,2,），则数列匕的常生成函数是（）nnn0C.5(1-2x)把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（）种A.45B.36C.28D.20多重集S=b-a,4-b的5-排列数为（）TOC o 1-5 h zA.5B.10C.15D.20部分数为3且没有等于1的部分的15-分拆的个数为（）A.10/B.11C.12D.13设n,k都是正整数，以PO表示部分数为k的n-分拆的个数，则PG1）的值是（）k6A.6B.7A.6B.7C.8D.923.设A，B，C23.设A，B，C是实数且对任意正整数n都有n3rn)rnA-+B-

4、13丿0A.a=7n+6n+5nnB.a=7n6n+5nnC.a=7n+2x6n+5nD.a=7n2x6n+5nnn则该数列的通项公式是（）二、填空题TOC o 1-5 h z在1和2000之间能被6整除但不能被15整除的正整数共有个用红、黄、蓝、黑4种颜色去图lxn棋盘，每个方格涂一种颜色，则使得被涂成红色的方格数是奇数的涂色方法共有种已知递归推关系a二3a+4a-12a（n3）的一个特征根为2,则其通解为nn-1n-2n-3把n（n3）个人分到3个不同的房间，每个房间至少1人的分法数为xxx棋盘的车多项式为xxxx6.由5个字母a,b,c,d,e作成的6次齐次式最多可以有个不同类的项。7.

5、(-7.(-Jk2k=0求由2个0，3个1和3个2作成的八位数的个数9含3个变元x,y,z的一个对称多项式包含9个项，其中4项包含x,2项包含xyz,1项是常数项，则包含xy的项数为的3次多项式且的3次多项式且f）=111.已g（n,k）表示把n元集划分成k个元素个数均不小于2的子集的不同方法数，则gC,2）=12部分数为3且没有等于k的部分的n-分拆数13.把24颗糖分成5堆，每堆至少有3颗糖，则有种分法三、计算题1、在1000至9999之间有多少个数字不同的奇数？2、以3种不同的长度，8种不同的颜色和4种不同的直径生产粉笔，试问总共有多少种不同种类的粉笔？3、至多使用4位数字可以写成多少个

6、2进制数！（2进制数只能用符号0或1）4、由字母表L=a,b,c,d,e中字母组成的不同字母且长度为4的字符串有多少个？如果允许字母重复出现，则由L中字母组成的长度为3的字符串有多少个？5、从1，2，39中选取不同的数字且使5和6不相邻的7位数有多少？6、已知平面上任3点不共线的25个点，它们能确定多少条直线？能确定多少个三角形？7、计算数字为1，2，3,4，5且满足以下两个性质的4位数的个数：（a）数字全不相同；（b）数为偶数8、正整数7715785有多少个不同的正因子（1除外）？9、50!中有多少个0在结尾处？10、比5400大并且只有下列性质的数有多少？（a）数字全不相同；（b）不出现数

7、字2和711、将m=3761写成阶乘和的形式。12、根据序数生成的排列（p）=（3214），其序号是多少？13如果用序数法对5个文字排列编号，则序号为117的排列是多少？设中介数序列为（120）,向它所对应的4个文字的全排列是什么？按字典序给出所有3个文字的全排列。按递归生成算法，依次写出所有的4个文字的全排列。根据邻位互换生成算法,4个文字的排列4231的下一个排列是什不同的方案?有5件不同的工作任务，由4个人去完成它们，每件工作只能由一个人完成，问有多少种方式完成所有这5件工作？有纪念章4枚，纪念册6本，分送给十位同学，问有多少种分法？如限制每人得一件物品，则又有多少种分法？写出按次序产生

8、的所有从1，2，3,4，5，6中任取2个的组合。给定一个n边形，能画出多少个三角形使得三角形的顶点为n边形的顶点，三角形的边为n边形的对角线（不是边）？试问（x+y+z）的6次方中有多少不同的项？如果没有两个相邻的数在同一个集合里，由1，2,20中的数可形成3个数的集合有多少？试列出重集2a,1b,3c的所有3组合和4组合。设Fn为fibonna序列，求出使Fn=n的所有的n。试求从1到1000中,不能被4,5或6整除的个数?.计算12+22+n2设某地的街道把城市分割成矩形方格，每个方格叫它块，某甲从家里出发上班，向东要走过7块，向北要走过5块，问某甲上班的路经有多少条？设n=2532731

9、14,试求能除尽数n的正整数的数目。求(l+X4+X8)10中X20项的系数。试给出3个文字的对称群S中的所有元素，并说出各个元素的格式。3有一BIBD，已知b=14,k=3,入=2，求v和r。将39写成Eai!(0ai)的形式。34.8个人围坐一圈，问有多少种不同的坐法？求C(10,1)+2C(10,2)+3C(10,3)+10C(10,10)试给出两个正交的7阶拉丁方。在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。用红、黄两种颜色为一个等边三角形的三个顶点着色，问有多少种实质不同的着色方案？在r,s,t,u,v,w,x,y,z的排列中，求y居x和z中间的排列数。求10

10、40。和2030的公因数数目。求1到1000中不被5和7整除，但被3整除的数的数目。求14+24+34+n4的和。用母函数法求递推关系a-6a+8a=0的解，已知a=0,a=1。nn-1n-201试求由a,b,c这3个文字组成的n位符号串中不出现aa图像的符号串的数目。45.26个英文小写字母进行排列，要求x和y之间有5个字母的排列数。46.8个盒子排成一列，5个有标志的球放到盒子里，每个盒子最多放一个球，要求空盒不相邻，问有多少种排列方案？47有红、黄、蓝、白球各两个，绿、紫、黑球各3个，从中取出6个球，试问有多少种不同的取法。48用b、r、g这三种颜色的5颗珠子镶成的圆环，共有几种不同的方

11、案？49.n个完全一样的球放到r(n三r)个有标志的盒中，无一空盒，试问有多少种万案？50假设某个凸n边形的任意三条对角线不共点，试求这凸n边形的对角线交于多少个点？求S=1x2x3+2x3x4+n(n+1)(n+2)从艮个不同文字中取n个文字作n允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。求下图中从A点出发到n点的路径数。n条直线将平面分成多少个区域？假设无三线共点，且两两相交。四位十进制数abcd，试求满足a+b+c+d=31的数的数目。两名教师分别对6名学生面试，每位教师各负责一门课，每名学生面试时间固定，6名学生面试时间定于下周一的第1节至第6节课，两门课的面试分

12、别在901和902两个教室进行。试问共有多少种面试的顺序。对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转或翻转使之重合的视为相同的方案。生成矩阵(10001010100111G=001011010001011J试求相应的校验矩阵H。由m个0，n个1组成的n+m位符号串，其中nWm+1,试求不存在两个1相邻的符号串的数目。n个男人与n个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数，又m个女人n个男人，且mn，沿一圆桌坐下求无两个女人并坐的方案数。求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目。62求满足下列条件：x+x+x=40,6x15,5x20

13、,10 x3Jnn-1n-2n-3a0=0,ai=1,a2=2求下列递推关系的特解an一3an-1+2an-2=279.1）求小于10000的含1的正整数的个数2）求小于10000的含0的正整数的个数。在100名选手之间进行淘汰赛（即一场的比赛结果，失败者退出比赛）,最后产生一名冠军，问要举行几场比赛？计算1,n的无重不相邻组合C（n，r）的计数问题某保密装置须同时使用若干把不同的钥匙才能打开。现有7人，每人持若干钥匙。须4人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少点？又把所有对角线分割成多少段？在

14、5个0,4个1组成的字符串中，出现01或10的总次数为4的，有多少个？整数n拆分成1,2,3,，m的和，并允许重复，求其母函数。某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每二人各相遇3次，每五人各相遇2次，每六人各相遇1次，1人也没有遇见的有5次，问某甲共参加了几次会议？给出下列等式的组合意义：n-m仝(-Jm、n-广,nkmn-k丿1=0J丿&J(a)m+广m+广m+1+m丿jm+1m+2丿88.将正整数10写成3个非负整数n,n,n的和，要求n3,n4,n的母函数。有多少棵有n个顶点的二叉数？求下式之和1-c(n,1)/2+cn,2)/3+1)n

15、c(n,n)/n+1)97展开多项式(x+x+x1123六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。试求n个完全一样的骰子掷出多少种不同的方案？写出全部部分数最小的19-完备分拆已知f(n)=2n+(-，求Akf()求方程x1+2x2+4x3二17的非负整数解的个数。四、证明题证明：1,2,n的全排列的最大逆序数是n(n-l)/2。试确定具有n(n-l)/2个逆序的唯一排列。证n乙-1，r)=+】)乙,r+J并给出组合意义.n个完全一样的球，放到r个有标志的盒子，n三r，要求无一空盒，试证其方案数为cCn-1，r-.试证一整数是另一个整数的平方的必

16、要条件是除尽它的数目为奇数.试证明.cGm)+c.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数.试证明.cGm)+c(1,m)+c(n,m)=c(n+1,m+1)证明：(C(n,O)2+(C(n,l)2+-+(C(n,n)2=C(2n,n)证明：若F二F二1,F=F+F(n2)，贝V12nn1n2+語)/2)/2)丿其中a=(l+M5)/2,B=(l-M5)/2N个代表参加会议，试证其中至少有两个人各自的朋友数相等。证明：12+22+n2=n(n+l)2n+1)/610.证明：(2n)/2n是整数。11.证明：在边长为1的等边三角形内任取5点,试证至少有两点的距离小于1/2。12

17、.证明:(12.证明:(111n(FF1n+1nJ0丿LFFJn其中F定义为：F=F=1，F=F+Fn12nn1n2任取11个整数，求证其中至少有两个数它们的差是10的倍数。在边长为1的正方形内任取5点，试证其中至少有两点,其间距离小于2/2o15若H是群G的子群，试证：|xH匸K,其中K=|H|，xG。二维空间的点(x,y)的坐标x和y都是整数的点称为格点。任意5个格点的集合A，试证A中至少存在两个点，它们的中点也是格点。证明：在由字母表0，1，2生成的长度为n的字符串中，0出现偶数次的字符串有(3n+1)/2个。试证任意r个相邻的正整数的连乘积(n+1)(n+2)(n+r)必被r!除尽。1

18、9.证明:c(m,0)c(m,n)+c(m1)c(m1,n1)+cCn,n)c(mn,0)=2nc(m,n)20.证明20.证明c(n,l)+2c(n,2)+nc(n,n)=n2n-1任取5个整数，试求其中必存在3个数，其和能被3整除。若H是群G的子群，x和y是G的元素。试证xHGyH或为空集，或xH=yH.令S=1，2，,n+l,n2,T=紅,z)wS,xz,yz试证：T=12+22+n2=C(n+1,2)+2C(n+1,3)。证明：任何K个相继的正整数之积，必是r的倍数，其中r=1，2，K。25.求证:TOC o 1-5 h z(n+2)=)2n)+)25.求证:n+1n+1nn-126.

19、使用二项式定理证明n=k，试推广到任意实数r，求()k。kkk=0k=027-证明|aubuc=|a|+B+|c|-|anb-|anC-|bnC+|anbncl证明任何k个相继正整数中，有一个必能被k整除。证明在小于或等于2n的任意n+1个不同的正整数中，必有两个是互等的。旳=2L叫I证任一正整数n可唯一地表成如下形式：，0WajWi,i=1,2,。对于给定的正整数n,证明当性为奇数答“为偶数)(、展时，C(n,k)是最大值。32证明在由字母表0,1,2生成的长度为n的字符串中,0出现偶数次的字符串踏+1有？个；33.设有三个7位的二进制数：aaaaaaa，bbbbbbb，ccccccc。12

20、3456712345671234567试证存在整数i和j，1ij7，使得下列之一必定成立，a=a=b=b,a=a=c=c,b=b=c=c。ijijijijijij证明：在n阶幻方中将每个数码a换成n2+1-a，所得的阵列仍是一个n阶幻方。(注：所谓幻方是指一个nxn方阵，其中的元素分别是1,2n2，且每列的元素和均相等)证明：把有n个元素的集合s划分为k个有序集合的个数等于kn试证明：1/G+x二hC1/c(n+k1,k)xk,|x|l)个不同文字取出n个(可以重复)作排列，但不允许一个文字连续出现3次的排列所组成的集合为A,则所求排列数a=|A丨。将A中的字符串按nnnn最后一个文字可以分成

21、两类：一类是最后一个文字同其前一个文字不相同的那些字符串，共有(kl)a个(最后一位有kl种选择，而前nl位是没有一个文l字连续出现3次的字符串)，另一类是最后两个文字相同，但与倒数第3个文字不相同的字符串，共有(kl)a个，所以有递推关系n2TOC o 1-5 h za=(kl)a+(kl)a(nnln2而a=k，a=k2,a=ksk=k(kl)(k+ll23递推关系的特征方程为x2(kl)x(kl)=0其根为：al=(kl+sqrt(kl)(k+3)/2a=(klsqrt(kl)(k+3)/22于是知a=Aan+AanTOC o 1-5 h znll22由于a=k，a=k2，由递推关系知a

22、=k/(kl)，所以l20a=k/(kl)=Aa0+AaoA=A+A0ll22l2a=k=Aai+Aai=A(kl+sqrt(kl)(k+3)/2ll22l+A(klsqrt(kl)(k+3)/22解得A=(k/(2(kl)+k/(2sqrt(kl)(k+3)A=(k/(2(kl)k/(2sqrt(kl)(k+3)2所以a=(k/(2(kl)+k/(2sqrt(kl)(k+3)n(kl+sqrt(kl)(k+3)/2)n+(k/(2(kl)k/(2sqrt(kl)(k+3)(klsqrt(kl)(k+3)/2)nf(n)=(l+V5)/2)n+1(l5)/2)n+i)/5假设从A(编号为0)到

23、编号为i的顶点有f(i)条路径，则f(l)=l,f(2)=2,当i2时，f(i)=f(i-l)+f(i2)，由此知f(0)=f(A)=l。当i=n时，f(n)=f(n-l)+f(n2)，即f(n)f(nT)f(n2)=0。其特征方程为：X2x1=0,它的两个根分别为：a=(l+V5)/2,a=(l5)/2。l2于是知f(n)=Aan+Aan,根据ll22f(0)=l=A+A12f(l)=l=A(l+5)/2+A(l5)/2,12解得A=(l+V5)/(2V5),A=(lV5)/(2V5)12所以，f(n)=(l+V5)/2)n+i(l5)/2)n+i)/5=F(n+1)其中F(n)为第n个Fi

24、bonacci数。a=(n2+n+2)/2n设n条符合条件的直线将平面分成a个区域，那么nl条直线可将平面分成a个区TOC o 1-5 h znnl域，而第n条直线与前n-1条直线均相交，有nl个交点，因此第n条直线被分成n段，而每一段对应一个新增的区域，所以有a=a+n,即aa=n。于是nnlnnlaa=nl,由此得a2a+a=l,同样有a2a+a=l，nln2nnln2nln2n3故得a3a+3aa=0,其特征方程为x33x2+3x1=0,解此方程nnln2n3得a=a=a=a=l,所以a=(A+An+An2)an=A+An+Am，而l23n012012a0=l=A0a=2=A+A+A10

25、12a=4=A+2A+4A012解得A=10A=1/21A=1/22由此知a=(m+n+2)/2nTOC o 1-5 h z56因为x+x+x+x=31,x20(i=l,2,3,4)的整数解共有C(4+31-1,31)1234i=C(34,3)=343332/6=5984(个)。再考虑x+x+x+x=31,x2l0(i=l,2,3,4。的整数解的个数。令N为全1234i体非负整数解，贝J|N|=5984O令Ai(i=l,2,3,4)为其中xi2l0的解集合。贝贝IA|即为(x1+10)+x2+x3+x=31，也就是x+x+x+x=21的非负整数解的个数。所以，41234|A|=C(4+21l,

26、21)=C(24,3)=242322/6=2024。同理可知IA|=|A|=|A|=|A|=2024。类似地，2341|AnA|=C(4+11l,11)=C(14,3)=141312/6=364(lWijW4),ij|AnAnA|=C(4+1l,1)=C(4,1)=4(lWijkW4),而ijk|AnAnAnA|=0。TOC o 1-5 h zl234根据容斥原理，a+b+c+d=31,0Wa,b,c,dW9的整数解个数等于|AnAnAnA|=l234|N|4|A|+C(4,2)|AnA|C(4,3)|AnAnA|+ll2l23|AnAnAnA|l234=598442024+636444+0=

27、56190800假设6个学生参加第l位教师的面试的顺序为l、2、3、4、5、6(即对第l个面试的学生编号l,.,对第6个面试的学生编号6),那么，这6个学生参加第2位教师的面试的顺序必定是l、2、3、4、5、6的一个错排。不然，就有至少一个学生要同时参加两为教师的面试。于是面试方案总数为6!D=6!6!(11+1/2!1/3!+1/4!1/5!+1/6!)=6!256=19080061505对应于旋转与翻转的运动群的置换为：p1(不动)(1)(2)(3)(4)(5)(6)格式为(l)6p（逆时针旋转60）2(123456)二?壬格式为（6）1p3（逆时针旋转120）(135)(246)格式为（

28、3）2p（逆时针旋转180）4(14)(25)(36)格式为（2）3p（逆时针旋转240）(153)(264)格式为（3）2p（逆时针旋转300）6(654321)格式为（6）1p7（沿14轴翻转）(1)(4)(26)(35)格式为（1）2（2）2p8（沿25轴翻转）(2)(5)(13)(46)格式为（1）2（2）2p9（沿36轴翻转）(3)(6)(15)(24)格式为（1）2（2）2p（沿12边54边中线翻转）10(12)(36)(45)格式为（2）3卩（沿23边56边中线翻转）(14)(23)(56)格式为（2）3p（沿16边34边中线翻转）12(16)(25)(34)格式为（2）3所以，

29、总方案数为l=(5e+25i+252+453+354)/12=18060/12=150558.i1110100H=01110101101001丿3x7因为i10001010100111=(!IA)G=001011034x30001011丿4x7而1110At=0111i1101J343x411)11)33x7C(m+l,n)将m个0排成一行，两个0之间有一间隔，共有m+1（三n）个间隔（包括头尾处的间隔）。在此m+1个间隔中任取n个插入1,则所得符号串满足要求，所以共有C（m+1,n）个这样的符号串。（n1）!n!,（n1）!n!/（nm）!先让n个男人围坐一圈，共有（n1）!种坐法。对应于每

30、一种坐法，有n个间隔,将n个女人排成一行插入这n个间隔中，有n!种方案，所以共有（n1）!n!种不同的坐法。若只有m（my1+y2+y3=19当丫产10时的非负整数解集合，贝川A=C(3+9-1,9)=C(11,2)=1110/2=55,令A是y+y+y=19当y216时的非负整数解集合，贝川A|=C(3+3-1,3)=C(5,2)TOC o 1-5 h z12322=54/2=10,令A是y+y+y=19当y216时的非负整数解集合，贝川A|=C(3+3-1,9)=C(5,2)12333=54/2=10,而且IAnA1=1AnA1=1AnA1=0,|AnAnA|=0,根据容斥原理可知，符12

31、2313123合条件的解的个数为IAnAnAI=210-(55+10+10)=210-75=13512330设S=1,2,3,120，若nWS且n为合数，即n=n气，则因为1111=121120,所以气或气中必有一数2,3,5,7。12设A表示S中能被2整除的数，贝9|Aj=int(120/2)=60(int(x)表示不超过x的最大整数)，设码表示S中能被3整除的数，则|A2|=int(120/3)=40,设A：表示S中能被5整除的数，贝川A：|=int(120/5)=24,设I表示S中能被7整除的数，贝川A3|=int(120/7)=17,4而且，|AnAI=20,IAnA|=12,IAnA

32、I=8,121314|AnA1=8,|AnA1=5,|AnA1=3,TOC o 1-5 h z232434|AnAnA|=4,|AnAnA|=2,|AnAnA|=1,|AnAnA|=1,123124134234|AnAnAnA|=o,1234所以，根据容斥原理知，S中既不是2、3、5的倍数，也不是7的倍数的个数共有120-(60+40+24+17)+(20+12+8+8+5+3)(4+2+1+1)+0=176-149=27但是，这27个数中包含了1,它不是素数，却没有包含2、3、5、7,所以，1至120之间的素数共有27-1+4=30个。因为A=(1)(2)(3)(4),(123),(124)

33、,(132),(134),(142),(143),(234),4(243),(12)(34),(13)(24),(14)(23),它共有12个置换，其中格式为(1)4的有1个：(1)(2)(3)(4),格式为(1)1(3)1的有8个:(123),(124),(132),(134),(142),(143),(234),(243),格式为(2)2的有3个：(12)(34),(13)(24),(14)(23)(a)w=(1111)G=(1111111)w=(1000)G=(1000011)2w=(0001)G=(0001111)3w=(1101)G=(1101001)4(n-2)2n-1+1从n个不

34、相同的数a,a,.,a中取出r(r=2,3,.,n)个，将这r个数TOC o 1-5 h z12n从小到大排序：aWaW.Wa。将这r个数分成前后两部分，使每一部分非空,ili2ir共有r-1种分法。前面部分形成第2组，后面部分形成第1组，则第1组中的最小数大于第2组中的最大数。所以满足条件的取法共有EnC(n,r)(r-1)=EnrC(n,r)EnC(n,r)r=2r=2r=2=(EnrC(n,r)-C(n,1)(EnC(n,r)-C(n,1)-C(n,0)r=1r=0=(n2n-1-n)(2n-nT)=(n-2)2n-1+1解根据题设，无论选哪一名，有26种可能结果；余下选一名只有25种可

35、能结果；最后选一名就只有24种可能结果。由于同时选出三名，所以由积的法则知，共有26X25X24=15600种选法。解(1)这100个数的前7个数，任选取两个数的差不可能等于7,只有1007=93种选取方式，才能使这100个数两数之差等于7。(2)同理，选取两数之差等于6的有1006=94种选取方式；等于5的有1005=95；，等于1的有1001=99种。以上两数之差均小于7。故两数的差小于或等于7的选取方式，根据和的法则，共有(94+95+96+97+98+99)+93=672种选取方式。解这是一个多重集5=n红球；m白球的重复排列问题。S的一个排列就是它的m+n个元素的一个全排列，因为S中

36、有n个红球，在排列时要占据n个位置，这些位置的选法是种，接下去，在剩下的(n+m)n=m个位置选择m个位置的选法是Cm,m+nm由积运算法则,S的排列数为N=Cn由积运算法则,S的排列数为N=Cnm+nCm=m(m+n)!n!m!1=，以下化为较简单形式:m!n!(m+n)!=(m+n+n一1)In+m一(n-1)!n!m!nn!m!(n+(n+m)(n1)(m+1)!n!m!(n+m)(+m一1)(m+1)n!这即为所求排列方式数。70.解设分别具备这三种设备的汽车依次为,A2,A3,由题设IaJ=15,|a2I=8,Iana?nA31=3n|aa=Ia.A31=Ia这即为所求排列方式数。7

37、0.解设分别具备这三种设备的汽车依次为,A2,A3,由题设IaJ=15,|a2I=8,Iana?nA31=3n|aa=Ia.A31=Ia_A31=3，于是这二种设备都不具备的汽车，由容斥原理JL厶JJL厶JLJ厶J1213232知为An可nA3=a.ua2ua3=30-|a.ua2ua3I=30-耳A=30-K15+8+6)-(3+3+3)+3=7叫n码1+IA1nA31+IA2nAl)+lAna2na371.解实际上是求奇数1,3,5,7,9这5个数的移位排列数目D(n),由于n=5,所以:(11111、D(5)=5!1-+1!2!引4!5!120l-l+-+24一120丿=120(60-2

38、0+5-1120=4472.解设A1，A2,A3分别为能被3,5,300300=60,|a1=300=42；|anA=300=20,|anA=3005J37J1235J13L37J=100，3=14，=8；IA1nA2nA37整除的集合，则|aJ=-300_57_IA2nA3-300_357_=2。73.(1)由容斥原理2知,不能被3,5,7整除的数的个数为:NI=A1nA2nA3=A1UA2Ua300-Ea+=300-&00+60+42)-(20+14+8)+2=138Ia2I+1a3I)(州na2I+1Ana3I+|a2na(2)能被3整除但不能被5和7整除的数的个数为:n2=IaJIa.

39、naJ-LAnaJ+Ia.na2na3I=1002014+2=68解(1)a0=c0=1，ai=c，C2=c2，ar=宀.f(r)=a0+aix+a2x2+曾+=1+cx+c2x2+crxr+=，其中|cx|3,而当r2时a0r75.解生成函数F(x)=(乂+xLii=0ixi1n(x)=Iixi1n(1ixi1n1()+2()+3()2+n()n-1n(1+x-1TOC o 1-5 h z123n当令X)=1时又为()+2+n人丿n2n-12n76.解令上到第n个台阶的方式数为a，可心分成两类：一类是从第n1阶台阶迈一步n上去的，共有a,种方式；另一类是从第n2阶台阶迈两个台阶上去的，有a种

40、方n1n2式，由于最后一步的上法有一步和二步之分，所以这两类上楼梯方式不同，且a与an-1n-2的各自上法都不同，故a=a+a，为得到初始条件，当n=l时，a=1种显然；nn-1n-21当n=2时，有两种可能方式(一步或二步)，故a2=2，这样，可得递推关系：aa+a,n2Jnn1n2a1,a2l152利用特征方程法：由于为2阶常系数齐次递推关系，所以特征方程x2X+10之特征根X1+W5,X根X1+W5,X=22不同于是通解an=A】X1n+A2X2n，代入初始条件得方程组A1+A2=a0=1小可求出AAx+Axa2111221v5+32斗,A242；52X2X215将xx,A,A代入a即得

41、1,212nTOC o 1-5 h z77.解a一a一9a+9a=0nn-1n-2n-3特征方程x3-x2-9x+9=0特征根X=1,x2=3,x3=-3.通解为a=A1n+A3n+A“123A+A+A=0123代入初始条件得方程组Al1A+3A2-3A=1+32A+(-3代入初始条件得方程组Al1 HYPERLINK l bookmark11 o Current Document 23利用消元法得A145利用消元法得A145a2=-112.现=-4+3-3n一古(-3解先求对应齐次递推关系特征方程的根。特征方程x2-3x+2=0有两相异特征根兀=1,x2=2由于申C)=2n中2是特征方程的m

42、=1重根所以设特解为5p.ni2n=p02n+p1n2n代入原递推关系得2n+p1n2n)-3)2n-1+p(n-1)2n-11292n-2+p故特解为(p0+2n)2n,C0为任意Q解小于10000的不含1的正整数可看做4位数，但0000除外.故有9X9X9X9-1=6560个.含1的有：99996560=3439个不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个不含0小于10000的正整数有9+92+93+94=(959)/(91)=7380个含0小于10000的正整数有99997380=2619个是淘汰的选手与比赛(按场计)集对应。99场比赛解法1:0-010-010

43、-010-010-0共有n位，其中含有r个1且不可含11。以1结尾：r-1个10与n-1-2(r-1)个0的排列rT+nT2(r1)=nr这样的排列有一以0结尾：r个10与n-2r个0的排列4八r+n-2r=n-r这样的排列有广f(aa*a)=bb七TOC o 1-5 h z12r12r解法2:任给aa&WC(n,r),aVaVVa12r12r令f：aa*afbb七12r12rb=a.i+1,i=1,2,，r.1i1WbVbVVbWnr+1,bb七WC(nr+1,r)12r12rC(n,r)=C(nr+1,r)解:每3人至少缺1把钥匙，且每3人所缺钥匙不同。故至少共有l丿=35把不同的钥匙。任

44、一人对于其他6人中的每3人，都至少有1把钥匙与之相配才能开锁。故每人至少持何=20把不同的钥匙。解：根据题意，每4个点可得到两条对角线,1个对角线交点，从10个顶点任取4个的方案有C(10,4)中，即交于210个点。根据图论知识，每个对角线交点有4个度,每个顶点去掉与相邻两个顶点的连线还有7个度,可以得到210-4+10-7=455条边解：先将5个0排成一列：00000,1若插在两个0中间，“010”，则出现2个“01”或“10”；若插在两端，贝9出现1个“01”或“10”；要使出现“01”，“10”总次数为4,有两种办法：把两个1插入0得空当内，剩下的1插入1的前面。(2)把1个1插入0得空

45、当内，再取两个1分别插入两端，剩下的1插入1的前面。故总方案数为C(4,2)X2+C(4,1)X3=36.若整数n拆分成1,2，3,，m的和，并允许重复，其母函数为：G(无)=(1十兀十F十)(1十”十艮4十(1十/十兀獭十_111-1-=186.r6r6r6r686.r6r6r6r6r6r6A=12iJ丿-62丿+43丿-34丿+25丿6丿=28故甲参加的会议次数为：28+5=3387.解：(a)从n个元素中取k个元的组合，总含有指定的m个元的组合数为。设这m个元为a,a2,，am，A；为不含a；的组合(子集)，1=1,m。，n，iAnAni1i2(n-mrn-广&丿i+Aii=1l=11乙

46、e=(-1)kc(n,k)xk的两边在区间0,1积分左端二(-x+1/(n+1)1=1/(n+1),0右端二工(1/c(n,k)xk+1/(k+1)1二1c(n,1)/2+c(n,2)/3+(dc(n,k)/(n+1)0k=0所以1c6,1)/2+c(n,2)/3+(1)nc(n,n)/(n+1)=1/(n+1)(x+(x+x12+X)4TOC o 1-5 h z=X4+X4+X4+4X3X+4X3X+4X3X+4X3X+4X3X+4X3X+123121323213132+6X2X2+6X2X2+6X2X2+12X2XX+12X2XX+12X2XX121323123213312解：第1步从特定

47、引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。所以共有C(3,1)C(2,1)C(2,1)=12种方案解：相当于把i个小球放入6个不同的盒子里，为可重组合，即共有(n+6-1,n沖方案，即C(n+5,n)中方案。19+1=20=22x5解：因=2x2x5=2x5x2=5x2x2所以部分数最小的19-完备分拆有如下3个:19=4+4+4+4+2+119=10+2+2+2+2+119=10+5+1+1+1+1101.Akf(n)=Ak2n+Ak(1)n丄(-1)Ek

48、i2n+工(1)kEk-i(d丄(-1)i=0丄(1)i=02n+ki+i=0丄(1)i=02n+ki+工(1)1+k-ii=0Ii丿i=0=2n(2-1)k+(1)n+k2k=2n+(d+k2ki=0n+k2ki+(1)乙i=0102.解：设所求为N,则N是aC)=(+13+15+)(+12+14+X+14+18+展开式中t17的系数，且A(t)=12(14L=t(+12t厶)町k+2、k=0、丿因为1+4k=17的解为k=4,3+4k=17无整数解，5+4k=17的解为k=3，所(4+2(3+2(6(5)+I2丿I2丿=25四、证明题排列n(n-l)21是有逆序n(n-l)/2。因为2有1

49、个逆序，3有2个，n有n-1个，所以总的最大逆序数为1+2+(n-1)=n(n-1)/2因为C(p,i)=p(p-1)(p-i+1)/(i(i-1)21),又因为p是素数，而pi,所以p不能整除i，iT,2,1。于是(p-1)(p-i+1)/(i(i-1)-21)一定是整数,因而p(p-1)(p-i+1)/(i!)必定是p的倍数，所以p能整除C(p,i)。因为(1+1)A(2n)=2A(2n)=4An,又因为(1+1)A(2n+1)=C(2n+1,0)+C(2n+1,1)+-+C(2n+1,2n)+C(2n+1,2n+1)因为C(2n+1,0)+C(2n+1,2)+-+C(2n+1,2n)=C

50、(2n+1,1)+C(2n+1,3)+-+C(2n+1,2n+1)所以(1+1)A(2n+1)=2(C(2n+1,0)+C(2n+1,2)+-+C(2n+1,2n)即C(2n+1,0)+C(2n+1,2)+-+C(2n+1,2n)=(1+1)A(2n)=2A(2n)=4An证明：右边=(k+1)C(n,k+1)+kC(n,k)=(k+1)n!/(k+1)!(n-k-1)!)+kn!/(k!(n-k)!)二n!/(k!(nk1)!)+kn!/(k!(n-k)!)二n!/(k!(n-k)!)(n-k+k)=nn!/(k!(n-k)!)=nC(n,k)二左边证明：左端=c(m,m)+c(m+l,m)

51、+c(n,m)=c(m,O)+c(m+l,l)+c(m+(nm),nm)二c(n+l,nm)二c(n+l,m+l).这里用到了等式3,令m=n,n-m=r即可。证明：左式二C(n,O)C(n,O)+C(n,l)C(n,l)+C(n,n)C(n,n)二C(n,O)C(n,n)+C(n,l)C(n,n-l)+C(n,n)C(n,0)=在n个蓝球和n个红球中任取n个球的方案数=C(2n,n)令G(x)二Fx+Fx2+Fxn+2n因为F=F+F，即F-FF=0,所以F的特征方程为c(x)=x2-x-1。其nn-1n-2nn-1n-2n根为a=(1+V5)/2,B=(1-V5)/2于是G(x)=A/(l

52、-ax)+B/(l-Bx)=(A+B)+(Aa+BB)x+(Aan+BBn)xn+由此知JA+B=0fA=1/V5XAa+B寵1B=-1/V5所以F=(an-Bn)/V5.n&证明：假设n代表没有两人的朋友数相同，所以他们的朋友数必定为0,1,2,，n-1这n个不同的整数。也就是说他们中必定有1个代表A无朋友，而另一个代表B有n-1个朋友，但既然A无朋友，则B不可能是他的朋友，而如果B没有A这个朋友，则B不可能有n-1个朋友，于是产生矛盾，可见n个代表各自具有不同数目的朋友的假设是错误的，由此命题得证。用归纳法证明：当n=0时，左式=02=0,右式=011/6=0,命题成立。假设当n0时对任意

53、的mWn命题均成立，则当m=n+1时左式=12+22+n2+(n+1)2二n(n+1)(2n+1)/6+(n+1)2=(n+1)(n+2)(2n+3)/6=(n+1)(n+1)+1)(2(n+1)+1)/6二右式，命题也成立，所以对于任意的n20,12+22+n2=n(n+1)(2n+1)/6。2n个人2人一组分成n组，排成二列纵队，每行左右不分，则其有C(2n,2)C(2n-2,2)C(2,2)=(2n)(2n-1)/2(2n-2)(2n-3)/2-21/2=(2n)!/2“种方案。所以(2n)!/2n必定为整数。将等边三角形各边中点相连，将该三角形分成4个边长为1/2的小等边三角形，则5个

54、点必有2个点落在其中一个小三角形内，且此两点中至少有一点不在原三角形的边上，所以这两点的矩离必小于1/2.12用归纳法证明，由F1=F2=1，Fn=Fn-1+Fn-2知F0=Oa)当n=a)当n=1时，左式二(F右式二E2命题成立b)假设当n1，对任意的mn命题成立，则当m=n+1时左式二(1(F+F二n+左式二(1(F+F二n+1nIF+Fnn-1(1(Fn+1IFF1(FF1n+1=n+2n+1F丿nlFn+1F丿nnF1(111nFn-1人10丿由此可知，对于任意的n0，命题成立。证明：因为任一个整数除以10的余数只可能为0,1,9，现有11个整数，故其中必有2个数m,n它们的余数气和r

55、2相同，即m=10k1+r1，n=10k2+r2于是,m-n=10(k-k)+r-r=10(k-k)为10的倍数。121212证明：将正方形划分为4个边长为1/2的小正方形，则5个点中必不2点取自同一个小正方形，小正方形内最长的线段均小于其对角线的长度V2/2.因为这两条对角线的4个顶点中只有一个属于小正方形内部，所以由落在这个小正方形内的两点组成的线段的长度必定小于2/2.证明：设H=a,a,a,对任一xG,若i工j,则xaMxa,TOC o 1-5 h z12kij若不然，假设xa=xa,在等式两边乘上x-1,即x-1xa=x-1xa,ijij于是得a=a，但已假设iMj,且H中无相同元素

56、，所以xaMxa,ijij即丨xH|=|xa,xa2,xajl二K.16证明：令A=(x,y)，(x,y),，(x5,y5)。因为A中的点(x，y)(i=l,112255ii2,3,4,5)是格点，即x和y均为整数，所以在这5个格点中必有3个格点的iix坐标的奇偶性相同，不妨设x1，x2,x3均为偶数。于是在格点集B=(x1，y1),(x2,y2)，(x3,y3)中必有2个格点的y坐标的奇偶性相同，不妨设人，打均为奇数。于是格点(x,y)和(x,y)的中点M的坐标为(M,M),其中M=(xx)/2,M=(y1122xyx21y2y)/2,因为x和x均为偶数，y和y均为奇数，所以M和M均为整数，

57、也就是说点11212xyM是格点。证明：假设符合条件的字符串集合为A,其中的字符串个数为a。设由0、1、2组n成的长度为n的字符串中0出现奇数次的字符串个数为b,那么，根据字符串最后一位n为0或1或2将A中字符串分类，若最后一位是1或2,则共有2a个，若最后一位n1是0,则前n1位中必有奇数个0,故有b个，于是n1a=2a+b，但a+b=3n1,所以，b=3n1a，于是TOC o 1-5 h znn1n1n1n1n1n1a=a+3n-1,即卩aa=3n1,由此知aa=3n2，也就是3a3ann1nn1n1n2n1n2=3n-1，于是有a4a+3a=0,其特征方程为x24x+3=0,解此方程得：

58、nn1n2a=1,a=3,所以a=A1n+A3n，而a=2,a=5,于是有12n1212A+3A=212A+9A=512解得A=1/21A=1/22所以a=(3n+1)/2n证明：因为从n+r个不同的物品中任取r个的方案数是C(n+r,r)=(n+r)(n+r1).(n+rr+1)/r!=(n+1)(n+2).(n+r)/r!它是一个整数，所以(n+1)(n+2).(n+r)必能被r!整除。证明：因为已知C(n,l)C(l,r)=C(n,r)C(n-r,lr)卩卩C(m,n)C(n,r)=C(m,r)C(m-r,n-r),所以左端=C(m,0)C(m,n)+C(m,1)C(m-1,nT)+.+

59、C(m,n)C(m-n,0)=C(m,m)C(m,m-n)+C(m,m-1)C(m-1,m-n)+.+C(m,m-n)C(m-n,m-n)=C(m,m-n)C(m-(m-n),m-(m-n)+C(m,m-n)C(m-(m-n),m-1-(m-n)+.+C(m,m-n)C(m-(m-n),m-n-(m-n)=C(m,n)C(n,0)+C(m,n)C(n,1)+.+C(m,n)C(n,n)=C(m,n)(C(n,0)+C(n,l)+.+C(n,n)=C(m,n)2n=右端故命题得证。证明：将3n个人排成n行，每行3人，不分左中右，贝排列方案数为C(3n,3)C(3n-3,3).C(3,3),其中C

60、(3n,3)为第1行的可能方案数，C(3n-3,3)为在剩余3n-3个人中任取3人站在第2行的方案数，C(3,3)为最后3个人站在第n行的方案数，因为必须为每一行确定人选，故用乘法法则，由于C(3n,3)C(3n-3,3).C(3,3)=(3n)(3n-1)(3n-2)/3!(3n-3)(3n-4)(3n-5)/3!.321/!=(3n)!/(3!)n是方案数，它必为整数，所以(3n)!/(2n3n)必是整数。证明：设任给的5个数为a,a,a,a,a，将它们除以3得到的余数分别是TOC o 1-5 h z12345r,r,r,r,r,即卩a=3M+r(i=1,2,3,4,5),因为除以3的余数