青蛙表情包-李佑晨

长春工业大学2012-2013组合数学考试范围

第一部分：填空题。
题目1:求n元布尔函数f (x1，x2，…，xn）的数目，其中布尔函数是指含有与（∧）、或（ ∨）、
非（－）等基本布尔运算的函数。
解答：设有n个布尔变元x
1
，x
2
，…，x
n
，其中x
i
∈{0，1}，i =1，2，… ，n，根据乘法原理
(x
1
，x
2
，…，x
n
)共 有2
n
种不同指派，对每个指派，布尔函数取值为{0，1}，故不同的布尔
函数的数 目为：
2
2
。
（考试中会给定n的具体数值，带入公式直接计算即可。）
题目2：n对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数。
解答：夫妻相邻而坐，可以 将一对夫妻看成一个整体，其圆排列数为(n-1)!，由于每对夫妻
可以交换位置，故所求方案数为( n-1)!×2。
题目3：求多重集合M = {∞·a
1
, ∞·a
2
, …, ∞·a
n
}的r排列数。
解答：在构造的M的一个r排列时，第一项有n种选择，第二项有n种选择，……，
第r项有n种选择，故M的r排列数为n
r
。
(一般地，n元多重集合表示为：M = {k
1
·a
1
, k
2
·a
2
, …, k
n
·a
n
}其中：a
i
（i = 1, 2, …, n）
表示元素的种类，k
i
（i = 1, 2, …, n）表示元素a
i
的个数。)
题目4：求多重集合M = { k
1
·a
1
, k
2
·a
2
, …, k
n
·a
n
}的全排列数。
解答：先把M中的所有的k
1
+ k
2
+ … + k
n
个元素看成是互不相同的，则它的全排列数为(k
1
+ k
2
+ … + k
n
)!。但是这里k
i
!个a
i
是 相同的，所以k
i
!个a
i
的位置相同并且同其他元素排列
也相同的 排列是同一个，故M的全排列数为：

(k
1

k
2

k
n
)!
k
1
!k
2
!

k
n
!
n
n
。
题目5：确定
(x
1
x
2
x
3
x
4
x
5
)
10
的展开式中x
1
3
x
2
x
3
4
x
5
2
的系数。
解答：


10!

10

7

6

2

10





1

4

2

3,1,4,2

3



3!7!1!6!
7!

6!
4!2!

2!
2!0!

10!
3!1!4!2!


n

r
C

（

表示从n中取r个的组合，与的意义完全相同。试题中可能会改变具体的数值，
n

r


15
例如求
(x
1
x
2
x
3
x
4
x
5
)< br>的展开式中x
1
5
x
2
4
x
3
4
x
5
2
的系数，只需按上述过程计算即可。）
题目6： 求正整数n的有序k分拆的个数，要求第i个分部量大于等于p
i
。

k< br>

nk

p
i
1

解答 ：分拆的个数为：

，其中（1≤i≤k）。
i1


k1


例如：9的有序3分拆，要求所有分部量都大于等于2，其个数为：

第
1
页 共 1 页

长春工业大学2012-2013组合数学考试范围

936 1

5



31

=


2


=10。

题目7：一个抽屉里 有20件衬衫，其中4件是兰色的，7件是灰色的，9件是红色的，问从
中随意取多少件能保证有4件是 同色的？抽取多少件能保证5，6，7，8，9件是同色的？
解答：应用鸽笼原理即可，抽取的件数分别为：3 × 3 +1= 10；4 + 2×4 + 1 = 13；4 + 2×5 + 1
= 15；4 + 2×6 + 1 = 17；4 + 7 + 1×7 + 1 = 19；4 + 7 + 1×8 + 1 = 20。
题目8：有置换

1



31


123
2
4


1

，

2



4
4



2
3
3
2
4


1


求

1


2
和

2


1
， 若令S
n
是G =
{1, 2, 3,4}上置换的全体，则S
n
是否构成置换群？

1




解答：
12


3

2< br>1
3
2
4

1


4



4
2
3
3
2
4


1





2
1



2
4
3
3
4


。
1


即先作δ
1
置换，再作δ
2
置换，置换过 程如下：
12
132

,
2
312
214

12
12
41

23
，
4
，
3


1




同理，
21


4

3
2
4

1

1


3
2
1
3
2
4

1




4


4
2
2
3
1
4


。
3


由运算“·”的定义可知，若

1


2
< br>
2


1
，即先作δ
1
的置换再作δ2
的置换，其结果与先作δ
2
的置换再作δ
1
的置换相同，则S
n
对于元算“·”构成群，且称（S
n
，·）为n次对称群，（S
n
，·）
的任意子群称为置换群。

δ
1
·δ
2
≠ δ
2
·δ
1
，

S
n
不是置换群。
题目9：求n元多重集合的r组合数；求方程x
1
+ x
2
+ … + x
n
= r（n, r为正整数）的非负
整数解的个数；求r个相同的球放 入n个有区别的盒子中，允许有空盒的放法；求
(x
1

x
2

x
n
)
展开式的项数。
r
解答：以上问题的所求计数均为




nr1



r

。
题目10：求n元多重集合的r-n的组合数；求方程x
1
+ x
2
+ … + x
n
= r（n, r为正整数）的
正整数解的个数；求r个 相同的球放入n个有区别的盒子中，不允许有空盒的放法；求
(x
1

x2

x
n
)
展开式中含
x
1
1x
2
2
x
n
n
且r
i
≥1（1≤i ≤n）的项数。
r
rr
r
解答：以上问题的所求计数均为


n(rn)1

r1

r1

r1




rn

rn
(r1)(rn)





n 1



。
题目11：把r只相同的球放到n个不 同的盒子里，每个盒子至少包含q只球，问有多少种
放法？
解答：相当于求如下方程的解：
x
1
+ x
2
+ … + x
n
= r （x
i
≥q） （式1）
令 y
i
= x
i
-q，则y
i
≥0且方程
y
1
+ y
2
+ … + y
n
= r – nq （式2）

第
2
页 共 2 页

长春工业大学2012-2013组合数学考试范围
的解与式1的解一一对应 ，而方程2的非负整数解为：


n(rnq)1


，即为所求。

rnq

题目12：求
(x
1
x
2
x
r
)
n
展开式中
x
i< br>n
(n
i
1)
的项数
。

i
解答 ：本题与n个相同的球放进r个有区别的盒子且不允许有空盒，即r个盒子的球数依次

n1

为n
1
, n
2
,…, n
r
，且n
1
+ n
2
+ … + n
r
= n（n
i
≥1，1≤i≤r）的求解策略类似，方案数为

< br>
。
r1

题目13：在一个凸n边形中，通过插入内部不相交对 角线将其剖分成一些三角形区域，有
多少种不同的分法？设有n个元素
a
1
, a
2
,

,a
n
，在其前后次序不变的情况下，每次只对两
个元素进行乘法，以括号决定乘的先后顺序，有多少种不同的相乘方式？
解答：令h(n)表 示所求数量，则
h(n)

h(k)h(nk)
，补充定义h(1) = 1即可计算。
k1
n1
题目14：有2n个人排成一行进入剧场，入场费50元 ，2n个人中有n个人有50元的纸币，
n个有100元的纸币，剧场售票处用一个空的现金收录机开始 售票，有多少种排队方法使得
只要有100元的人买票，售票处就有50元找零。
解答：根据 Catalan序列的定理：n个+1和n个-1构成的2n项
a
1
,a
2< br>,,a
2n
，其部分和满足：
a
1
a
2
a
k
0(1k2n)
的数列的个数等于第n个Catalan数
C
n


2n



(n1)。

n
n1

1
有50元的人用+1标识，有1 00元的人用-1标识，且这2n个人是不可区分的，则方案数为
C
n

< br>2n

1

2n


；如果这2n个人是 可区分的，则方案数为。

n!n!


n1

n

n
n1


1
题目15：求S = {3·a, 4·b, 5·c}的10组合数。
解答：S中共有3+4+5=12个元素，由组 合数的意义可知，10组合的数量与2组合的数量相
等，而S中的2组合为{aa
，
b b
，
cc
，
ab
，
ac
，
bc}，故10 组合数为6种。
（本题的出题形式未确定，也可能以解答题的形式出现，并改变具体的数值，通用的解 题
步骤会在下面解答题中详述。）
题目16：求集合S的不相邻的排列个数Q
n
，集合S = {1, 2, …, n}的不相邻的排列是该集合
上不出现12, 23, …, (n–1)n这些模式的全排列。 解答：
Q
n
n!


1

1
n1

n2

n


(n1)!(n2)!

(1)

2

n1


1!


（针对填空题，仅需记住公式 带入具体数值即可，其中

例如：
Q
8

1
< br>n1

的意义与

的意义相同，


n 1

1



7

6

5

4

3

2

1


7!

6!

5!
 
4!

5!

2!

1!
=14664；本知识点也可能以解答题的
8!


1
2

3

4

5

6

7


形式出现，详细的求解过程会在下 面的解答题中详述。）
第二部分：解答题。

第
3
页 共 3 页

长春工业大学2012-2013组合数学考试范围
题目1：在一个 凸n边形中，通过插入内部不相交对角线将其剖分成一些三角形区域，有多
少种不同的分法？设有n个元 素
a
1
,a
2
,

,a
n
，在其 前后次序不变的情况下，每次只对两个
元素进行乘法，以括号决定乘的先后顺序，有多少种不同的相乘方 式？
解答：在一个凸n边形中，当n≥4时，凸n+1
A
k+1

边形的顶点用A
1
, A
2
,…, A
n+1
表示 ，取定多边形一
条边A
1
A
n+1
，任取多边形的一个顶点A
k+1
（2≤k +
1≤n  1≤k≤n-1），将A
k+1
分别与 A
1
和A
n+1
连
线得到三角形T，则三角形T将凸n+1边形分成
T、R
1
和R
2
三个部分，其中R
1
为k+1边形 ，R
2
为n-k+1边形，如图5所示。因此，R
1
有h(k)种
剖 分方法，R
2
有h(n-k)种剖分方法。所以：
h(n)
A
k

R
1

T
A
1

R
2

A
n+1

图5 n+1边形剖分示意图

h(k)h(nk)
。
k1
n1
n个元素相乘，无论怎样结合（即画括号），总有一个时刻到达最后一 次相乘，即
设竖线左边有k个元素竖线右边有n-k个元素，则竖线左边有
h(k)
( a
1
a
k
)
|
(a
k1
a
n
)
，
种结合方式，竖线右边有
h(nk)
种结合方式。由乘法原 理，共有
h(k)h(nk)
种结合方式。
现移动竖线，竖线可从
a
1
|(a
2
,,a
n
)
到
(a
1,

,a
n1
)|a
n
范围内移动，即从1到n-1 ，由加
法原理，
h(n)

h(k)h(nk)
。
k1
n1
题目2：证明：n个+1和n个-1构成的2n项
a
1
,a
2
,,a
2n
，其部分和满足：
a
1
a< br>2
a
k
0(1k2n)
的数列的个数等于第n个Cata lan数
C
n


2n




(n1)
。
n
n1


1
解答： 证明：在2n项中有n个1的方案数为



2n

2n


，则所求方案数 = - 不符合要求


n

n

的方案数。而不符合要求的方案的特征：从左向右扫描，在某个奇 数位2m+1上首先出现
m+1个-1和m个1，在第2m+1位后还有2n-(2m+1) = 2(n-m)-1位。则在2(n-m)-1位中必
然有n-m-1个-1和n-m个1。把剩下的2( n-m)-1位的-1与1互换，结果得到一个由n+1

2n

2n
个-1和n-1个1组成的2n位数，即


n1


或


n1


，反之亦然。
 
因而不符合要求的方案数

由n+1个-1和n-1个1组成的组合数，即 < br>
2n

2n


1

1
(2n)!1

2n


(2n)!



n

n1


n

。
n!n!(n1)!(n1)!
n!(n1)!n1



题目3：求S = {3·a, 4·b, 5·c}的10组合数。
解答：令S
∞
={∞·a, ∞·b, ∞·c}，则S< br>∞
的10组合数为



3101

12




66

2

10

。
设集合A：集合S
∞
的10组合的全体，则|A| =66，现在要求在10组合中的a的个数≤3，b

第
4
页 共 4 页

长春工业大学2012-2013组合数学考试范围
的个数≤4，c的个数≤5的组合数。
设A
1
：10组合中a的个数≥4的集合；
A
2
：10组合中b的个数≥5的集合；
A
3
：10组合中c的个数≥6的集合。
则A
1
中的元素可以看作是由S
∞
的10-4 = 6组合（可能包含a也可能不包含a）再拼上4个
a构成。所以
类似的有

31051

7




21A2



105

2



31041

8



< br>28A
1



104

2


。
，

31061

6< br>



15A
3


106

2




3104 51

3




3A
1A
2



1045

1


，

310461

2



1

A
1
A
3



1046

0



310561

1




A
2
A
3



1056
1

0

，|A
1
∩A
2
∩A
3
|=0
则
A
1
A
2
A3
S(A
1
A
1
A
3
)(A
1
A
2
A
1
A
2
A
2
A
3
)A
1
A
2
A
3
= 66 - ( 28 + 21 + 15 ) + ( 3 + 1 + 0 ) - 0= 6
题目4：求集合S的不相邻的排列个数Q
n
，集合S = {1, 2, …, n}的不相邻的排列是该集合
上不出现12, 23, …, (n–1)n这些模式的全排列。
解答：设S为{1, 2, …, n}的全排列，则|S| = n!，定义性质集合P={p
1
, p
2
, …, p
n
}，其中
P
i
：出现i(i+1)模式（1≤i≤n–1）， 则A
i
：S中满足性质P
i
的全排列的集合。
A
i
中每个排列是集合{1, 2, …, i–1, i(i+1), i+2, …, n}的一个全排列，则|A
i
| =(n–1)!。
同理，A
i
∩A
j
中每个排列是集合{1, 2, …, i–1, i(i+1), i+2, …, j(j+1), …, n}的一个全排列，则
|A
i
∩A
j
|=(n–2)!（1≤i ≠ j≤n–1）。
一般的有：
|A
i1
∩A
i2
∩…∩A
ik
|=(n–k)!（1≤A
i1
≠ A
i2
≠ … ≠ A
ik
≤n–1)
则
Q
n

n1

n2

1


(n1)!

(n2)!

(1)
n

A
1
< br>A
2

A
n
n!


1< br>
2

n1

1!


。

题目5：当n≥r≥1时，解释

 



r


n

n1< br>



r


n1



r1

的组合意义。


解答：其组合意义为：设n元集合A = {a
1
, a
2
, …, a
n-1
} + {a
n
}，则集合A的r 元子集


可

r


n
< br>以分为两类：①、r元子集含a
n
：集合{a
1
, a
2
, …, a
n
}的r元子集即是集合{a
1
, a
2
, …, a
n-1
}的
r-1元子集，共有



n1



个；
r1

②、r元子集不含a
n
：集合{a
1
, a
2
, …, a
n
}的r元子集即是集合{a
1
, a
2
, …, a
n-1
}的r元子集，
共有



n

n1

n1


n1







个。由加法 原理，得：

r

r

r1

。



r

题目6：设A
1
， A
2
，…，A
k
是A的k个子集，若满足：（1）A
i
≠Φ（1≤ i ≤ k）（2）A
i
∩A
j
=
Φ（1≤ i≠j ≤ k）（3）A = A
1
∪A
2
∪…∪A
k
， 则称{A
1
，A
2
，…，A
k
}是A的一个k分划， 一

第
5
页 共 5 页

长春工业大学2012-2013组合数学考试范围
个n元集合的全部k分划的个数记作S(n, k)。证明 S(n + 1, k) = S(n, k - 1) + k×S(n, k) ，(1
≤k≤n)，并解释其组合意义。
解答：这个证明方法也是构造集合A的所有k分划的方法。
(n + 1, k) 是集合A = {a
1
, a
2
,…, a
n
, a
n+1
} 的k分划的个数，这些k分划可以分成两类：
（1）{a
n+1
}是A 的k分划中的一块，这时，只需对集合A-{a
n+1
}进行k-1分划，再加上{a
n+1
}
这块，就构成了A 的k分划，因此，这类分划有S(n, k - 1) 个。
（2）{a
n+1
}不是A 的k分划中的一块，这时，先构造集合A-{a
n+1
}的k分划，共有S(n, k)
个，然后，对A-{a
n+1
}的每个k分划，分别将a
n+1
加到k个块 中，从而构成A的k分划，由
乘法原理，A的此类k分划共有k×S(n, k)。
题目7：证明S(n + 1, k) =


n

mk1

m
n


S(m,k1)
，并 解释其组合意义。


解答：S(n + 1, k) 是集合A = {a
1
，a
2
，…，a
n
，a
n+1
}的k分划数， 对于A的一个k分划，设
包含a
n+1
的块为B（即a
n+1
∈B） ，则其余的

k-1块构成了A-B的一个k-1分划；反过来，给
定A的一个包含a
n+1
的集合B，若|A-B|≥k

-1，则A-B的k

-1分划再加上B就构成了A的
一个k分划。可以如下构造A的k分划：
（1）先取A的一个不含a
n+1
的子集C，使|C|≥k

-1；
（2）作出C的一个k

-1分划；
（3）再拼上A-C = B就构成了A的一个k分划，而m＝|C|可以取k

-1, k,…, n。
< br>n

对于确定的m，从A中取C的方案有


m
< br>
，确定了C之后，C的k

-1分划为S(n, k - 1)，


n

由加法原理和乘法原理，有S(n + 1, k) =

mk1

m
n


S(m,k1)
。


题目8：设A = {1, 2, 3, 4}（n=3, k=2），求S（4,2）并解释其组合意义。
3

3
 
3

3

3

3

 






7
解答：
S(4,2)


S(m,1)



1

2

3

m1

m

m1

m

3
A的2分划为 ：
A = {1}∪{2，3，4}
= {1，2}∪{3，4} = {1，3}∪{2，4} = {2，3}∪{1，4}
= {1，2，3}∪{4} = {1，2，4}∪{3} = {1，3，4}∪{2}

3


1
，设

3



3

 
3
，设

2


C = {1, 2, 3}，则A-C = B = {4}，即S(3, 1) ={1, 2, 3}∪{4}。
C = {1, 2}，则A-C = B = {3, 4}；设C = {1, 3}，则A-C = B = {2, 4}
设C = {2, 3}，则A-C = B ={1, 4}，即S(2, 1) = {1, 2}∪{3, 4} = {1, 3}∪{2, 4} = {2, 3}∪{1, 4}。

3


3
，设

1

 
C = {1}，则A-C = B = {2, 3, 4}；设C = {2}，则A-C = B = {1, 3, 4}；设C = {3}，
则A-C = B = {1, 2, 4}，即S(1, 1) = {1}∪{2, 3, 4} = {2}∪{1, 3, 4} = {3}∪{1, 2, 4}。

第
6
页 共 6 页

长春工业大学2012-2013组合数学考试范围
题目9：给定15的4分拆，如15 = 5 + 5 + 3 + 2，画出其Ferrers图和共轭图，并求其共轭
分拆。
解答：






180
共轭图

把一个Fer rers图的行变列（即转置），这样的Ferrers图的称为原Ferrers图的共轭图，共轭
F errers图对应的分拆称为原分拆的共轭分拆。
故15 = 4 + 4 + 3 + 2 + 2是15 = 5 + 5 + 3 + 2的共轭分拆，且15的5分拆数等于15的最大
分部量为5的分拆数。
题目10：v
1
v
2
v
3
是圆圈上的三等分点 ，用红、蓝和绿三种颜色的珠子镶嵌，问有多少种不
同的方案？
解答：
方法1：圆 圈可以分别绕中心点旋转0，120，240，以及过点的垂直于其他两点的连线的垂
直线为轴翻转，则 有如下置换群：
G = {(v
1
)(v
2
)(v
3
), (v
1
v
2
v
3
), (v
3
v
2
v
1
), (v
1
)(v
2
v
3
), (v
2
)(v
1
v
3
), (v
3
)(v
1
v
2
)}
依据Polya定理，设G = {p
1
, p
2
, …, p
g
}是D = {1, 2, …, n}上的置换群，用 m种颜色对D上
的n个对象着色，则不同的着色方案数为：
l
1
G
g

m
i1
c(p
i
)
，其中
c(p< br>i
)
表示置换p
i
分解为不相交轮换之积中轮换因子的个数。故不同的 方案数为：N = (3
3
+ 3+ 3 + 3
2
+ 3
2
+ 3
2
)
6 = 10。
方法2：使用穷举法直接画出图即可。







第
7
页 共 7 页