姓名 学号 评分
一、填空题（每小题3分，共18分）
1、红、黄、蓝、白4个球在桌上排种排法。成一圈，有
2、设P、Q为集合，则|P∪Q| |P| + |Q|.
3、 。
4. 366个人中必有 个人生日相同。
5. 。
6.解常系数线性齐次递推关系的常用方法称为 法 。
二、单项选择题（每小题2分，共12分）
1、数值函数f = (1,1,1,...)的生成函数F(x) =（ ）
A、(1+x)n B、1－x C、(1－x)－1 D、(1+x)－n
2、递推关系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.
3、由6颗不同颜色的珠子可以做成 （ ）种手链。
A、720 B、120 C、60 D、6
4、（ ）。
A、2n B、0 C、n2n－1 D、1
5、设F(x),G(x)分别是f和g的生成函数，则以下不成立的是（ ） 。
A、F(x)+G(x) 是f+g的生成函数 B、F(x)G(x) 是fg的生成函数
C、xrF(x) 是Sr(f)的生成函数 D、F(x)－xF(x) 是 f的生成函数.
6、在无柄茶杯的四周画上四种不同的图案，共有（ ）种画法。
A、24 B、12 C、6 D、3
三、解答题（每小题10分，共70分）
1.有4个相同的红球，5个相同的白球，那么这9个球有多少种不同的排列方式？
2.公司有5台电视机，4台洗衣机，7台冰箱，现要把其中3台电视机，2台洗衣机，4台冰箱选送到展销会，试问有多少种选法？
3.设S = {1, 3 2, 3 3, 2 4, 5}是一个多重集，那么由集合S的元素能组成多少个不同的四位数。
4.试求在1到300之间那些不能被3, 5和7中任何一个整除的整数个数。
5. 解非齐次递推关系
6. 将字母a,b,c,d,e,f,g排成一行，使得模式beg和cad都不出现的排列总数是多少？
7. 某次会议有10个代表参加，每一位代表至少认识其余9位中的一位，则10位代表中至少有两位代表认识的人数相等。
《组合数学》试题参
一、填空题（每小题3分，共18分）
1、6； 2、≤； 3、； 4、2； 5、60； 6、特征方程；
二、单项选择题（每小题2分，共12分）
1、C ； 2、B ；3、C ； 4、B ； 5、B ；6、C ；
三、解答题（每小题10分，共70分）
1.解：设有限多重集S = {4 红球，5 白球}，
则9-重复排列数为：
= 126.
即9个球有126种不同的排列方式.
2.解：
由乘法法则得，
3.解：从多重集{1, 3 2, 3 3, 2 4, 5}产生
无重复的四位数有：个；
有1个2-重复的四位数有：个；
有2个2-重复的四位数有：个；
有1个3-重复的四位数有：个；
共有120 + 216 + 18 + 32 = 386个四位数。
4. 解：令A1,A2和A3分别表示1到300之间能被3, 5和7整除的整数集合，则有
根据容斥原理知：
5. 解：特征方程为：x2 + 6x + 9 = 0
解得特征根为- 3, - 3. 因此齐次通解
(A + Br) (-3) r
设非齐次的特解为 C , 代入递推关系式有
C + 6C + 9C = 3
所以特解为
非齐次的通解
为一般解，由边界条件得
解此线性方程组得唯一解
因此所求的解为
6 . 解：仅有beg模式，或cad模式的排列数都是P(5,5)=5!(将模式捆在一起视为一个元素，再和其余4个元素构成5个元素的全排列)。即有beg模式又有cad模式出现的排列数为3。根据容斥原理，符合题意的排列数是
7！－2×5！＋3！＝4 806
7. 解：10位代表认识的人数有1、2、3、4、5、6、7、8、9，共九种情况（抽屉），根据抽屉原理： 10个代表中至少有两位代表认识的人数相等。下载本文
