大学毕业做什么-模板图片

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅

组合数学练习题
第一章 排列组合
1, 在1到10000之间，有多少个每位上数字全不相同而且由偶数构成的整数？
本题分为四种情况:
1位整数有4个: 2, 4, 6, 8
2位整数有4*4种方案, 有16个
3位整数有4*4*3种方案, 有48个
4位整数有4*4*3*2种方案, 有96个
总共有4+16+48+96=164个这样的整数.

2, 一教室有两排，每排9个坐位，今有14名学生，问按下列不同的方式入座，各有多少
种坐法？(1) 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；(2) 要求
前排至少坐5人，后排至少坐4人。
(1) 本问中, 第一排和第二排各有5名和4名同学被确定, 那么14名同学中还有5名同学
没有固定在哪一排, 所以可以根据这5名同学的不同排列来计算, 分5种情况考虑; 1)
从这5名同学中选出4名同学坐在第一排, 这4名和固定的5名同学进行全排列、另
外1名同 学和第二排固定的4名同学进行全排列，以此类推；2) 从5名同学中选出3
名同学坐第一排; 3) 从5名同字中选出2名同学坐第一排; 4) 从5名同学中选出1名
同学坐第一排; 5) 最后5名同学全部坐在第二排; 把这5种情况的坐法安排数全部加
起来就是结果.
C (5,4)*P(9,9)*P(9,5)+C(5,3)*P(9,8)*P(9,6)+C(5,2)*P( 9,7)*P(9,7)+
C(5,1)*P(9,6)*P(9,8)+P(9,5)*P(9,9)
(2) 本问中, 第一排和第二排所坐的同学的数量被确定, 分别是5名和4名, 那么要从14
名同学中把省下的5名同学选出来, 然后再按照坐在不同排的情况进行计算, 同样分5
种情况考虑; 1) 从这5名同学中选出4名同学坐在第一排, 这4名和固定的5名同学< br>进行全排列、另外1名同学和第二排固定的4名同学进行全排列，以此类推；2) 从5
名同学中选出3名同学坐第一排; 3) 从5名同字中选出2名同学坐第一排; 4) 从5名
同学中选出1名同学坐第一排; 5) 最后5名同学全部坐在第二排; 把这5种情况的坐
法安排数全部加起来再乘以从14名同学中任选出5名同学方法的数就是结果. C(14,5)*[P(9,9)*P(9,5)+P(9,8)*P(9,6)+P(9,7)*P(9, 7)+P(9,6)*P(9,8)+ P(9,5)*P(9,9)]

3, n对夫妇, 要求排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，
又有多少种不同的方案？围 一圆桌而坐且要求每对夫妇坐在一起,又有多少种方案?
(1) 本问中, 男女各有n名, 分别进行全排列各有n!种方案, 将他们交叉排列就有(n!)
2
种
方案, 同时男在女前或女在男前又是不同的方案, 所以要乘以2, 所以
方案数为--- 2 (n!)
2

(2) 本问较第一问要去掉变为圆周排列后的重复度, 总的人数为2n, 用第一问的方案数
除以2n, 所以
方案数为--- (n!)
2
n
(3) 本问中, 每对夫妇交换位置坐的方案数为2
n
, 再把每对夫妇看成单个元素进行圆周
全排列, 方案为n!n, 最后把两种方案数相乘, 所以
方案数为--- 2
n
n!n
4, 有16名选手，其中6名只能打后卫，8名只能打前锋，2名能打前锋或后卫，今欲选出
11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？
根据2名既能打前锋也能打后卫选手的不同情况来计算方案

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅

(1) 方法一, 分成6种情况: 1) 这2名选手全部打前锋; 2) 这2名选手全部打后卫; 3) 从
2名选手中选出1名打前锋, 另一名不上场; 4) 从2名选手中选出1名打后卫, 另一
名不上场; 5) 2名选手全部上场, 分别打前锋和后卫; 6) 2名选手全部不上场; 把这些
方案加起来就是全部选法.
C(8,5)*C(6,4)+C(8,7)*C(6,2 )+2C(8,6)*C(6,4)+2C(8,7)*C(6,3)
+C(8,6)*C(6,3)+C(8,7)*C(6,4) = 2800
(2) 方法二, 分成3种情况: 1) 把这2名选手全部加入前锋后选组进行组合; 2) 把这2名
选手合部加入后卫后选组进行组合; 但这两种方案中这2名选手全部不上场的方案
是重复的, 所以要减掉一个2名选全部不上场的方案数; 3) 上面的方案中也包括了2
名选手中只有1名上场的情况, 所以省下只考虑2名选手都上场, 但分别打前锋和后
位的方案; 把这些方案加起来就是全部选法.
C(6,4)*C(10,7)+C(8,4)*C(8,7) -C(8,7)*C(6,4)+ C(6,3) *C(8,6) = 2800

5, 从1到10这10个正整数中每次取 出一个并登记，然后放回，连续取5次，得到一个由
5个数字组成的数列。按这种方式能够得到多少个严 格递减数列？能够得到多少个不减数
列？
(1) C(10,5) = 10!((10-5)!5!) = 252
(2) C(10+5-1,5) = 14!((14-5)!5!) = 2002

6,证明
n1
n2
＝。

kCn,k

n
k1
证明:
将等式左边展开为:
C(n,1)+2C(n,2)+3C(n,3)+…+kC(n,k)+…+ (n-1)C(n,n-1)+nC(n,n)
设这个多项式等于Q
设等式1为Q = Q
将等式1左右两边分别加上下面的等式P:
nC(n,0)+(n-1)C(n,1)+…+C(n,n-1)
得到等式2, 等式右边合并项为: nC(n,0)+nC(n,1)+…+nC(n,n-1)+nC(n,n)
提取公因子n, 等于n[C(n,0)+C(n,1)+…+C(n,n-1)+C(n,n)]
根据定理, 等式右边等于n2
n

由定理C(n,r) = C(n,n-r) 可将P变型为P’:
nC(n,n)+(n-1)C(n,n-1)+…+2C(n, 2)+C(n,1)
P’就等于Q
等式2左边是Q+P, 等于2Q
等式2左右两边同时除以2, 得到等式3: Q = n2
n
2 = n2
n-1

多项式Q就是题目中等式的左项, 所以证明题目中等式左右相等

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅

第二章 母函数与递推关系
1, 设平面内有n条直线两两相交，且无三线共点。问这样的n条直线把平面分割成多少个
不重叠的区域？
解：设集合{a
0
,a
1
,…,a
n
}为本题的解 ，当有0条线的时候，平面只有一个区域，所以a
0
=1，
当有1条直线的时候，平面 被分为2个区域，当有2条线的时候，平面被分为4个区
域，也就是说每增加一条直线，这条直线都会穿 过上次每条线所构成的相邻的区域，
被穿过区域的个数为(n-1)+1个，即n个，所以有下面的递推 关系：
a
n
= a
n-1
+ n 初始条件为：a
0
=1 a
1
=2
先求一般解
设特征方程：X

- 1 = 0 r

= 1
a’
n
= A ×1
n
= A
再求特解, 因为1是特征方程的根, 所以
设特解a*
n
= k
0
n + k
1
n
2
, 代入原特征多项式
a
n
– a
n-1
= k
0
n + k
1
n
2
- k
0(
n-1) - k
1(
n-1)
2
= k
0
+ 2 k
1
n – k
1
= n
可得出k
0
= k
1
= 12
特解为: a*
n
= n2 + n
2
2
一般解为: a
n
= A + n2 + n
2
2
当n=0时，有A = 1
a
n
= 1 + n(n+1)2

2, 求下列递推关系的一般解：

a
n
4a
n1
25
n
,
（1）

；

a
1
2.
解: 先求一般解
设特征方程：X

- 4 = 0 r

= 4
a’
n
= A ×4
n

再求特解, 因为3是特征方程的根, 所以
设特解a*
n
= p5
n
, 代入原特征多项式
a
n
– 4a
n-1
= p5
n
– 4p5
n-1
= 2×5
n

当n=1 时, 有
5p – 4p = 10 所以p = 10
特解为: a*
n
= 10×5
n
,
一般解为: a
n
= A ×4
n
+ 10×5
n

当n=1时，有2 = 4A + 50，所以A = -12
a
n
= (-12) ×4
n
+ 10×5
n



a< br>n
6a
n1
9a
n2
3
n
,（2）

。

a
0
1,a
1
3.
解: 先求一般解
设特征方程：X
2
- 6X + 9 = 0 (X - 3)
2
= 0 r
1
= r
2
= 3
通解为: a’
n
= (A + B*n)3
n
= 3
n

再求特解, 因为3是特征方程的重根, 所以
设特解a*
n
= pn
2
3
n
, 代入原特征多项式
a
n
– 6a
n-1
+ 9a
n-2
= pn
2
3
n
- 6p(n-1)
2
3
n-1
+ 9p(n-2)
2
3
n-2
= 3
n

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅

当n=2时, 有
36p – 18p = 9 所以p = 12
特解为: a*
n
= n
2
3
n
2,
一般解为: a
n
= (A + B*n +n
2
2)3
n

根据a
0
和a
1
的值，可列出方程组：
A = 1
3(A + B + 12) = 3 可求出B = -12
一般解为: a
n
= (1 –n2 +n
2
2)3
n


3, 求解下列递推关系: (n- 1)a
n
-(n-2)a
n-1
-2a
n-2
=0(n2 ), a
0
=0,a
1
=1.







4, 设有2个红球，1个黑球，2个白球，问(1)有多少种不同 的选取方法，试加以枚举？(2),
从中任取3个，有多少种不同的取法？
解: 设红球多项式为1+t+t
2
, 黑球多项式为1+t, 红球多项式为1+t+t
2

所以的取球方法可以用多项式(1+t+t
2
)( 1+t)( 1+t+t
2
)表示
多项式展开=1+3t+5t
2
+5t
3
+3t
4
+t5
一共有1+3+5+5+3+1=18种选取方式
从中任取3个球的方式有5种

5, 用{1, 3,6,8}组成的3和6出现偶数次的4位数的个数是多少?
解：根据题目可设指数型母函数为：
G
e
(x) = (1 + x + x
2
2! + x
3
3! +x
4
4!)
2
×( 1 + x
2
2! +x
4
4!)
2

将等式右侧展开，其中x
4
项为：80×x
4
4!
即可以组成80个不同的4位数

6, 求由直线x+2y=n与坐标轴围成的三角形内(含边界)整点的个数S
n

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅

第三章 容斥原理与鸽巢原理
1,求由1、2、3、4组成的10位数中，1、3、4都至少出现一次的数的个数。
解: 设A1为1不出现的集合, A2为3不出现的集合, A3为4不出现的集合，可求出:
全集个数为|U| = 4
10

每个数字分别不出现的个数为|A1| = |A2| = |A3| = 3
10

分别有2个数字不出现的个数为|A1|∩|A2| = |A1|∩|A3| = |A2|∩|A3| = 2
10

分别有3个数字不出现的个数为|A1|∩|A2|∩|A3| = 1
10

题目所求为:
|A1|∩|A2|∩|A3|
= |A1|U|A2|U|A3|
= |U| - C(3,1)×|A1| + C(3,2)×|A1|∩|A2| - |A1|∩|A2|∩|A3|
101010
= 4 - 3×3 + 3×2 - 1

2,求从10到9999的正整数中是n
2
是但不是n
3
,n
4
形式的数的个数
解: 从10到9999中一共有9990个正整数, 其中 为n
2
的数有99-3=96个,n为4到99,设这
个集合为全集,这其中又为n< br>2
的数有9-1=8个,n为2到9,设这个集合为A1,全集中为n
3
的数< br>有4-1=3个,n为2,3,4,设这个集合为A2, A1中的8
2
=64，A2中 的4
3
=64，所以|A1|∩|A2|=1，
题目所求为:
|U| - |A1|U|A2| = |U| - |A1| - |A2| + |A1|∩|A2| = 96 – 8 – 3 + 1 = 86 (个)

3, 设
n
为大于1的奇数，证明： 在
2
1
1,2
2
1,,2
n
1
中 必有一个数能被
n
整除.




4, 某学者 每周上班工作35小时，每天工作的小时数是整数，每天工作时间不少于5小时
也不多于8小时。今要编 排一周的工作时间表，问有多少种不同的编排方法？
解: 设每周工作5天,分别为X1到X5,有等式如下:
X1 + X2 + X3 + X4 + X5 = 35
因为X1到X5均≥5小时,可分另设Y1+5=X1到Y5+5=X5,有等式:
Y1 + Y2 + Y3 + Y4 + Y5 = 10
因为X1到X5均≤8小时,又可分另设Y1=3-Z1到Y5=3-Z5,有等式:
Z1 + Z2 + Z3 + Z4 + Z5 = 5
求此方程的非负整数解的个数即为题解,
解为: C(5+5-1,5) = C(9,4)=(9×8×7×6)(4×3×2) = 126(种)

5, 从1到200这200个自然数中，至少要取出多少个数，才能保证一 定存在两个数是互素
的。并证明你的结论。（两个正整数互素，是指它们没有除1以外的正公因数。）
解: 1到200可分为素数和合数, 因为17×17 = 285 > 200, 所以其中的合数必然是
2,3,5,7,11,13的倍数, 其中有最多公因子的合数是以2为公因子的偶数, 为100个, 当取101
个数时, 至少有一个数

北京邮电大学软件学院软件工程研究生2009级 学号: 09R0232 姓名: 赵冬寅



6, n个 人参加一晚会，每人寄存一顶帽子和一把雨伞，会后各人也是任取一顶帽子和一把
雨伞，问(1)有多少 种可能的取法使得没有人能拿回他原来的任一件物品？
(2)有多少种可能取法使得没有人能同时拿回他原来的两件物品？
解:
问题1: 设数 列1,2,3,……,2n-1,2n为n个人所对应的物品,没人能取回原来的任何一件物品
就是把帽 子和雨伞分别进行错排,再把方案数相乘，根据错排公式,所求解为:
(n!(12!+13!-...+(-1)
n
n!))
2


问题2:
解法一:
设A1为全部不能取回自己帽子的方案集合, A2为全部不能取回自己雨伞的方案集合,有:
|A1| = |A2| = n!×n!(12!+13!-...+(-1)
n
n!)
全部同时不能取回帽子和雨伞的方案数为: |A1|∩|A2| = (n!(12!+13!-...+(-1)
n
n!))
2

题目所求为|A1|U|A2|, 根据公式:
|A1|U|A2| = |A1| + |A2| - |A1|∩|A2|
= (2(n!) - n!(12!+13!-...+(- 1)
n
n!))×n!(12!+13!-...+(-1)
n
n!)

解法二:
没有人能同时拿回他原来的两件物品, 分为四种情况: 1)帽子拿错但雨伞没错; 2) 雨伞拿
错但帽子没错; 3)有 k个人拿错帽子,n-k个人拿错雨伞, k=2,…,n-2; 4)所有人两样东西全部
拿错(此情况就是第一问),根据错排公式以及加法原理, 所求解为:
2(n!(12+13-...+(-1)
n
n!)) + (n!(12!+13!-...+(-1)
n
n!))
2
+
∑C(n,k)×k!(12+...+(-1)
k
k!)×(n-k)! (12+...+(-1)
n-k
(n-k)!
{k=2,……,n-2}