组合数学期末考试样卷
一、选择题：10?3?
1、集合A={a1,a2,…,a10}的非空真子集的个数为（ ）。
A、1022 B、1023 C、1024 D、1021
2、设(x,y)满足条件x+y?10，则有序正整数对(x,y)的个数为( ).
A.100 B.81 C.50 D.45 3、设A,B,C均是有限集，则|A?C?B|=( ).
A.|A|?|C|?|B| B.|A|?|C|?|A?B?C| C. |A|?|C|?|A?C|?|B?C|
D. |A|?|C|?|A?C|?|A?B|?|C?B|?|A?B?C|
4、在1至100的整数中，有多少整数能被3整除，但不能被2也不能被5整除？（ ）
A.23 B.13 C.9 D.14
5、排列26个字母，使得c ，d之间恰有8个方式数是（ ）。 A.2??24,8???17,17? B.??26,9???17,17? C.??26,7???17,17? D??16,8???17,17? 6、今有12只鸽子飞进5个笼子，则必有有一个笼子，该笼子里至少有（ ）只鸽子。
A、3 B、2 C、4 D、1
7、有4个相同的红球，5个相同的白球，那么这9个球有（ ）种不同的排列方式
Ａ、63 Ｂ、126 Ｃ、252 Ｄ、378 8、求?x0?3x1?2x2?x3?中x0x1x2项的系数是（ ）。
623A.2450 B.60 C.3240 D.3460
9、递推关系f(n) = 4f(n－1)－4f(n－2)的特征方程有重根2，则（ ）是它的一般解 。
A、C12n－1+C22n B、(C1+C2n)2n C、C(1+n)2n D、C12n+C22n.
10、用数字1，2，3，4（数字可重复使用）可组成多少个含奇数个1、偶数个2且至少含一个3的n(n>1)位数（ ）
4n?3n?14n?2n?14n?3n???1?4n?3n???1?A、 B、 C、 D、
4343nn二、填空题：5?3?
11、n元集到m元集满射个数为 。
12、由初始条件f(0)?1，f(1)?1及递推关系（ ）
确定的数列{f(n)}n??0}叫做Fibonacci数列。
13、计算p4?12?? 14、计算S1?10,9?= 15、求把12件相同的物件分给4个人，使得每人至少分得一件物件的不同方法数
三、计算题。7?5?
1、某校甲班有学生60名，24名学生喜欢数学，28名学生喜欢物理，26名学生喜欢化学，10名学生既喜欢数学又喜欢物理，8名学生既喜欢数学又喜欢化学，14名学生既喜欢物理又喜欢化学，6名学生对这三门功课都喜欢，问有多少学生对这三门课都不喜欢？
2、设f(n)?n?4n，求?kf(n) ?k?1?。
3、求Fibonacci数f(20)
4、解下列递推关系：
?an?5an?1?6an?2 （n?2) ?a?4,a?901?
5、解下列递推关系：
?an?5an?1?8an?2?4an?3, ?a?2,a?3,a?7.(n?3)13?0
6、计算题
n??6?n?1?12?n?2?8?n?3求{?的解? ?0?1,?1??2,?2?8
7、求x1?2x2?4x3?28的正整数解的个数。
四、证明题：2?10?
?n?1、证明：?(k?1)2???2n?2(n2?5n?4)
k?0?k?n
2、证明题
s2?n?1,k?
答案： 1、A
?n?????s2?j,k?1?
j?0?j?n2、D解析：设所求为N.因为满足条件x?y?10，且x=k(1?k?9)的有序正整数对
(x，y)有10-k个，故由加法原则，有
N??(10?k)?9?8?…?2?1?k?1910(10?1)?45 2|A?C?B|?|A?C|?|(A?C)?B|?|A?C|?|(A?B)?(C?B)|3、D解析：
?|A|?|C|?|A?C|?|A?B|?|C?B|?|A?B?C|4、D解析：此题只要考查容斥原理的符号形式，S中同时满足a1,a2,....,ak,但不
??满足ak?1,....,an的元素个数：N(a1...akak?1...an)?N(a1...ak(1?ak?1)...(1?an))。这
k?里要与S中同时满足的m个性质的元素个数区别开来，N(m)??(?1)k?m??m?Nk ??k?m??所以，所求个数为N(a1a2a3)?N(a1(1?a2)(1?a3))
n ?N(a1?a1a2?a1a3?a1a2a3)
=N(a1)?N(a1a2)?N(a1a3)?N(a1a2a3)
?100??100??100??100? =? ???????????3??3?2??3?5??2?3?5? ?33?16?6?3 =14 5、A
?m?1??12?1?6、解析：由鸽笼原理：??1??1?3，选择A ????n??5?7、解析：B解析：设有限多重集S = {4?红球，5?白球}，
则9-重复排列数为：
9!= 126. 4!5!即9个球有126种不同的排列方式
6!?3240.答案为C。 8、解：33?22!3!9、B 10
、
A
，
解
析
；
由
指
数
生
成
定
理
?tt3??t2??tt2??tt2?e4t?e3t?e?t A?t????1!?3!??????1?2!??????1!?2!??????1?1!?2!?????4????????ntn1nntn=?4?3???1?，的系数即为所求。
n!4n!n?0???11、答案：m!s2(n,m)
12、f（n）=f（n-1）+f (n-2) (n>=2)
13、解析：p4?12???pk?12??p1?8??p2?8??p3?8??p4?8?
k?14 ?p1?8??p2?8???pk?5???pk?4??1?4?5?5?15
k?1k?134?n??10?14、根据定理s1?n,n?1?????=s1?10,9?????=-45即可得到
?2??2?15、165．
三、计算题：
1、解：设60名学生集合为A，令a1,a2和a3分别表示一名学生喜欢数学、物理和化学这一性质。令Ai(i?1,2,3)是A中具有性质ai的学生所组成的集合。于是对这三门课都不喜欢的学生人数为
N?A1?A2?A3
?A?A1?A2?A3
?A?(A1?A2?A3)?(A1?A2?A1?A3?A2?A3)?A1?A2?A3 而A?60,A1?24,A2?28,A3?26,A1?A2?10,A1?A3?8,
A2?A3?14,A1?A2?A3?6
所以，N?60?(24?28?26)?(10?8?14)?6?8 2、解：?f(n)?f(n?1)?f(n)?(n?1)4n?1?n4n?4n(3n?4)
?2f(n)??f(n?1)??f(n)?4n?1(3n?4?1)?4n(3n?4)?4n(32n?42) 设?sf(n)?4n(3sn?4s)，则
?s?1f(n)??(?sf(n))??sf(n?1)??sf(n)?4n?1(3n?4)?4(3n?4)?4(3ssnssns?1n?4s?1)
由数学归纳法可知
?kf(n)??k?1f(n?1)??k?1f(n)?4n(3kn?4k) 3、解：因为f(3)?3，f(4)?5，f(5)?8，
f(20)?f(10?10)
=f(10)f(10)?f(9)f(9) f(10)?f(5?5)=f(5)f(5)?f(4)f(4) ?8?8?5?5?89
f(9)?f(5?4)=f(5)f(4)?f(4)f(3)
?8?5?5?3?55
所以f(20)?89?89?55?55?7921?3025?10946