组合数学答案

1、离线考核组合数学满分100分一、计算题(每小题 10分，共60分。) 7 231、求Xi X2 . X5的展开式中X1X3X4X5的系数？展开后合并同类项，则一共有多少项？在多项式XiX2.X57的展开式中的项X；X3X：X5的系数是C/1,3,1=7!=420.2!0!1!3!1!因为在它的展开式中不同项(合并同类项后)的个数等于从5个不同元素中有重复地取出7个元素的方法数，所以不同项的个数为C； 71 330。2、求从1至1000的整数中能被14或21整除的整数的个数。解：设所求为N,令S 1,2,1000,以A, B分别表示S中能被14和能被21整除的整数所成之集,N A B A B A

2、 B100010001000142114 371 47 23 953、一次宴会，7位来宾寄存他们的帽子，在取回他们的帽子时，问有多少种可能使得：(1)没有一位来宾取回的是他自己的帽子？(5分)(2)至少有一位来宾取回的是他自己的帽子？ (5分)解：记7个来宾为A , A2 ,A7 ,则7个来宾取帽子的方法可看成是由A , A2 ,，A7作成的全排列：如果A (K i <7)拿了 Aj的帽子，则把 Ai排在第j位，于是(1)没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数D7 ,即等于1854。(2)至少有一位来宾取回的是他自己的帽子的取法种数等于由A1, A2,，A7作成的至少有

3、一个元保位的全排列数，为7! D7 5040 1854 31864、在平面上，对任意自然数n,连接原点O与点Pn(n, n 3),用f(n)表示线段OPn上除端点外的整点个数试求 f (1) f(2) L f(2004).解线段OPn的方程为y -3X,0 x n.n如果n与n3互素，则不定方程(n 3)x ny 0不存在适合0 X n的整数解，即f (n)0;如果n与 n 3不互素，则n与n 3只能有公因数3,即可以设n 3k.则通过解不定方程，有整数点(k,k 1),(2k,2(k1)位于线段OPn之上，且OPn中间仅有这二个整数点，即f(n) 2 .所以2 型04 2 668 1336.

4、35、解递推关系an5an 1 6an 2 (n 2)a04 al9解：特征方程为x2 5x 6 0 ,特征根为x12 , X23 ,所以 an a 2n a 3n,其中 c1，C2是待定常数，由初始条件得c1G242G 3c29解之得c13, c21,所以an 3 2n3n(n 0,1,2,)f (1) f(2)f(3) L f (2004)5、现有人手中有 3张一元,2张2元和3张5元的钱币，问该人都能买价值为多少的物品？对每种价值的物品他有几种付款方法?解令一元钱币对应的能买物品的形式哥级数为f1(x) 1 x x2 X3； 2元钱币对应的能买物品的形式募级数为f2(x) 1 x2 (x

5、2)2 1 x2 x4 ; 5元钱币对应的能买物品的形式哥级数为55 25 351015 ，f5(x) 1 x (x ) (x )1 x x x则该人能买物品对应的形式哥级数为f(x) f1(x) f2(x)f5(x)232451015(1 x x x )(1 x x )(1 x x x )2345678910= 1+x+2x +2x +2x +3x +2x +3x +2x +2x +3x1112131415161718+2x +3x +2x +2x +3x +2x +3x +2x1920 ,21 ,22+2x +2x +x +x所以该人可以买价值分别为0,1,2, L ,21,22元的物品，

6、并且付款的方法数分别为 0,1,2,2,2,3,2,3,2,2,3,2,3,2,2,3,2,3,2,2,2,1,1.二、证明题(每小题 20分，共40分。)1、证明：1 kC；C：0 。k 0证明在牛顿定理中令a 1, b对上式两边的t求微商，得到令t=1,我们就得到第一个结论t,则有 1 t n 1 kC：tk k 0n 1kkx k 1n 1 t1 kCn t.k 1如果我们对(1)式两边的t进彳t r次微商，则有1 r Pnr 1 t nr1 kPkrCnktkr.k r在上式两边同时除以r!,并令t=1,即可得到第二个结论.2、证明：在任意Z出的1998个自然数ai,a2,，ai998中，必存在若干个数，它们的和能被1998整除。证明：令B>&, bi998,其中bja1a2 aj (j 1,2,1998)贝U B 1998,对任一个非负整数 i(0wiw1997),令Bibb B且b除以1998所得余数为i,则BiB (i 0,1,2,，1997)1997且BiB,如果Boi 0，设bs是Bo1997，则BiB,i 0由鸽笼原理的简单形式，必有正整数