拱手让人-货代考试

组合数学期末考试样卷

一、选择题：10
3


1、集合A={
a
1
,a
2
,…,a
10
}的非空真子集的个数为（ ）。
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< br>
24,8



17,17

B.

26,9



17,17

C.


26,7



17,17
< br> 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、求

x
0
3x
1
2x
2
x
3

中
x
0
x
1
x2
项的系数是（ ）。
6
23
A.2450 B.60 C.3240 D.3460
9、递推关系f(n) = 4f(n－1)－4f(n－2)的特征方程有重根2，则（ ）是它的一般
解 。
A、C< br>1
2
n
－
1
+C
2
2
n
B、(C
1
+C
2
n)2
n
C、C(1+n)2
n
D、C
1
2
n
+C
2
2
n
.
1 0、用数字1，2，3，4（数字可重复使用）可组成多少个含奇数个1、偶数个2
且至少含一个3的n (n>1)位数（ ）
4
n
3
n
14
n
 2
n
1
4
n
3
n


1< br>
4
n
3
n


1

A、
B、 C、 D、
43
43
nn

二、填空题：5
3


11、n元集到m元集满射个数为 。
12、
由初始条件
f(0)1
，
f(1)1
及递推 关系（ ）
确定的数列
{f(n)}
n0
}叫做
Fibonacci
数列。

13、计算
p
4

12



14、计算
S
1

10,9

=
15、求把12件相同的物件分给4个人，使得每人至少分得一件物件的不同方法
数

三、计算题。7
5


1、某校甲班有学生60名，2 4名学生喜欢数学，28名学生喜欢物理，26名学生
喜欢化学，10名学生既喜欢数学又喜欢物理，8 名学生既喜欢数学又喜欢化学，
14名学生既喜欢物理又喜欢化学，6名学生对这三门功课都喜欢，问有 多少学生
对这三门课都不喜欢？

2、设
f(n)n4
n，求

k
f(n)


k1

。

3、
求
Fibonacci
数
f(20)


4、解下列递推关系：

a
n
5a
n1
6a
n2

（n2)


a4,a9
01


5、解下列递推关系：

a
n
5a
n1
8 a
n2
4a
n3
,


a2,a3,a7.(n3)
13

0

6、计算题
n
6

n1
12

n2
8

n3
求{

的解?

< br>0
1,

1
2,

2
8

7、求
x
1
2x
2
4x
3
28的正整数解的个数。

四、证明题：2
10



n

1、证明：

(k1)
2

2
n2
(n
2
5n4)

k0

k

n

2、
证明题
s
2

n1,k












答案：
1、A

n




s
2

j,k1


j0

j

n
2、D解 析：设所求为N.因为满足条件
xy10
，且x=k(
1k9
)的有 序正整
数对
(x，y)有10-k个，故由加法原则，有
N

(10k)98…21
k1
9
10(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中同时满足
a
1
,a
2
,....,a
k
,
但不

满足
a
k1
,....,a
n
的元素个数：
N(a
1
...a
k
a
k1
...a
n
)N(a
1...a
k
(1a
k1
)...(1a
n
))< br>。这
k

里要与S中同时满足的m个性质的元素个数区别开来，
N(m )

(1)
km


m

N
k


km

所以，所求个数为
N(a
1
a
2
a
3
)N(a
1
(1a
2
)(1a
3
))

n

N(a
1
a
1
a
2
a
1
a
3
a
1
a
2
a
3
)

=
N(a
1
)N(a
1
a
2
)N(a
1
a
3< br>)N(a
1
a
2
a
3
)

100

100

100

100
< br> =









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、解：
3
3
2
2!3!
9、B
10、A，解析；由指 数生成定理

tt
3

t
2

tt< br>2

tt
2

e
4t
e
3t< br>e
t

A

t




1!

3!





1
2!





1!

2!< br>




1
1!

2!



4

n
t
n
1
n
n
t
n
=

43
< br>1

，的系数即为所求。
n!
4n!
n0
< br>
11、答案：
m!s
2
(n,m)

12、f（n）=f（n-1）+f (n-2) (n>=2)
13、解析：
p
4

12



p
k

12

p
1

8

p
2
< br>8

p
3

8

p
4

8


k1
4

p
1

8

p
2

8



p
k

5



p
k

4

145515

k1k 1
34

n


10

14、
根据定理
s
1

n,n1



=
s
1

10,9



=-45即可 得到


2


2

15、165．

三、计算题：
1、解：设60名学生集合为A，令
a1
,a
2
和a
3
分别表示一名学生喜欢数学、物理
和化 学这一性质。令
A
i
(i1,2,3)
是A中具有性质
a
i
的学生所组成的集合。于是
对这三门课都不喜欢的学生人数为
NA
1
A
2
A
3

AA
1
A
2
A
3

A(A< br>1
A
2
A
3
)(A
1
A
2
A
1
A
3
A
2
A
3
) A
1
A
2
A
3

而
A60,A1
24,A
2
28,A
3
26,A
1
 A
2
10,A
1
A
3
8,

A2
A
3
14,A
1
A
2
A
3
6

所以，
N60(242826)(10814)68

2 、解：
f(n)f(n1)f(n)(n1)4
n1
n4
n
4
n
(3n4)


2
f(n)f(n 1)f(n)4
n1
(3n41)4
n
(3n4)4n
(3
2
n4
2
)

设

s
f(n)4
n
(3
s
n4
s
)
，则

s1
f(n)(
s
f(n))
s
f (n1)
s
f(n)
4
n1
(3n4)4(3n4 )4(3
ssnssns1
n4
s1
)

由数学归纳法可知

k
f(n)
k1
f(n1) 
k1
f(n)4
n
(3
k
n4
k
)

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

4、解：对应的特征方程为：
x
2
5x60

特征根分别：
x
1
2,

x
2
3


原递推关系的通解为：
a
n
c
1
2
n
c
2
3
n

把
a
0
4
，
a
1
9
代入

c
1
c
2
4


2c3 c9
2

1

c
1
3
解得：


c1

2

原递推关系的通解为：
a
n
32
n
3
n

5、解：对应特征方程为
x
3
5x
2
8x40,
特征根分别为
x
1
1,x
2,3
2.
故原递推
关系通解为
a
n< br>c
1
c
2
2
n
c
3
n 2
n
,
将
a
0
2,a
1
3,a
2
7
代入通解得

c
1
c
2
2


c
1
2c
2
2c
3
3


c4c4c7
23

1
c
1
3


c
2
1


c1

3
a
n
3(1)2
n
n2
n
3(n1)2
n

(n0,1,2,)

（解析：该题考查第三章第二节“递推关系”中的第四点“ 特征方程有重根的常
系数线性齐次递推关系的解法”中 定理3.15
“设递推关系有
t
个相异的特征根
q
1
,q
2
,

,q
i
，其中
q
i

i
1,2,,
t
是
e
i
重根，令
h
i

n

c
i1
c
i2
nc
i3
n
2< br>c
ie
i
n
e
i
1


i1,2,,t

,
其中
c
i1
,c
i2
,

,c
ie
i
是任意常数，
n
则递 推关系的通解为
u
n
h
1

n

q1
n
h
2

n

q
2
”学 生做题时能够灵活应
h
t

n

q
t
n
。
用该定理就可以顺利解决此题。此题难度适中。而且此题出之于课本第三章习题
第111页作业：第20题第（1）题。）
6、解：对应的特征方程为

3
6

2
1280
，
特征根为

1,2,3
2
，
nnn

原递推关系的通解为

n
c
1

2

c
2
n

2

c
3
n
2

2


把

0
1,
2
2,

3
8
代入通解,得

C
1


2C
1
2C
2
2C
3
2


4C
1
8C
2
16C
3
8

11
C
1
1,C
2
,C
3


22

nn
2

特解：

n
< br>
2



1
2

2




n
7、解：
A
(
t)

(
tt
2

)(
t
2
t
4

)(
t
4
t
8

)


t
7
(1
tt
2
)(1
t
2
t
4

)(1
t
4
t
8

)

t
7

24
(1t)(1t)(1t)
t
7
(1t)


(1t
2
)
2
(1t
4
)
t7
(1t)(1t
2
)
2


43
(1t)

3k1

4k
(tt2t2ttt )



k


t

k0
789101112

由于8+4k=28得k=5,12+4k=28，k =4，其余的得到的k均不为正整数.
故
t
28

351< br>
341

的系数为


5





4


36

 
所以
x
1
2x
2
4x
3
28< br>的正整数解的个数为36.
四、证明题：
n

n
n

n

n

1、证明：左边=

k

2

k




< br>k0

k

k0

k

k0

k

n
2
nn

n

n1

k

n

而

k

n

k

=
n

k

kkk1
n
k0k1

k0
n
2
n

n1

n1


n

(k1)

n




k1

k1

k1

k1

n

n2

n1
=
n(n1)


2n

k2
k2

n

=
n(n1)2
n2
2
n1
n

nnn< br>
n

n1

k

n

kn

n1

n1n
又因为
2

k

2n


=
2n

2n


2n*22n

k0

k
< br>k0
n

k

k0
nk

k 1

k0

k1

n
所以左边
n( n1)2
n2
2
n1
n2
n
n2
n< br>

2
n2
(n
2
n2n4n4)


2
n2
(n
2
5n4)

所以等式成立
2、证明：
证：设A=

a
0
,a
1
a
n

对A的任一k部划分中，除
a
0
外，与
a0
同类的元素为i
个，i=0,1…..n,f方式数为

，剩余n- i个元素，分成k-1类的方式数为
s
2

ni,k1



n


i


n

s
2

n1,k




s2

ni,k1


j0

i

n



n



s
2

ni,k 1


i0

ni

n
n

n




s
2

j,k 1


j0

j
