《组合数学》模拟练习题
四年级美术教案-百度下吧
《组合数学》模拟练习题
组合数学模拟练习题04
一、 填空题
1、
红、黄、蓝、白4个球在桌上排成一圈，有
种排法。
2、设P、Q为集合，则|P∪Q| |P| + |Q|.
n
3、
max
。
i
0in
4、设S =
{1,2,3,4}中仅有2个定位的排列数
N(2) = 。
5、依照字典序，排列(4576321)的下一个排列
是
。
6.
n
1.
k0
k
n
。
7
7.
2,0,1,3,1
.
8. 366个人中必有 个人生日相同。
9、
(1,2,3,4)的移位排列数D(4)
。
10、解递推关系 f (r) – 4f (r-1) + 4f (r-2) = 2
r
时，应设非齐次的特解
为
。
6
11.
4
23x
2
x
3
x
4
的系数为
x
i
的展开式中，
i1
。
12. 在14个人中至少有 个人为同月份
出生。
13.
解常系数线性齐次递推关系的常用方法称
为 法 。
14.
记移位排列数为D(n)，则r定位排列数N(r)
= 。
15.数值函数的推迟函数
k
S
(f)=
。
二、 单项选择题
1、数值函数f = (1,1,1,...)的生成函数F(x)
=（ ）
A、(1+x) B、1－x C、(1－x)
D、
(1+x)
－
n
n
－
1
2、递推关系f(n) =
4f(n－1)－4f(n－2)的特征方
程有重根2，则（ ）是它的一般解 。
A
、C
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
.
3、由6颗不同颜色的珠子可以做成 （ ）种
手链。
A、720 B、120 C、60
D、6
4、
(1)
k0
n
k
n
k
（ ）。
A、2
n
B、0
C、n2
n－1
D、
1
5、按照字典序，排列4517632的下一个排列是
( ).
A、4571236 B、4517623 C、4576321
D、4521367
6、当r≥k时差分多项式P
k
(r) =（ ）
r
C、r(r－1)...(r－k+1) A、0 B、
k
D、
k
1
!
7、设F(x),G(x)分别是f和g的生成函数，则以
下不成立的是（
） 。
A、F(x)+G(x) 是f+g的生成函数
B、F(x)G(x)
是fg的生成函数
C、x
r
F(x) 是S
r
(f)的生成函数
D、F(x)－xF(x)
是f的生成函数.
8、在无柄茶杯的四周画上四种不同的图案，共
有（ ）种画法。
A、24
B、12 C、6
D、3
n
（ ）9、
k
。
k
k1
n
A、2
n
B、0 C、n2
n
－
1
D、1
10、设S={1,2,3,4,5,6,7}，5-组合12367的下一个
组合是 (
).
A、12567 B、12376 C、12467
D、
12456
三、 解答题
1.
有4个相同的红球，5个相同的白球，那么这
9个球有多少种不同的排列方式？
2. 公司有5台电视机，4台洗衣机，7台冰箱，
现要把其中3台
电视机，2台洗衣机，4台冰
箱选送到展销会，试问有多少种选法？
3. 设S = {1,
3•2, 3•3, 2•4, 5}是一个多重集，那么
由集合S的元素能组成多少个不同的四位数。
4.
用09这十个数码，可以组成多少个恰有两个重复数码的三位数？
5. 设S ={a, b, c, d, e}，求S的所有3－组合(按
字典序排列)。
6. 设集合S ={1, 2, 3,
4}，按照字典序写出排列
3124后的所有全排列。
7.
试求在1到300之间那些不能被3, 5和7中
任何一个整除的整数个数。
8. 数1,
2, 3, 4, 5, 6, 7,
8的全排列中，有
4个数字在原来位置上，另外4个不在原来位置
上的错排数目。
9. 一人在8小时内加工了40个零件，已知他在
第一个小时内加工了6个零件，而最后一个
小时
内加工了4个零件。证明一定存在连续的两个小
时，这两个小时内至少加工了10个零件。
10. 证明在边长为2的正方形内任意5点必有两
点，其距离不超过
2
。
11. 设数值函数f = {1,7,7
2
,7
3
,...},
g =
{1,6,6
2
,6
3
,...}, 求卷积f *
g的生成函数。
12. 用生成函数求下式之和：
n
n<
br>
n
n
1
2
3
L
n
1
2
3
n
13.
解非齐次递推关系
a
n
6a
n1
9a
n
2
3,n2
a
0
0,a
1
1
14. 解齐次递推关系
a
n
8a
n
1
16a
n2
0
a
0
1,
a
1
0
15.一教室有两排座位，每排8个，今有14名学
生，
5人总坐在前排，4人总在后排，问学生入
座有几种方式？
16.
将字母a,b,c,d,e,f,g排成一行，使得模式beg
和cad都不出现的排列总数是多少？
17. 按照字典序写出集合S ={1,2,3,4}的前面
12个全排列。
18. 求8个字母A、B、C、D、E、F、G、H的
全排列中只有4个元素不在原来位置上
的排列
数。
19. 某次会议有10个代表参加，每一位代表至
少认识其余9位中的
一位，则10位代表中至少
有两位代表认识的人数相等。
20.
求数值函数f =
{1,－3,3
2
,－3
3
,...}的生成函
数.
21. 设初始值h(0) = 0, h(1) = 1，求解递推关系
h(n) =
5h(n－1)－6h(n－2). (n = 2,3,...)
组合数学模拟练习题参考答案
一、 填空题
1、6； 2、≤；
3、
5、4612357.
6、2
n
； 7、420； 8、2；
9、9 ；
10、
p2
0
r
n
n
2
； 4、6 ；
p
1
r2
r
p<
br>2
r
2
2
r
11、60； 12、2；
13、特征方程； 14、
n
D(nr)
nr
；
0rk1
rk
0
15、
f(rk)
.
二、 单项选择题
1、C ； 2、B ；3、C ； 4、B ； 5、D ；
6、B ； 7、B
；8、C ； 9、C ； 10、D ；
三、 解答题
1. 解：设有限多重集S = {4•红球，5•白球}，
则9-重复排列数为：
9!
4!5!
= 126.
即9个球有126种不同的排列方式.
2. 解：
5
4
7
电视机有
种选法；洗衣机有
种选法；冰箱有
种
选法.
3
2
4
由乘法法则得，
5
4
7
<
br>共有
2100种选法.
3
2
4
3.
解：从多重集{1, 3•2, 3•3, 2•4, 5}产生
无重复的四位数有：
P
个；
4
5
有1个2-重复的四位数
有：
3
4
4!
1
2
2!
个；
3
4!
有2个2-重复的四位数有：
2
2!2!
个； <
br>
2
4
4!
有1个3-重复的四位数有：<
br>
1
1
3!
个；
共有120 + 216 + 18 + 32 = 386个四位数。
9
9
4. 解：
第1,2位重复有
1
1
;
9
9
第1,3位重复有
;
1
1
9
9
第
2,3位重复有
;
1
1
9
9
共有3
243个重复数码的三位数.
1
1
5. 解：S ={a, b, c, d,
e}，按组合生成算法S的所
有3－组合：
abc－>abd－>abe－>acd－>ac
e－>ade
－>bcd－>bce－>bde－>cde
6.
解：按照字典序排列算法，集合S ={1, 2, 3,
4}的3124后全排列为：
3124－>3142－>3214－>3241－>3412
－>3421
－>4123－>4132－>4213－>4231－>4312
－>4321
7. 解：令A
1
,A
2
和A
3
分别表示1到30
0之间能被
3, 5和7整除的整数集合，则有
300
30
0
300
|A
1
|
100,
|A|60,|A|42,
23
3
5
7
300
300
300
|A
1
A
2
|<
br>
20,|AA|14,|AA|8
1323
353757
300
|A
1A
2
A
3
|
2
357
根据容斥原理知：
|A
1
A
2
A
3
|300(1006042)(20148)2
138.
8. 解：求8个数字全排列中只有4个数字不在
原来位置上，其余4个数字保持不动，相当
于4个数字的移位排列，其数目为：
11
11111
)24()
1!2!3!4!2624
12419.
(8分)
D(4)4!(1
故8个数字的全排列中只有4个数字不在原来
位置上的排列数为
8
D(4)
8!
9
8765
3630
4
4!4!42
9. 解：去掉首尾两个小时，在其余6个小时内
加工了30个零件,把这6个小时分成3个“
连续
的两个小时”（抽屉），根据抽屉原理：一定存在
连续的两个小时，这两个小时内至少加工
了10
个零件。
10. 解：把边长为2的正方形，分成4个边
长为
1的小正方形，这4个小正方形组成4个抽屉，
根据抽屉原理：正方形内任意5点必有两点
落入
一个小正方形内，而小正方形内两点间距离不超
过
2
(对角线长)，所以
正方形内必有两点，其距
离不超过
2
。
11. 解：数值函数f =
{1,7,7,7,...}的生成函
数
23
F(x)
17x7
2
x
2
7
3
x
3
...
1(7x)(7x)
2
(7x)
3
...
1.(|7x|1)
17x
数值函数f =
{1,6,6
2
,6
3
,...}的生成函数
F(x)16x
6
2
x
2
6
3
x
3
...
1(6x)(6x)
2
(6x)
3
...
1
.
(|6x|1)
16x
1
所以卷积 f * g
的生成函数为
(16x)(1
.
7x)
12.
解：设数值函数
n
n
n
n
f{
,
,
,
,
L
0
1
2
3
n
,
}
n
其生成函数
n
n
n
n
n
F(x)
x
x
2
x
3<
br>
L
x
n
(1x)
n
0
1
2
3
n<
br>
两边对x求导
n
n
n
n
F
(x)
2
x3
x
2
L
n
x
n1
n(1x)
n1
1
<
br>2
3
n
令 x = 1 得
n
n
n
n
n1
1
2
2
3<
br>
3
L
n
n
n2
13. 解：特征方程为：x
2
+ 6x + 9 = 0
解得特征根为- 3, - 3. 因此齐次通解
(A + Br) (-3)
r
设非齐次的特解为 C , 代入递推关系式有
C + 6C + 9C = 3
所以特解为
C
3
16
3
16
非齐次的通解
a
r
(ABr)(3)
r
为一般解，由边界条件得
3
A0
16
(AB)(3)
3
1
16
解此线性方程组得唯一解
31
A
16
,B
12
因此所求的解为
a<
br>r
313
(3)
r
r(3)
r
161216
14.
解：特征方程为：x
2
－8x + 16 = 0
解得特征根为4, 4.因此
a
r
= (A + Br)4
r
为一般解，由边界条件得
A1
(AB)40
解此线性方程组得唯一解
A = －1, B = 1
a
r
因此所求的解为
(1r)4
r
15. 解：由5人总坐在前排，在前排选5个座位，
有C
8
5
5!种坐法；
由4人总坐在后排，在后排选4个座位，有
C
8
4
4!种坐法；
在余下的7个座位中选5个座位，给余下的
5人坐，有C
7
5
5!种坐法；
所以学生入座共有C
8
5
5!
C
8
4
4! C
7
5
5! = 28
449
792 000种方式.
16 . 解：仅有beg模式，或cad模式的排列数都
是P(5,5)=5!(将模式捆在一起视为一个元素，再
和其余4个元素构成5个元素的全排列)。
即有
beg模式又有cad模式出现的排列数为3！。根据
容斥原理，符合题意的排列数是
7！－2×5！＋3！＝4 806
17. 解：按照字典序排列算法，集合S ={1,2,3,4}
的前面12个全排列为：
1234－>1243－>1324－>1342－>1423
－>1432
－>2134－>2143－>2314－>2341－>2413
－>2431.
18. 解：求8个字母全排列中只有4个元素不在
原来位置上，其余4个字母保持不同，相当
于4
个字母的移位排列，其数目为：
1111111
)24()
1!2!3!4!2624
12419.
D(4)4!
(1
故8个字母的全排列中只有4个元素不在原来
位置上的排列数为 8
D(4)
8!
9
8765
3630
4
4!4!42
19. 解：10位代表认识的人数有1、2、3、4、5、
6、7、8、9，共九种情况（抽
屉），根据抽屉原
理： 10个代表中至少有两位代表认识的人数相
等。
20.
解：数值函数f =
{1,－3,3
2
,－3
3
,...}的生成函
数
F(x
)13x3
2
x
2
3
3
x
3
.
..
1(3x)(3x)
2
(3x)
3
...
1
.(|3x|1)
13x
21.
解：特征方程为：x
2
－5x+6 = 0
解得特征根为2, 3.因此
h(n) = A2
n
+ B3
n
为一般解，由边界条件得
AB0
2A3B1
解此线性方程组得唯一解
A = －1, B = 1
因此所求的解为
h(n) = 3
n
－2
n
.