大学数学组合数学试题与答案(修正版)4

《组合数学》练习题一参考答案《组合数学》练习题一参考答案一、填空：1.!()!m n P n m m n m =- 2.2)1(-n n 3. 0. 4. 2675.),2,1,0(3)2(2321 =+-+=n c c c a n n n n .6.4207.78.()()!!11...!31!21!111n n n ??-++-+-9.22 10.267二、选择：1. 1—10 A B D D A D A B B C三、计算： 1. 解因为]250[=25, ]450[=12, ]850[=6, ]1650[=3, ]3250[=1, ]6450[=0, 所以, 所求的最高次幂是2(50!)=25+12+6+3+1=47.2. 解由我们最初观察的式子,有614,1124,634,144=??===, 再利用定理1,我们得到24!415,102)15(545,155==??=-?==, 3511642434435=+?=???+=, 5061141424425=+?=??+=. 所以,x x x x x x f 24503510)(23455+-+-=.3. 解：设所求为N ，令}2000,,2,1{ =S ，以A ，B ，C 分别表示S 中能被32?，52?，53?整除的整数所成之集，则53466663133200333 532200053220003532000522000322000 =+?-++=+-???????+???????+???????=+---++==C B A C B C A B A C B A CB A N 4. 解：记7个来宾为1A ，2A ，…，7A ，则7个来宾的取帽子方法可看成是由1A ，2A ，…，7A 作成的这样的全排列：如果i A （1≤i ≤7）拿了j A 的帽子，则把i A 排在第j 位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数7D ，即等于1854。

根据清华远程教育课堂答案编辑整理,有改动，如果有错误，请指正。

――编者注 第一章习题1.证任一正整数n 可唯一地表成如下形式:,0≤a i ≤i,i ＝1,2,…。

证：对n 用归纳法。

先证可表示性：当n=0,1时，命题成立。

假设对小于n 的非负整数，命题成立。

对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k ·k!由假设对n-k!,命题成立，设，其中a k ≤k-1,，命题成立。

再证表示的唯一性：设, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!, ∑∑∑∑⋅-≥⋅-≥⋅>≥⋅-=⋅-!)(!!!!)(!)(i a bi a bi i j i a bj b a i ii ii ij j矛盾，命题成立。

另一种证法：令j=max{i|a i ≠b i}, 两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾.2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。

证：)1,()1()!1()!1(!)1()!1(!)1(!)1()!1(!1),1(++=--⋅+⋅+=--⋅⋅+⋅+=--⋅-=-r n C r r n r n r r n r r n r r n r n n r n nC组合意义：等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。

显然两种方案数相同。

3.证。

证：由等式∑==⋅++⋅+⋅+=+nk knn xk n C xn n C x n C x n C n C x 02),(),()2,()1,()0,()1(两边求导并令x=1,即命题得证。

第四章 生成函数1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4}=235(11111)1x x x x x +++-（）（2）343,,,333n +⎧⎫⎛⎫⎛⎫⎛⎫⎨⎬ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎩⎭L 解：3n G n +⎧⎫⎛⎫⎨⎬ ⎪⎝⎭⎩⎭=41(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=（211x-）2. （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…=11kx -. 2. 求下列和式： （1）14+24+…+n 4解：由上面第一题可知，{n 4}生成函数为A(x)=235(11111)1x x x x x +++-（）=0kk k a x ∞=∑， 此处a k =k 4.令b n =14+24+…+n 4，则b n =0nk k a =∑，由性质3即得数列{b n }的生成函数为 B(x)= 0nn n b x ∞=∑=()1A x x -=34125(1111)ii i x x x x x i ∞=++++⎛⎫ ⎪⎝⎭∑. 比较等式两边x n 的系数，便得14+24+…+n 4=b n =1525354511111234n n n n n n n n -+-+-+-++++----⎛⎫⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭321(1)(691)30n n n n n =+++-（2）1·2+2·3+…+n (n +1)解：{ n (n +1)}的生成函数为A(x)=32(1)x x -=0kk k a x ∞=∑，此处a k = n (n +1).令b n =1·2+2·3+…+n (n +1)，则b n =0nk k a =∑.由性质3即得数列{b n }的生成函数为B(x)=nn n b x ∞=∑=()1A x x-=42(1)xx -=032nk kk x x k =+⎛⎫⎪⎝⎭∑. 比较等式两边x n 的系数，便得1·2+2·3+…+n (n +1)= b n =2(1)(2)213n n n n n +++=-⎛⎫ ⎪⎝⎭. 3. 利用生成函数求解下列递推关系： （1）()7(1)12(2)(0)2,(1)7f n f n f n f f =---==⎧⎨⎩;解：令A(x)=0()n n f n x ∞=∑则有A(x)-f(0)-f(1)x=2()nn f n x ∞=∑=2(7(1)12(2))n nf n f n x∞=---∑=217()12()nnn n x f n x xf n x∞∞==-∑∑=7x(A(x)-f(0))-12x 2A(x).将f(0)=2，f(1)=7代入上式并整理，得22711()(34)17121314n n n x A x x x x x ∞=-==+=+-+--∑. （2）()3(1)53(0)0nf n f n f =-+⋅=⎧⎨⎩;解：令A(x)=0()nn f n x ∞=∑，则有A(x)-f(0)= 1(3(1)53)n nnf n x ∞=-+⋅∑=03()153nn n n n x f n x x x ∞∞==+∑∑=3xA(x)+15x·113x-.A(x)= 215(13)xx - （3）()2(1)(2)(0)0,(1)1f n f n f n f f =-+-==⎧⎨⎩;解：令A(x)=0()nn f n x ∞=∑，则有A(x)-f(0)-f(1)x=2(2(1)(2))n nf n f n x ∞=-+-∑=212()()nnn n x f n x xf n x∞∞==+∑∑=2x(A(x)-f(0))+x 2A(x).将f(0)=0，f(1)=1代入上式并整理，得2()12x A x x x =--.4. 设序列{n a }的生成函数为：343(1)(1)xx x x --+-,但00b a =,110b a a =-,……,1n n n b a a -=-,……,求序列{n b }的生成函数.解：由00b a =,110b a a =-,……,1n n n b a a -=-,得0nk n k b a ==∑，所以A(x)=()1B x x-.由此得B(x)=(1-x)A(x)= 3431xx x -+-，亦即序列{n b }的生成函数。

第2章 鸽巢原理2.4 练习题1、关于本节中的应用4，证明对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋（情形=k 21是在应用4中处理的情况）。

能否判断：存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？证明：设i a 表示在前i 天下棋的总数若正好有i a =k ,则命题得证。

若不然,如下：∵共有11周，每天至少一盘棋，每周下棋不能超过12盘∴有 771≤≤i ，且13217721≤<<<≤a a a {}21,,2,1 ∈∀k 有kk a k a k a k +≤+<<+<+≤+13217721 观察以下154个整数：ka k a k a a a a +++77217721,,,,,,, 每一个数是1到k +132之间的整数，其中153132≤+k 由鸽巢原理，这154个数中至少存在两个相等的数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了k 盘棋。

综上所述，对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋。

□当k =22时，132+k =154，那么以下154个整数22,,22,22,,,,77217721+++a a a a a a在1到154之间。

ⅰ）若这154个数都不相同则它们能取到1到154的所有整数，必然有一个数是22∵2222>+i a ，771≤≤i ∴等于22的数必然是某个i a ，771≤≤i则在前i 天，这位国际象棋大师总共下了22盘棋。

ⅱ）若这154个数中存在相同的两个数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了k 盘棋。

第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 2⨯5⨯P(8,2)+3⨯4⨯P(8,2)6. (n+1)!-17. 用数学归纳法易证。

8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn k , 则n 2的除数个数为 ( 2p 1+1) (2p 2+1) …(2p k+1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。

11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。

当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。

故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。

第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。

满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。

满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。

1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。

将女生插入，有5!种方案。

故按乘法原理，有：7!×58C ×5!=33868800(种)方案。

(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≤n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。

1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5；解：（1）：由|a-b|=5⇒a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。

当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。

所以这样的序列有90对。

（2）：由题意知，|a-b|≤5⇒|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。

当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。

当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对所以总的序列数=90+98+96+94+92+50=5201.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2所以总的排列数为上述6种情况之和。

组合数学第4章答案4.1证明所有的循环群是ABEL 群 证明：nn ,,**×x ,x m nm na b G G a b b a x xa b b a ++∈==∴=mmm 循环群也是群，所以群的定义不用再证，只需证明对于任意是循环群，有成立，因为循环群中的元素可写成a=x 形式所以等式左边x 等式右边x ＝，，即所有的循环群都是ABEL 群。

4.2x 是群G 的一个元素，存在一最小的正整数m ，使x m =e ，则称m 为x的阶，试证：C=｛e,x,x 2, …,x m-1｝ 证：x 是G 的元素，G 满足封闭性所以，xk 是G 中的元素 C ∈G再证C 是群：1、x i , x j ∈C , x i ·x j = x i+j 若i+j<=m-1,则x i+j ∈C若i+j>m,那么x i+j =x m+k =x m ·x k =x k ∈C 所以C 满足封闭性。

2、存在单位元e.3、显然满足结合性。

4、存在逆元， 设x a ·x b =e=x m x b =x m-ax a ∈C, (x a )-1= x b =x m-a4.3设G 是阶为n 的有限群，则G 的所有元素的阶都不超过n.证明：设G 是阶为n 的有限群，a 是G 中的任意元素，a 的阶素为k ， 则此题要证n k ≤首先考察下列n+1个元素a a a a a n 1432,....,,,+由群的运算的封闭性可知，这n+1个元素都属于G ,，而G 中仅有n 个元素，所以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为aaji i+=（n j ≤≤1）aa ajii*=由群的性质3可知，a j是单位元，即a j=e ，又由元素的阶数的定义可知，当a 为k 阶元素时a k=e ，且k 是满足上诉等式的最小正整数，由此可证n j k ≤≤4.4 若G 是阶为n 的循环群，求群G 的母元素的数目，即G 的元素可表示a 的幂：a,a2……..an解：设n=p 1a1…….p k ak ，共n 个素数的乘积，所以群G 中每个元素都以用这k 个素数来表示，而这些素数，根据欧拉定理，一共有 Φ(n)=n(1-1/p 1)………(1-1/p k )所以群G 中母元素的数目为n(1-1/p 1)………(1-1/p k )个. 4.5证明循环群的子群也是循环群证明：设H 是G=<a>的子群，若H=<e>,显然H 是循环群，否则取H 中最小的正方幂元m a ，下面证明m a 是H 的生成元,易见m a ⊆H ，只要证明H 中的任何元素都可以表成m a 的整数次方，由除法可知存在q 和r,使得l=qm+r,其中0≤r ≤m-1,因此有r a =qm l a -，因为m a 是H 中最小的正方幂元，必有r=0,这就证明出la=mq a }{m a ∈证明完毕。

组合数学期末考查卷一、选择题。

（每小题3分，共24分）1.在组合数学的恒等式中n k ⎛⎫= ⎪⎝⎭A 11(1)1n n n k k k --⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭B 1(1)1n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭C 1(1)11n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪--⎝⎭⎝⎭D (1)1n n n k k k ⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭2、14321=++x x x 的非负整数解个数为（ ）。

A.120B.100C.85D.503、()()=94P 。

A. 5B. 8C. 10D. 64、递推关系12432(2)n n n n a a a n --=-+≥的特解形式是（a 为待定系数）（）A 、2n anB 、2n aC 、32n anD 、22nan 5、错排方式数n D =（）A 1(1)n n nD ++-B (1)(1)n n n D ++-C -1(1)n n nD +- D 1(1)(1)n n n D +++-6、将n 个不同的球放入m 个不同的盒子且每盒非空的方式数为（ ）。

Ａ（nm ） Ｂ (),P n m Ｃ ｍ！Ｓ2（ｎ，ｍ） Ｄ（nm ）ｍ！7、有100只小鸟飞进6个笼子，则必有一个笼子至少有（ ）只小鸟。

A 15B 16C 17D 188、若颁发26份奖品给4个人，每人至少有3份，有（ ）种分法A 55B 40C 50D 39二、填空。

（每小题4分，共20分）1、现有7本不同的书，要分给6个同学，且每位同学都要有书，有__________________种不同的分法2、设q 1, q 2,…… ,q n 是n 个正整数，如果将q 1+ q 2+…+q n －n ﹢1件东西放入n 个盒子里，则必存在一个盒子j 0，1≤j 0≤n ，使得第0j 个盒子里至少装有0j q 件东西，我们把该定理称为__________________。

习题四（容斥原理）1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则22001002A ⎢⎥==⎢⎥⎣⎦，3200663A ⎢⎥==⎢⎥⎣⎦，5200405A ⎢⎥==⎢⎥⎣⎦，7200287A ⎢⎥==⎢⎥⎣⎦， 112001811A ⎢⎥==⎢⎥⎣⎦，132001513A ⎢⎥==⎢⎥⎣⎦，232003323A A ⎢⎥==⎢⎥⨯⎣⎦， 252002025A A ⎢⎥==⎢⎥⨯⎣⎦，272001427A A ⎢⎥==⎢⎥⨯⎣⎦，2112009211A A ⎢⎥==⎢⎥⨯⎣⎦， 2132007213A A ⎢⎥==⎢⎥⨯⎣⎦，352001335A A ⎢⎥==⎢⎥⨯⎣⎦，37200937A A ⎢⎥==⎢⎥⨯⎣⎦， 3112006311A A ⎢⎥==⎢⎥⨯⎣⎦，3132005313A A ⎢⎥==⎢⎥⨯⎣⎦，57200557A A ⎢⎥==⎢⎥⨯⎣⎦， 5112003511A A ⎢⎥==⎢⎥⨯⎣⎦，5132003513A A ⎢⎥==⎢⎥⨯⎣⎦，7112002711A A ⎢⎥==⎢⎥⨯⎣⎦， 7132002713A A ⎢⎥==⎢⎥⨯⎣⎦，111320011113A A ⎢⎥==⎢⎥⨯⎣⎦，2352006235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 2372004237A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231120032311A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231320022313A A A ⎢⎥==⎢⎥⨯⨯⎣⎦ 2572002257A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251120012511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251320012513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 271120012711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，271320012713A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 21113200021113A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，3572001357A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，351120013511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦351320013513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，371120003711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，…， 235720002357A A A A ⎢⎥==⎢⎥⨯⨯⨯⎣⎦，…，23571113200023571113A A A A A A ⎢⎥==⎢⎥⨯⨯⨯⨯⨯⎣⎦， 所以 23571113200(1006640281815)(3320149713965533221)(6432211110111i i j i j k i j k lii ji j ki j k li j k l m i j k l m ni j k l mi j k l m nA A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+-+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑∑0)00041+-+=但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：416146+-=2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，则2200010002A ⎢⎥==⎢⎥⎣⎦，320006663A ⎢⎥==⎢⎥⎣⎦，520004005A ⎢⎥==⎢⎥⎣⎦， 23200033323A A ⎢⎥==⎢⎥⨯⎣⎦，25200020025A A ⎢⎥==⎢⎥⨯⎣⎦，35200013335A A ⎢⎥==⎢⎥⨯⎣⎦， 235200066235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， （1）即求235A A A ++，根据容斥原理有：235235232535235()1000666400(333200133)661466A A A A A A A A A A A A A A A ++=++-+++=++-+++=（2）即求232535A A A A A A ++，根据容斥原理有：232535232535235235235235()333200133266534A A A A A A A A A A A A A A A A A A A A A A A A ++=++-+++=++-⨯=（3）即求[1]N ，根据Jordan 公式有：1112233235232535235[1]2()310006664002(333200133)366932N q C q C q A A A A A A A A A A A A =-+=++-⨯+++⨯=++-⨯+++⨯=3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。

数学组合综合练习题及答案数学组合综合练习题及答案一、选择题1．某年级有6个班，分别派3名语文教师任教，每个教师教2个班，则不同的任课方法种数为( )A．C26C24C22 B．A26A24A22C．C26C24C22C33 D.A26C24C22A33[答案] A2．从单词“equation”中取5个不同的字母排成一排，含有“qu”(其中“qu”相连且顺序不变)的不同排法共有( )A．120种 B．480种C．720种 D．840种[答案] B[解析] 先选后排，从除qu外的6个字母中任选3个字母有C36种排法，再将qu看成一个整体(相当于一个元素)与选出的3个字母进行全排列有A44种排法，由分步乘法计数原理得不同排法共有C36A44＝480(种)．3．从编号为1、2、3、4的四种不同的种子中选出3种，在3块不同的土地上试种，每块土地上试种一种，其中1号种子必须试种，则不同的试种方法有( )A．24种 B．18种C．12种 D．96种[答案] B[解析] 先选后排C23A33＝18，故选B.4．把0、1、2、3、4、5这六个数，每次取三个不同的数字，把其中最大的数放在百位上排成三位数，这样的三位数有( ) A．40个 B．120个C．360个 D．720个[答案] A[解析] 先选取3个不同的数有C36种方法，然后把其中最大的数放在百位上，另两个不同的数放在十位和个位上，有A22种排法，故共有C36A22＝40个三位数．5．(2010湖南理，7)在某种信息传输过程中，用4个数字的一个排列(数字允许重复)表示一个信息，不同排列表示不同信息，若所用数字只有0和1，则与信息0110至多有两个对应位置上的数字相同的信息个数为( )A．10 B．11C．12 D．15[答案] B[解析] 与信息0110至多有两个对应位置上的数字相同的信息包括三类：第一类：与信息0110只有两个对应位置上的数字相同有C24＝6(个)第二类：与信息0110只有一个对应位置上的数字相同有C14＝4(个)第三类：与信息0110没有一个对应位置上的数字相同有C04＝1(个)与信息0110至多有两个对应位置上的数字相同的信息有6＋4＋1＝11(个)6．北京《财富》全球论坛开幕期间，某高校有14名志愿者参加接待工作．若每天排早，中，晚三班，每班4人，每人每天最多值一班，则开幕式当天不同的排班种数为( )A．C414C412C48 B．C1214C412C48C.C1214C412C48A33 D．C1214C412C48A33[答案] B[解析] 解法1：由题意知不同的排班种数为：C414C410C46＝14×13×12×114！10×9×8×74！6×52！＝C1214C412C48.故选B.解法2：也可先选出12人再排班为：C1214C412C48C44，即选B.7．(2009湖南理5)从10名大学毕业生中选3人担任村长助理，则甲、乙至少有1人入选，而丙没有入选的不同选法的种数为( ) A．85 B．56C．49 D．28[答案] C[解析] 考查有限制条件的组合问题．(1)从甲、乙两人中选1人，有2种选法，从除甲、乙、丙外的7人中选2人，有C27种选法，由分步乘法计数原理知，共有2C27＝42种．(2)甲、乙两人全选，再从除丙外的其余7人中选1人共7种选法．由分类计数原理知共有不同选法42＋7＝49种．8．以一个正三棱柱的顶点为顶点的四面体共有( )A．6个 B．12个C．18个 D．30个[答案] B[解析] C46－3＝12个，故选B.9．(2009辽宁理，5)从5名男医生、4名女医生中选3名医生组成一个医疗小分队，要求其中男、女医生都有，则不同的组队方案共有( )A．70种 B．80种C．100种 D．140种[答案] A[解析] 考查排列组合有关知识．解：可分两类，男医生2名，女医生1名或男医生1名，女医生2名，∴共有C25C14＋C15C24＝70，∴选A.10．设集合Ⅰ＝{1,2,3,4,5}．选择Ⅰ的两个非空子集A和B，要使B中最小的数大于A中最大的数，则不同的选择方法共有( ) A．50种 B．49种C．48种 D．47种[答案] B[解析] 主要考查集合、排列、组合的基础知识．考查分类讨论的思想方法．因为集合A中的最大元素小于集合B中的最小元素，A中元素从1、2、3、4中取，B中元素从2、3、4、5中取，由于A、B非空，故至少要有一个元素．1° 当A＝{1}时，选B的方案共有24－1＝15种，当A＝{2}时，选B的方案共有23－1＝7种，当A＝{3}时，选B的方案共有22－1＝3种，当A＝{4}时，选B的方案共有21－1＝1种．故A是单元素集时，B有15＋7＋3＋1＝26种．2° A为二元素集时，A中最大元素是2，有1种，选B的方案有23－1＝7种．A中最大元素是3，有C12种，选B的方案有22－1＝3种．故共有2×3＝6种．A中最大元素是4，有C13种．选B的方案有21－1＝1种，故共有3×1＝3种．故A中有两个元素时共有7＋6＋3＝16种．3° A为三元素集时，A中最大元素是3，有1种，选B的方案有22－1＝3种．A中最大元素是4，有C23＝3种，选B的方案有1种，∴共有3×1＝3种．∴A为三元素时共有3＋3＝6种．4° A为四元素时，只能是A＝{1、2、3、4}，故B只能是{5}，只有一种．∴共有26＋16＋6＋1＝49种．二、填空题11．北京市某中学要把9台型号相同的电脑送给西部地区的三所希望小学，每所小学至少得到2台，共有______种不同送法．[答案] 10[解析] 每校先各得一台，再将剩余6台分成3份，用插板法解，共有C25＝10种．12．一排7个座位分给3人坐，要求任何两人都不得相邻，所有不同排法的`总数有________种．[答案] 60[解析] 对于任一种坐法，可视4个空位为0,3个人为1,2,3则所有不同坐法的种数可看作4个0和1,2,3的一种编码，要求1,2,3不得相邻故从4个0形成的5个空档中选3个插入1,2,3即可．∴不同排法有A35＝60种．13．(09海南宁夏理15)7名志愿者中安排6人在周六、周日两天参加社区公益活动．若每天安排3人，则不同的安排方案共有________种(用数字作答)．[答案] 140[解析] 本题主要考查排列组合知识．由题意知，若每天安排3人，则不同的安排方案有C37C34＝140种．14．2010年上海世博会期间，将5名志愿者分配到3个不同国家的场馆参加接待工作，每个场馆至少分配一名志愿者的方案种数是________种．[答案] 150[解析] 先分组共有C35＋C25C232种，然后进行排列，有A33种，所以共有(C35＋C25C232)A33＝150种方案．三、解答题15．解方程Cx2＋3x＋216＝C5x＋516.[解析] 因为Cx2＋3x＋216＝C5x＋516，所以x2＋3x＋2＝5x＋5或(x2＋3x＋2)＋(5x＋5)＝16，即x2－2x－3＝0或x2＋8x－9＝0，所以x＝－1或x＝3或x＝－9或x＝1.经检验x＝3和x＝－9不符合题意，舍去，故原方程的解为x1＝－1，x2＝1.16．在∠MON的边OM上有5个异于O点的点，边ON上有4个异于O点的点，以这10个点(含O点)为顶点，可以得到多少个三角形？[解析] 解法1：(直接法)分几种情况考虑：O为顶点的三角形中，必须另外两个顶点分别在OM、ON上，所以有C15C14个，O不为顶点的三角形中，两个顶点在OM上，一个顶点在ON上有C25C14个，一个顶点在OM上，两个顶点在ON上有C15C24个．因为这是分类问题，所以用分类加法计数原理，共有C15C14＋C25C14＋C15C24＝5×4＋10×4＋5×6＝90(个)．解法2：(间接法)先不考虑共线点的问题，从10个不同元素中任取三点的组合数是C310，但其中OM上的6个点(含O点)中任取三点不能得到三角形，ON上的5个点(含O点)中任取3点也不能得到三角形，所以共可以得到C310－C36－C35个，即C310－C36－C35＝10×9×81×2×3－6×5×41×2×3－5×41×2＝120－20－10＝90(个)．解法3：也可以这样考虑，把O点看成是OM边上的点，先从OM上的6个点(含O点)中取2点，ON上的4点(不含O点)中取一点，可得C26C14个三角形，再从OM上的5点(不含O点)中取一点，从ON上的4点(不含O点)中取两点，可得C15C24个三角形，所以共有C26C14＋C15C24＝15×4＋5×6＝90(个)．17．某次足球比赛共12支球队参加，分三个阶段进行．(1)小组赛：经抽签分成甲、乙两组，每组6队进行单循环比赛，以积分及净剩球数取前两名；(2)半决赛：甲组第一名与乙组第二名，乙组第一名与甲组第二名作主客场交叉淘汰赛(每两队主客场各赛一场)决出胜者；(3)决赛：两个胜队参加决赛一场，决出胜负．问全程赛程共需比赛多少场？[解析] (1)小组赛中每组6队进行单循环比赛，就是6支球队的任两支球队都要比赛一次，所需比赛的场次即为从6个元素中任取2个元素的组合数，所以小组赛共要比赛2C26＝30(场)．(2)半决赛中甲组第一名与乙组第二名(或乙组第一名与甲组第二名)主客场各赛一场，所需比赛的场次即为从2个元素中任取2个元素的排列数，所以半决赛共要比赛2A22＝4(场)．(3)决赛只需比赛1场，即可决出胜负．所以全部赛程共需比赛30＋4＋1＝35(场)．18．有9本不同的课外书，分给甲、乙、丙三名同学，求在下列条件下，各有多少种分法？(1)甲得4本，乙得3本，丙得2本；(2)一人得4本，一人得3本，一人得2本；(3)甲、乙、丙各得3本．[分析] 由题目可获取以下主要信息：①9本不同的课外书分给甲、乙丙三名同学；②题目中的3个问题的条件不同．解答本题先判断是否与顺序有关，然后利用相关的知识去解答．[解析] (1)分三步完成：第一步：从9本不同的书中，任取4本分给甲，有C49种方法；第二步：从余下的5本书中，任取3本给乙，有C35种方法；第三步：把剩下的书给丙有C22种方法，∴共有不同的分法有C49C35C22＝1260(种)．(2)分两步完成：第一步：将4本、3本、2本分成三组有C49C35C22种方法；第二步：将分成的三组书分给甲、乙、丙三个人，有A33种方法，∴共有C49C35C22A33＝7560(种)．(3)用与(1)相同的方法求解，得C39C36C33＝1680(种)．。

习题四（容斥原理）1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则22001002A ⎢⎥==⎢⎥⎣⎦，3200663A ⎢⎥==⎢⎥⎣⎦，5200405A ⎢⎥==⎢⎥⎣⎦，7200287A ⎢⎥==⎢⎥⎣⎦， 112001811A ⎢⎥==⎢⎥⎣⎦，132001513A ⎢⎥==⎢⎥⎣⎦，232003323A A ⎢⎥==⎢⎥⨯⎣⎦， 252002025A A ⎢⎥==⎢⎥⨯⎣⎦，272001427A A ⎢⎥==⎢⎥⨯⎣⎦，2112009211A A ⎢⎥==⎢⎥⨯⎣⎦， 2132007213A A ⎢⎥==⎢⎥⨯⎣⎦，352001335A A ⎢⎥==⎢⎥⨯⎣⎦，37200937A A ⎢⎥==⎢⎥⨯⎣⎦， 3112006311A A ⎢⎥==⎢⎥⨯⎣⎦，3132005313A A ⎢⎥==⎢⎥⨯⎣⎦，57200557A A ⎢⎥==⎢⎥⨯⎣⎦， 5112003511A A ⎢⎥==⎢⎥⨯⎣⎦，5132003513A A ⎢⎥==⎢⎥⨯⎣⎦，7112002711A A ⎢⎥==⎢⎥⨯⎣⎦， 7132002713A A ⎢⎥==⎢⎥⨯⎣⎦，111320011113A A ⎢⎥==⎢⎥⨯⎣⎦，2352006235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 2372004237A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231120032311A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231320022313A A A ⎢⎥==⎢⎥⨯⨯⎣⎦ 2572002257A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251120012511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251320012513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 271120012711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，271320012713A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 21113200021113A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，3572001357A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，351120013511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦351320013513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，371120003711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，…， 235720002357A A A A ⎢⎥==⎢⎥⨯⨯⨯⎣⎦，…，23571113200023571113A A A A A A ⎢⎥==⎢⎥⨯⨯⨯⨯⨯⎣⎦， 所以 23571113200(1006640281815)(3320149713965533221)(6432211110111i i j i j k i j k lii ji j ki j k li j k l m i j k l m ni j k l mi j k l m nA A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+-+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑∑0)00041+-+=但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：416146+-=2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，则2200010002A ⎢⎥==⎢⎥⎣⎦，320006663A ⎢⎥==⎢⎥⎣⎦，520004005A ⎢⎥==⎢⎥⎣⎦， 23200033323A A ⎢⎥==⎢⎥⨯⎣⎦，25200020025A A ⎢⎥==⎢⎥⨯⎣⎦，35200013335A A ⎢⎥==⎢⎥⨯⎣⎦， 235200066235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， （1）即求235A A A ++，根据容斥原理有：235235232535235()1000666400(333200133)661466A A A A A A A A A A A A A A A ++=++-+++=++-+++=（2）即求232535A A A A A A ++，根据容斥原理有：232535232535235235235235()333200133266534A A A A A A A A A A A A A A A A A A A A A A A A ++=++-+++=++-⨯=（3）即求[1]N ，根据Jordan 公式有：1112233235232535235[1]2()310006664002(333200133)366932N q C q C q A A A A A A A A A A A A =-+=++-⨯+++⨯=++-⨯+++⨯=3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。

组合数学题目及标准答案————————————————————————————————作者：————————————————————————————————日期：组合数学例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。

问共有多少种不同的安全状态?解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。

用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。

这种对应显然是一对一的。

因此，安全状态的总数等于这8个数的全排列总数8!＝40320。

例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。

证明n 偶数。

证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。

根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。

例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。

证 设n +1个数是a 1, a 2, ···, an +1。

每个数去掉一切2的因子，直至剩下一个奇数为止。

组成序列r 1, r 2,, ···, rn +1。

这n +1个数仍在[1 , 2n ]中，且都是奇数。

而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。

若ai ＞aj ，则ai 是aj 的倍数。

例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k<l ≤m ，使得和ak+1+ ak +2+ ···+ al 是m 的倍数。

证 设Sh = , Sh ≡rh mod m, 0≤rh ≤m -1，h = 1 , 2 , ···, m . 若存在l , Sl ≡0 mod m 则命题成立．否则，1≤rh ≤m -1．但h = 1 , 2 , ···,m ．由 鸽巢原理，故存在rk= rl , 即Sk ≡Sl mod m ，不妨设l ＞k ．则Sl －Sk= ak+1+ ak+2+…+ al ≡0 mod m例6 设a 1, a 2, a3是任意三个整数，b1 b2 b3为a1, a2, a3的任一排列，则a1－b1, a2－b2 ,a3－b3中至少有一个是偶数．证 由鸽巢原理：a1, a2, a3至少有两个奇偶性相同．则这３个数被２除的余数至少有两个是相同的，不妨设为x; 同样b1, b2, b3中被２除的余数也至少有２个x ．这样a1－b1, a2－b2 , a3－b3被２除的余数至少有一个为０．例7 设a 1, a 2,…, a100是由数字1和２组成的序列, 已知从其任一数开始的顺序10个数的和不超过16．即ai+ ai+1+…+ ai+9≤16，1≤i ≤91。

组合数学例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。

问共有多少种不同的安全状态?解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。

用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。

这种对应显然是一对一的。

因此，安全状态的总数等于这8个数的全排列总数8!＝40320。

例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。

证明n 偶数。

证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。

根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。

例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。

证 设n +1个数是a 1, a 2, ···, an +1。

每个数去掉一切2的因子，直至剩下一个奇数为止。

组成序列r 1, r 2,, ···, rn +1。

这n +1个数仍在[1 , 2n ]中，且都是奇数。

而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。

若ai ＞aj ，则ai 是aj 的倍数。

例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k<l ≤m ，使得和ak+1+ ak +2+ ···+ al 是m 的倍数。

证 设Sh = , Sh ≡rh mod m, 0≤rh ≤m -1，h = 1 , 2 , ···, m . 若存在l , Sl ≡0 mod m 则命题成立．否则，1≤rh ≤m -1．但h = 1 , 2 , ···,m ．由 鸽巢原理，故存在rk= rl , 即Sk ≡Sl mod m ，不妨设l ＞k ．则Sl －Sk= ak+1+ ak+2+…+ al ≡0 mod m例6 设a 1, a 2, a3是任意三个整数，b1 b2 b3为a1, a2, a3的任一排列，则a1－b1, a2－b2 ,a3－b3中至少有一个是偶数．证 由鸽巢原理：a1, a2, a3至少有两个奇偶性相同．则这３个数被２除的余数至少有两个是相同的，不妨设为x; 同样b1, b2, b3中被２除的余数也至少有２个x ．这样a1－b1, a2－b2 , a3－b3被２除的余数至少有一个为０．例7 设a 1, a 2,…, a100是由数字1和２组成的序列, 已知从其任一数开始的顺序10个数的和不超过16．即ai+ ai+1+…+ ai+9≤16，1≤i ≤91。

测试题——组合数学一、选择题1. 把101本书分给10名学生，则下列说法正确的是（）A.有一名学生分得11本书B.至少有一名学生分得11本书C.至多有一名学生分得11本书D.有一名学生分得至少11本书2. 8人排队上车，其中A ，B 两人之间恰好有4人，则不同的排列方法是（）A.!63⨯B.!64⨯C.!66⨯D.!68⨯3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）A.()4,11!10P ⨯B.()4,9!10P ⨯C.()4,10!10P ⨯D.!3!14-4. 把10个人分成两组，每组5人，共有多少种方法（）A.⎪⎪⎭⎫ ⎝⎛510B.⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛510510 C.⎪⎪⎭⎫ ⎝⎛49 D.⎪⎪⎭⎫ ⎝⎛⨯⎪⎪⎭⎫ ⎝⎛4949 5. 设x,y 均为正整数且20≤+y x ，则这样的有序数对()y x ,共有（）个A.190B.200C.210D.2206. 仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（）A.128B.252C.343D.1927. 百位数字不是1且各位数字互异的三位数的个数为（）A.576B.504C.720D.3368. 设n 为正整数，则∑=⎪⎪⎭⎫ ⎝⎛nk k n 02等于（）A.n 2B.12-nC.n n 2⋅D.12-⋅n n9. 设n 为正整数，则()k k n k k n 310⎪⎪⎭⎫ ⎝⎛-∑=的值是（） A.n 2 B.n2- C.()n 2- D.0 10.设n 为正整数，则当2≥n 时，∑=⎪⎪⎭⎫ ⎝⎛-nk k k 22=()A.⎪⎪⎭⎫ ⎝⎛3nB.⎪⎪⎭⎫ ⎝⎛+21nC.⎪⎪⎭⎫ ⎝⎛+31nD.22+⎪⎪⎭⎫ ⎝⎛n11.()632132x x x +-中23231x x x 的系数是（）A.1440B.-1440C.0D.1 12.在1和610之间只由数字1，2或3构成的整数个数为（） A.2136- B.2336- C.2137- D.2337- 13.在1和300之间的整数中能被3或5整除的整数共有（）个A.100B.120C.140D.16014.已知(){}o n n f ≥是Fibonacci 数列且()()348,217==f f ，则()=10f （） A.89B.110C.144D.28815.递推关系3143---=n n n a a a 的特征方程是（）A.0432=+-x xB.0432=-+x xC.04323=+-x xD.04323=-+x x16.已知()⋯⋯=⨯+=,2,1,0232n a n n ，则当2≥n 时，=n a （） A.2123--+n n a a B.2123---n n a aC.2123--+-n n a aD.2123----n n a a17.递推关系()⎩⎨⎧=≥+=-312201a n a a n n n 的解为（）A.32+⨯=n n n aB.()221+⨯+=nn n a C.()122+⨯+=n n n a D.()n n n a 23⨯+=18.设()⋯⋯=⨯=,2,1,025n a nn ，则数列{}0≥n n a 的常生成函数是（） A.x 215- B.()2215x - C.()x 215- D.()2215x - 19.把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（）种A.45B.36C.28D.2020.多重集{}b a S ⋅⋅=4,2的5-排列数为（）A.5B.10C.15D.2021.部分数为3且没有等于1的部分的15-分拆的个数为（）A.10B.11C.12D.1322.设n,k 都是正整数，以()n P k 表示部分数为k 的n-分拆的个数，则()116P 的值是（）A.6B.7C.8D.923.设A ，B ，C 是实数且对任意正整数n 都有⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅=1233n C n B n A n，则B 的值是（） A.9B.8C.7D.624.不定方程1722321=++x x x 的正整数解的个数是（）A.26B.28C.30D.3225.已知数列{}0≥n n a 的指数生成函数是()()t t e e t E521⋅-=，则该数列的通项公式是（） A.n n n n a 567++= B.n n n n a 567+-=C.n n n n a 5627+⨯+=D.nn n n a 5627+⨯-= 二、填空题1. 在1和2000之间能被6整除但不能被15整除的正整数共有_________个2. 用红、黄、蓝、黑4种颜色去图n ⨯1棋盘，每个方格涂一种颜色，则使得被涂成红色的方格数是奇数的涂色方法共有_______种3. 已知递归推关系()31243321≥-+=---n a a a a n n n n 的一个特征根为2，则其通解为___________4. 把()3≥n n 个人分到3个不同的房间，每个房间至少1人的分法数为__________5. 棋盘⨯⨯⨯⨯⨯⨯⨯的车多项式为___________ 6.由5个字母a,b,c,d,e 作成的6次齐次式最多可以有_________个不同类的项。