1
组合分析
2
组合分析部分
? 第 10章 组合分析初步
3
第 10章组合分析初步
? 10.1 加法法则和乘法法则
?加法法则与乘法法则
?应用实例
? 10.2 基本排列组合的计数方法
?排列组合问题的分类
?集合的排列与组合
?多重集的排列与组合
4
加法法则
使用条件：事件 A与 B 产生方式不重叠
适用问题：分类选取, 方式分别计数，再相加,
推广：事件 A1 有 n1 种产生方式，事件 A2有 n2
种产生方式,…,事件 Ak 有 nk 种产生的方式，
则“事件 A1 或 A2或 … Ak” 有 n1+n2+…+ nk 种产
生的方式,
事件 A有 m 种产生方式，事件 B 有 n 种产生方
式，则“事件 A 或 B”有 m+n 种产生方式,
5
乘法法则
使用条件：事件 A与 B产生方式相互独立
适用问题：分步选取, 方式是连续的步骤，各步
相互独立，分别计数，然后相乘,
推广：事件 A1 有 n1 种产生方式，事件 A2有 n2
种产生方式,…,事件 Ak 有 nk 种产生的方式，
则“事件 A1 与 A2与 … Ak” 有 n1n2… nk 种产生
的方式,
事件 A有 m 种产生方式，事件 B 有 n 种产生方
式，则“事件 A 与 B”有 mn 种产生方式,
6
应用实例
解 1400 = 23 52 7
正因子为,2i 5j 7k，其中 0 ?i?3,0?j?2,0?k?1
N = (3+1)(2+1)(1+1) = 24
例 1 设 A,B,C是 3个城市，从 A 到 B 有 3条道路，
从 B 到 C 有 2条道路，从 A 直接到 C 有 4条道路，
问从 A 到 C 有多少种不同的方式？
解 N = 3?2+4 = 10
例 2 求 1400 的不同的正因子个数
7
排列组合的分类
选取问题：设 n 元集合 S，从 S 中选取 r 个元素,
根据是否有序，是否允许重复可将该问题分为四
个子类型
不重复 重复
有序 集合排列 P(n,r) 多重集排列
无序 集合组合 C(n,r) 多重集组合
8
集合的排列
从 n 元集 S 中有序、不重复选取的 r 个元素称为
S 的一个 r 排列, S 的所有 r 排列的数目记作
S 的 r- 环排列 数 =
?
?
?
?
?
?
?
?
?
??
rn
rn
rn
n
rn
n
P
r
n
0
)!(
!
)!(
!
)!(
!
rnr
n
r
P rn
?
?
rnP
9
集合的组合
从 n 元集 S 中无序、不重复选取的 r 个元素称为
S 的一个 r 组合, S 的所有 r 组合的数目记作
证明方法,
公式代入
组合证明（一一对应）
?
?
?
?
?
?
?
?
?
?
rn
rn
rnr
n
r
P
C
r
n
r
n
0
)!(!
!
!
r
nC
10
基本计数公式的应用
解 令 A={1,4,…,298}, B={2,5,…,299}
C={3,6,…,300}
将方法分类,
分别取自 A,B,C,各
A,B,C各取 1个,1
100C
3100C
1485100)(3 311003100 ??? CCN
例 1 从 1— 300中任取 3个数使得其和能被 3整除有
多少种方法？
11
基本计数公式的应用（续）
解 1000! = 1000 ?999? 998 ?… ? 2?1
将上面的每个因子分解，若分解式中共有
i 个 5,j 个 2，那么 min{ i,j } 就是 0 的个数,
1,…,1000 中有
500 个是 2 的倍数,j > 500;
200 个是 5 的倍数,
40 个是 25 的倍数（多加 40个 5）,
8 个是 125 的倍数（再多加 8个 5）,
1 个是 625 的倍数（再多加 1个 5）
i = 200 + 40 + 8 + 1 = 249,min{ i,j }=249,
例 2 求 1000！的末尾有多少个 0？
12
多重集 S ={n1?a1,n2?a2,…,nk?ak},0 <ni ?+∞
(1) 全排列 r = n,n1 + n2 + … + nk = n
证明：分步选取，先放 a1,有 种方法；再放 a2,
有 种方法,...,放 ak有 种方法
(2) 若 r ? ni 时，每个位置都有 k 种选法，得 kr,
多重集的排列
1nnC
!...!!
!
21 knnn
nN ?
!...!!
!
...
21
.,, 11
2
1
1
k
n
nnn
n
nn
n
n nnn
n
CCCN k
k
??
????
2
1
n
nnC ? k
k
n
nnnnC 121,,, ?????
13
多重集的组合
当 r ? ni, 多重集 S ={ n1?a1,n2?a2,…,nk?ak } 的组
合数为
证明 一个 r 组合为 { x1?a1,x2?a2,…,xk?ak }，其中
x1 + x2+ … + xk = r,xi 为非负整数, 这个不定方程
的非负整数解对应于下述排列
1…1 0 1…1 0 1…1 0 …… 0 1…1
x1个 x2个 x3个 xk个
r 个 1,k-1个 0 的全排列数为
r
rkCkr
krN
1)!1(!
)!1(
????
???
r
rkCkr
krN
1)!1(!
)!1(
????
???
14
实例
解：设盒子的球数依次记为 x1,x2,…,xn,则满足下
述方程,
x1 + x2 + … + xn = r,x1,x2,…,xn为非负整数
该方程的解的个数为,
r
rkCkr
kr
N 1
)!1(!
)!1(
????
??
?
例 3 r 个相同的球放到 n 个不同的盒子里，每个盒
子球数不限，求放球方法数,
15
实例
解：固定 a 和 b 中间选 7个字母，有 种方法
将它看作大字母与其余 17个全排列有 18！种,
7
242P
!182 724 ?? PN
例 4 排列 26个字母，使得 a与 b之间恰有 7个字母，
求方法数,
16
实例（续）
解,
(1)
(2)
5
11
10
10 PP
5
01
10
1010
1
PP
例 5
(1) 10个男孩,5个女孩站成一排，若没女孩
相邻，有多少种方法？
(2) 如果站成一个圆圈，有多少种方法？
17
实例（续）
解：相当于 2n 不同的球放到 n 个相同的盒子，每
个盒子 2个，放法为
!2
)!2(
!)!2(
)!2(
n
n
n
n
N
nn
??
例 6 把 2n 个人分成 n 组，每组 2人，有多少分法？
18
实例（续）
例 7 9本不同的书，其中 4本红皮,5本白皮,
(1) 9本书的排列方式数有多少？
(2) 若白皮书必须放在一起，那么有多少方法？
(3) 若白皮书必须放在一起，红皮书也必须放在
一起，那么有多少方法？
(4) 若把皮和红皮书必须相间，有多少方法？
解,
(1) 9! (2) 5！ 5！
(3) 5！ 4！ 2！ (4) 5！ 4！
组合分析
2
组合分析部分
? 第 10章 组合分析初步
3
第 10章组合分析初步
? 10.1 加法法则和乘法法则
?加法法则与乘法法则
?应用实例
? 10.2 基本排列组合的计数方法
?排列组合问题的分类
?集合的排列与组合
?多重集的排列与组合
4
加法法则
使用条件：事件 A与 B 产生方式不重叠
适用问题：分类选取, 方式分别计数，再相加,
推广：事件 A1 有 n1 种产生方式，事件 A2有 n2
种产生方式,…,事件 Ak 有 nk 种产生的方式，
则“事件 A1 或 A2或 … Ak” 有 n1+n2+…+ nk 种产
生的方式,
事件 A有 m 种产生方式，事件 B 有 n 种产生方
式，则“事件 A 或 B”有 m+n 种产生方式,
5
乘法法则
使用条件：事件 A与 B产生方式相互独立
适用问题：分步选取, 方式是连续的步骤，各步
相互独立，分别计数，然后相乘,
推广：事件 A1 有 n1 种产生方式，事件 A2有 n2
种产生方式,…,事件 Ak 有 nk 种产生的方式，
则“事件 A1 与 A2与 … Ak” 有 n1n2… nk 种产生
的方式,
事件 A有 m 种产生方式，事件 B 有 n 种产生方
式，则“事件 A 与 B”有 mn 种产生方式,
6
应用实例
解 1400 = 23 52 7
正因子为,2i 5j 7k，其中 0 ?i?3,0?j?2,0?k?1
N = (3+1)(2+1)(1+1) = 24
例 1 设 A,B,C是 3个城市，从 A 到 B 有 3条道路，
从 B 到 C 有 2条道路，从 A 直接到 C 有 4条道路，
问从 A 到 C 有多少种不同的方式？
解 N = 3?2+4 = 10
例 2 求 1400 的不同的正因子个数
7
排列组合的分类
选取问题：设 n 元集合 S，从 S 中选取 r 个元素,
根据是否有序，是否允许重复可将该问题分为四
个子类型
不重复 重复
有序 集合排列 P(n,r) 多重集排列
无序 集合组合 C(n,r) 多重集组合
8
集合的排列
从 n 元集 S 中有序、不重复选取的 r 个元素称为
S 的一个 r 排列, S 的所有 r 排列的数目记作
S 的 r- 环排列 数 =
?
?
?
?
?
?
?
?
?
??
rn
rn
rn
n
rn
n
P
r
n
0
)!(
!
)!(
!
)!(
!
rnr
n
r
P rn
?
?
rnP
9
集合的组合
从 n 元集 S 中无序、不重复选取的 r 个元素称为
S 的一个 r 组合, S 的所有 r 组合的数目记作
证明方法,
公式代入
组合证明（一一对应）
?
?
?
?
?
?
?
?
?
?
rn
rn
rnr
n
r
P
C
r
n
r
n
0
)!(!
!
!
r
nC
10
基本计数公式的应用
解 令 A={1,4,…,298}, B={2,5,…,299}
C={3,6,…,300}
将方法分类,
分别取自 A,B,C,各
A,B,C各取 1个,1
100C
3100C
1485100)(3 311003100 ??? CCN
例 1 从 1— 300中任取 3个数使得其和能被 3整除有
多少种方法？
11
基本计数公式的应用（续）
解 1000! = 1000 ?999? 998 ?… ? 2?1
将上面的每个因子分解，若分解式中共有
i 个 5,j 个 2，那么 min{ i,j } 就是 0 的个数,
1,…,1000 中有
500 个是 2 的倍数,j > 500;
200 个是 5 的倍数,
40 个是 25 的倍数（多加 40个 5）,
8 个是 125 的倍数（再多加 8个 5）,
1 个是 625 的倍数（再多加 1个 5）
i = 200 + 40 + 8 + 1 = 249,min{ i,j }=249,
例 2 求 1000！的末尾有多少个 0？
12
多重集 S ={n1?a1,n2?a2,…,nk?ak},0 <ni ?+∞
(1) 全排列 r = n,n1 + n2 + … + nk = n
证明：分步选取，先放 a1,有 种方法；再放 a2,
有 种方法,...,放 ak有 种方法
(2) 若 r ? ni 时，每个位置都有 k 种选法，得 kr,
多重集的排列
1nnC
!...!!
!
21 knnn
nN ?
!...!!
!
...
21
.,, 11
2
1
1
k
n
nnn
n
nn
n
n nnn
n
CCCN k
k
??
????
2
1
n
nnC ? k
k
n
nnnnC 121,,, ?????
13
多重集的组合
当 r ? ni, 多重集 S ={ n1?a1,n2?a2,…,nk?ak } 的组
合数为
证明 一个 r 组合为 { x1?a1,x2?a2,…,xk?ak }，其中
x1 + x2+ … + xk = r,xi 为非负整数, 这个不定方程
的非负整数解对应于下述排列
1…1 0 1…1 0 1…1 0 …… 0 1…1
x1个 x2个 x3个 xk个
r 个 1,k-1个 0 的全排列数为
r
rkCkr
krN
1)!1(!
)!1(
????
???
r
rkCkr
krN
1)!1(!
)!1(
????
???
14
实例
解：设盒子的球数依次记为 x1,x2,…,xn,则满足下
述方程,
x1 + x2 + … + xn = r,x1,x2,…,xn为非负整数
该方程的解的个数为,
r
rkCkr
kr
N 1
)!1(!
)!1(
????
??
?
例 3 r 个相同的球放到 n 个不同的盒子里，每个盒
子球数不限，求放球方法数,
15
实例
解：固定 a 和 b 中间选 7个字母，有 种方法
将它看作大字母与其余 17个全排列有 18！种,
7
242P
!182 724 ?? PN
例 4 排列 26个字母，使得 a与 b之间恰有 7个字母，
求方法数,
16
实例（续）
解,
(1)
(2)
5
11
10
10 PP
5
01
10
1010
1
PP
例 5
(1) 10个男孩,5个女孩站成一排，若没女孩
相邻，有多少种方法？
(2) 如果站成一个圆圈，有多少种方法？
17
实例（续）
解：相当于 2n 不同的球放到 n 个相同的盒子，每
个盒子 2个，放法为
!2
)!2(
!)!2(
)!2(
n
n
n
n
N
nn
??
例 6 把 2n 个人分成 n 组，每组 2人，有多少分法？
18
实例（续）
例 7 9本不同的书，其中 4本红皮,5本白皮,
(1) 9本书的排列方式数有多少？
(2) 若白皮书必须放在一起，那么有多少方法？
(3) 若白皮书必须放在一起，红皮书也必须放在
一起，那么有多少方法？
(4) 若把皮和红皮书必须相间，有多少方法？
解,
(1) 9! (2) 5！ 5！
(3) 5！ 4！ 2！ (4) 5！ 4！
