Chapter 3
排列与组合
§1. 重复排列
一. 引例与简介
1. 例1:在三元集{a,b,c}中取两个,则
(2). 元素允许重复的排列有9个:
aa, bb, cc, ab, ac, ba, bc, ca, cb,
(1). 元素不允许重复的排列有P(3,2)=6个:
ab, ac, ba, bc, ca, cb
1 1 2 2
1
2. 1. { , , },
, , (
k k
k i i
S n a n a n a
a a S n a
定义 多重集 其中
为 中所有互不相同的元素, 1)称为元素
的重数.
重数无限制的重复排列计数问题
重数确定的重复排列计数问题
各元的重数分别限定于某些特定子集的重复排列
计数问题
圆周上的重复排列问题
一般图上的重复排列问题
3. 重复排列计数问题的类型
注:重复排列即从S中有序的取出r个元
1 21. 1. { , , }
.
k
r
S a a a
r k
定理 多重集合 的
排列数为
Proof: r个位置中,每个位置都有k种选择,且不依
赖于前面已选择的项.
二. 关于重复排列的若干结论
例:P30. Ex. 22:
若允许相邻位置的数相同
若不允许相邻位置的数相同
1 1 2 21. { , , , },
.
k k i
r
S n a n a n a n r
S r k
2.推论 多重集 若 ,
则 的 排列数为
1 1 2 2
1
1 21
3. . { , , , }
!
, , .
! !
k k
k
kk
S n a n a n a
nn
n n n
n n nn n
定理2 多重集 的全排列
数为 记为 这里
Proof: 方法一:从n个位置中依次找出ni 个位置给ai
1 11
1 2
1 11
1 1 2 1 2
1
N
( )!( )!!
!( )! !( )! !0!
!
! !
k
k
k
k
k
n n nn n n
nn n
n n nn nn
n n n n n n n n
n
n n
方法二:先看n个元的全排列(视为两两不同),n!
再看重复元的内部排列.
i in a个 互换位置对应的实为同一个排列
1 2
, .
k
nn
n n nk
注:(1) 此即 的推广 即多项式系数
1 2{ , , , }kn M a a a(2)此即 元集 的有序划分的个数:
即一:将n元集M有序划分为k份,使得第i份恰含有ni个
元素的划分个数为多少?
即二:将n个不同的球放到k个不同的盒子里,使得第i
个盒中恰含有ni个球的放法数有多少?
(3) 这里每个划分即相当于一个映射
( )i if a j a j 被划分到第份
注:用列表法来表示X到Y的映射,则每一个映射即相
当于从k个元素中选取n个的一个重复排列.
1 2 1 2 { , , , }, { , , , }n kX x x x Y y y y 设集合
①求X到Y的映射个数N1
②求X到Y的恰有ni个元素映成yi的映射个数N2,这
里n=n1+n2+...+nk
解: N1即从k个元素中取n个的重数无限制的重复排列
个数
解: N2即k个元素的重数固定为n1,n2,...,nk的重复排
列个数
3. 排列与映射:
解:N3即从k个元素中取n个不同元素的排列个数.
: 计数问题的基本思想方法即:建立适当的一
一对应关系,要求问题A的
数,改求问题B的方
案数.
③求X到Y的单射个数N3
特别,若X,Y均为n元集,则从X到Y的一一映射
的个数为n!
三. 应用举例
例1:一个矩形有向道路区由n+1条自左向右的横道路
和m+1条自下向上的竖道路构成,则从左下角A点到右
上角B点的有向道路由多少条呢?
解:(1) 此即从A(0,0)到B(m,n)
(2) 由A到B的一条有向路等价于m个横段与n个
竖段所成的一个重复排列
( )!
! !
m n
N
m n
(3)故,
注:(1) 称为从(0,0)到(m,n)的非降路径数
(2) 推广到高维:在k维欧氏空间的类似有向道路区内,
从原点到点(n1,n2,...,nk)的有向道路条数即多项式系数
例2. 将20本不同的
分送给王6本,李6本,张8本,
求不同的送法数.
注:(1) 此即{20本书}到{王,李,张}的映射,使得6个
元映到王,6个元映到李,8个元映到张的映射个数
(2) 若题为“将20本书分送给3人,使得其中两人得
6本,另一人得8本”呢?
例3. 将2n个人分成n组,使得每组2人,问有多少
种分法?
注: (1) 此即将2n个不同的球放到n个相同的盒子中,
使得每盒2球的放法数
(2) 注意盒子是否标号,有区别!
(3) 思考:将n个不同的物体放到k个相同的盒子里,
使得第i个盒中恰含有ni个物体的放法数有多少?
§2. 重复组合
一. 引例与简介
1. 例1:在三元集{a,b,c}中取两个,则
(2). 元素允许重复的组合有6个:
aa, bb, cc, ab, ac, bc
(1). 元素不允许重复的组合有C(3,2)=3个:
ab, ac, bc
2. 定义1. 从多重集S中不计次序地选出r个元素,即
为S的r-组合.
重数无限制的重复组合计数问题
重数确定的重复组合计数问题
各元的重数分别限定于某些特定子集的重复组合
计数问题
3. 重复组合计数问题的类型
注:本节考虑重数无限制的重复组合问题
1 21. { , , , }
1
.
kS a a a r
k r
r
定理1. 多重集合 的 重复组合数
为
1 2
Proof : (1)
.k
S r
x x x r
集的 组合数等于如下不定方程的非负
整数解的个数: + + + =
(2)
{( 1) , 1}T k r
此不定方程的非负整数解的个数即为多重集
的全排列数.
( 1 )
(3)
( 1)! !
k r
N
k r
!
二. 关于重复组合的若干结论
1 1 2 2. { , , , },
1
.
k k
i
S n a n a n a S r
k r
n r
r
推论1 则 的 组合数
为 ,这里
注: (1) r-组合数与不定方程的非负整数解之间可形成
一一对应
1
(2) 1 .
k r
k r r
r
即为 元集的 元子集的个数
(3) 集合S={1,2, …,k}的r重复组合与T={1,2,…,k+r-1}
的r非重复组合可形成一一对应
1 2
1 2
{ 1, 2, , }
1
1 0 1 1 1
{1,2, , 1}
r
r
S k r
y y y k
y y y r k r
T k r r
的 重复组合
即:
即:
的 元子集
对应如下:
1 22. . { , , }
1
).
1
kM a a a r
r
r
r k
k
定理2 从多重集 中取 个
元,要求每个不同元至少出现一次,则其 组合数为
,(
1 2
Proof : (1)
.k
r
x x x r
此 组合数等于如下不定方程的正整数解
的个数: + + + =
1 2 (2) ky y y r k对应于不定方程 + + + = 的非负
整数解的个数.
3. 变形:
思考一:从k种不同的东西中(每种无限多),取出r个
东西的取法数是多少?
将r个相同的球放到k个不同的盒中的放法数呢?
思考二:从k种不同的东西中(每种无限多),取出r个,
且每种至少拿一个的取法数是多少?
将r个相同的球放到k个不同的盒中,且无空盒的放法
数呢?
4. 推广
将r个相同的球放到k个不同的盒子里,且每个盒中
至少有q个球(r≥kq)的放法数为多少?
1 2 3 4
1 2 3 4
20
3 1 0 5.
x x x x
x x x x
例1:求不定方程 + + + = 的整数解的个数,
其中 , , ,
三. 应用举例
1 22
.
nx x x k
n k
k
例 :求证不等式 + + + 的非负整数解的
个数为
思路: 在原不等式的非负整数解与n+k元集的k元(或
者n元)子集之间建立一一对应关系
1 2 1 1 2 1 2
Pr
( , , , ) ( 1, 2, , )n n
oof
x x x x x x x x x n
:(1)定义映射:
(2)原不等式的非负整数解→ {1,2,…,n+k}的n项递增序列
注:n元集合中的r项递增序列与n元集合中的r元子集
是对应的.
0
1
.
k
j
n j n k
j k
习题:试证明等式:
1 2 1n nx x x x k
另解:
直接与等式 的非负整数解对应
例3:从集合M={1,2,…,n}中取出一个k元子集,使得
其中任意两数之差大于L,问这样的k元子集的个数有多
少?
注: 这样的k元子集称为L间歇的(或称L间隔k-组合)
1 2
1
{ , , , },
k
i i
a a a
a a L
解:(1) 取k元子集依次排列为
则
(3) 将符合条件的子集与不定方程的整数解对应
2 3 11
1 2
1 2 3
1,2 , , , ,
1
k
k
k
x x xx
n a a a
a a a a n
个数
(2) 设在 , 中, 的位置如下:
1 1 1 11, 1,( 1,2, , ),i i i k ka x a a x i k a x n 则:
1 2 1
1 1
0, ( 2, , ), 0
k
i k
x x x n k
x x L i k x
注:这个带限制条件的组合问题可以看做是无重复组合
和重复组合计数公式的一个共同推广:
(3) L=1时,即相应的k元组合中无相继数出现
1 2 1y ( 1)
(4)
0( 1,2, , 1)
k
i
y y n k k L
y i k
此即
( 1)n k L
N
k
故
(1) L=0时,即普通n元集的k元无重复组合
(2) L=-1时,即普通n元集的k元可重复组合
例4:将正整数n有序剖分成k个部分(即表成若干个正
整数之有序和)且允许重复的方案数是多少?
解:对应于不定方程的正整数解的个数问题
注:(1) 即正整数的有序剖分数
(2) 推广:将n有序剖分成k个部分,使得第i个分
部量至少是qi(这里i=1,…,k), 有多少种方案?