计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,1
4、计数原理 /Counting
4.4 排列与组合
Permutations and Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,2
定义 1,n个元素的集合 A中任意选择 r个（ r? n）
进行排列称为 A的一个 r-排列 /r-Permutation
定理 1,n个元素的集合 A的 r-排列数为
n(n-1)(n-2)…(n -r+1)
记为 P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,3
例 1 教室里有两排座位，每排 8个。
14个同学上课,5人喜欢前排,4人喜欢后排，求满足要求的座法。
Example 1
P（ 8,5） P（ 8,4） P（ 7,5）
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,4
定义 1,n个元素的集合 A中任意选择 r个（ r? n）
进行排列称为 A的一个 r-排列 /r-Permutation
定理 1,n个元素的集合 A的 r-排列数为
n(n-1)(n-2)…(n -r+1) =P(n,r)
特别地，当 r = n 时，记 P(n,r)=n!
称为 A的一个 全排列排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,5
排列的函数表示：
|A| = n,B={1,2,…,r},F:B?A
（ 1） F是一个单射? A的一个 r-排列
（ 2） B到 A的所有 单射总数?P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,6
排列的球盒模型表示：
|A| = n? n个盒子
B={1,2,…,r}? r个不同的球
F:B?A且是单射?每个盒子最多放一个球
A的一个 r-排列
B到 A的所有 单射总数?球放入盒子的放法总数
P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,7
定义 2,n个元素的集合 A中任意选择 r个（ r? n）
称为 A的一个 r-组合 /r-Combination
定理 2,n个元素的集合 A的 r-组合数为
n(n-1)(n-2)…(n -r+1)/r!
记为 C(n,r)
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,8
例 2 一个 CLUB有 10名男士,12名女士。选出 4
人组成董事会。
（ 1）至少包含 2名女士；
（ 2）同时满足某男某女不能同时参加。
Example 2
（ 1） C(12,2)C(10,2)+C(12,3)C(10,1)+C(12,4)
（ 2）上式 - C(11,1)C(9,1)-C(12,2)
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,9
组合的函数表示：
|A| = n,B={0,1},F:A?B
使得 A中的 r个元素的象为 1 的 F
A的一个 r-组合
C(n,r) = | { F| F:A?B? r=|{a|aA?F(a)=1}|}|
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,10
组合的球盒模型表示：
B={0,1}? 两个盒子
A? n个不同的球
F:B?A且使得 A中的 r个元素的象为 1
指定一个盒子恰好放 r个球
A的一个 r-组合满足条件的 F总数 = C(n,r) = 满足条件的球的放法总数组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,11
定理 2推论（组合推论）,
C（ n,r） = C（ n,n-r）
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,12
定理 3（ PASCAL’公式）：
对任意正整数 n,k，其中 n? k，则
C（ n + 1,k） = C（ n,k-1） +C（ n,k）
二项式系数与二项式定理
PASCAL三角形 /杨辉三角形
C（ n + 1,k） = C（ n,k-1） +C（ n,k）
n? k? 0,n,k = 0,1,2,3,…
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,13
定理 4：
对任意正整数 n，
nk=0 C（ n,k） = 2n
二项式系数与二项式定理定理 4证明思路：
利用 |A|=n时,|P（ A） |=2n
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,14
定理 5（ Vandermonde 公式）：
对任意非负整数 m,n,r（ r? m,n）
C（ m+n,r） =
rk=0 C（ m,r-k） C（ n,k）
二项式系数与二项式定理定理 5证明思路：两类不同物体中选择 r个的方式数计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,15
定理 6（ Binomial Theorem/二项式定理）：
对任意正整数 n和变量 x,y
（ x+y） n=?nj=0 C（ n,j） xn-j yj
二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,16
例 3：求（ x+y)25 中 x 12y 13的系数例 4：求（ 2x-3y)25 中 x 12y 13的系数二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,17
二项式定理推论：
（ 1）?nk=0 C（ n,k） = 2n
（ 2）?nk=0 (-1)k C（ n,k） = 0
二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,18
定义 3 n个不同元素的集合 A，每个元素可重复选取，则 A中任意选择 r个（ r? n）进行排列称为 A
的一个 r-可重排列 /r-Permutation with repetition。
排列与组合的推广定理 7 n个不同元素的集合 A，每个元素可重复选取，则 A的 r-可重排列总数为 nr。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,19
定义 4 k个不同元素的重集 A，其中每个元素的重数分别为 n1,n2,…,nk,n1+n2+…+n k =n。则 A中 n个元素进行的一个排列称为 A的一个 n-限重排列 /n-Permutation with
limited repetition。
排列与组合的推广定理 8 A的 r-限重排列总数为
n!/ (n1!n2!…n k!)
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,20
定义 5 n个元素的集合 A中任意选择 r个（ r? n）
进行排列且头尾相连称为 A的一个 r-循环排列 / r-圆排列 / r- Circle Permutation
排列与组合的推广定理 9 n个元素的集合 A的 r-循环排列数为
P(n,r)/r
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,21
定义 6 n个不同元素的集合 A，每个元素可重复选取，则 A中任意选择 r个（ r? n）的方式称为 A的一个 r-可重组合 /r-Combination with repetition。
排列与组合的推广定理 10 n个不同元素的集合 A，每个元素可重复选取，则 A的 r-可重组合总数为
C（ n-1+r,r）
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,22
小 结
1、排列,r-排列、全排列、
r-可重排列,r-限重排列,r-循环排列
2、组合,r-组合,r-可重组合
3、二项式定理与二项式系数：
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,23
进一步的思考
1、其他排列组合问题：
r-可重排列和 r-限重排列的结合
2,二项式定理的进一步考虑,x=1,y=z
3、排列组合的表示
4、应用问题计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,24
练 习
pp.258 17,22,39,62
pp.294 20,35（参考 pp258 t55),38
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,1
4、计数原理 /Counting
4.4 排列与组合
Permutations and Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,2
定义 1,n个元素的集合 A中任意选择 r个（ r? n）
进行排列称为 A的一个 r-排列 /r-Permutation
定理 1,n个元素的集合 A的 r-排列数为
n(n-1)(n-2)…(n -r+1)
记为 P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,3
例 1 教室里有两排座位，每排 8个。
14个同学上课,5人喜欢前排,4人喜欢后排，求满足要求的座法。
Example 1
P（ 8,5） P（ 8,4） P（ 7,5）
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,4
定义 1,n个元素的集合 A中任意选择 r个（ r? n）
进行排列称为 A的一个 r-排列 /r-Permutation
定理 1,n个元素的集合 A的 r-排列数为
n(n-1)(n-2)…(n -r+1) =P(n,r)
特别地，当 r = n 时，记 P(n,r)=n!
称为 A的一个 全排列排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,5
排列的函数表示：
|A| = n,B={1,2,…,r},F:B?A
（ 1） F是一个单射? A的一个 r-排列
（ 2） B到 A的所有 单射总数?P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,6
排列的球盒模型表示：
|A| = n? n个盒子
B={1,2,…,r}? r个不同的球
F:B?A且是单射?每个盒子最多放一个球
A的一个 r-排列
B到 A的所有 单射总数?球放入盒子的放法总数
P(n,r)
排列 /Permutations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,7
定义 2,n个元素的集合 A中任意选择 r个（ r? n）
称为 A的一个 r-组合 /r-Combination
定理 2,n个元素的集合 A的 r-组合数为
n(n-1)(n-2)…(n -r+1)/r!
记为 C(n,r)
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,8
例 2 一个 CLUB有 10名男士,12名女士。选出 4
人组成董事会。
（ 1）至少包含 2名女士；
（ 2）同时满足某男某女不能同时参加。
Example 2
（ 1） C(12,2)C(10,2)+C(12,3)C(10,1)+C(12,4)
（ 2）上式 - C(11,1)C(9,1)-C(12,2)
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,9
组合的函数表示：
|A| = n,B={0,1},F:A?B
使得 A中的 r个元素的象为 1 的 F
A的一个 r-组合
C(n,r) = | { F| F:A?B? r=|{a|aA?F(a)=1}|}|
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,10
组合的球盒模型表示：
B={0,1}? 两个盒子
A? n个不同的球
F:B?A且使得 A中的 r个元素的象为 1
指定一个盒子恰好放 r个球
A的一个 r-组合满足条件的 F总数 = C(n,r) = 满足条件的球的放法总数组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,11
定理 2推论（组合推论）,
C（ n,r） = C（ n,n-r）
组合 /Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,12
定理 3（ PASCAL’公式）：
对任意正整数 n,k，其中 n? k，则
C（ n + 1,k） = C（ n,k-1） +C（ n,k）
二项式系数与二项式定理
PASCAL三角形 /杨辉三角形
C（ n + 1,k） = C（ n,k-1） +C（ n,k）
n? k? 0,n,k = 0,1,2,3,…
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,13
定理 4：
对任意正整数 n，
nk=0 C（ n,k） = 2n
二项式系数与二项式定理定理 4证明思路：
利用 |A|=n时,|P（ A） |=2n
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,14
定理 5（ Vandermonde 公式）：
对任意非负整数 m,n,r（ r? m,n）
C（ m+n,r） =
rk=0 C（ m,r-k） C（ n,k）
二项式系数与二项式定理定理 5证明思路：两类不同物体中选择 r个的方式数计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,15
定理 6（ Binomial Theorem/二项式定理）：
对任意正整数 n和变量 x,y
（ x+y） n=?nj=0 C（ n,j） xn-j yj
二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,16
例 3：求（ x+y)25 中 x 12y 13的系数例 4：求（ 2x-3y)25 中 x 12y 13的系数二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,17
二项式定理推论：
（ 1）?nk=0 C（ n,k） = 2n
（ 2）?nk=0 (-1)k C（ n,k） = 0
二项式系数与二项式定理计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,18
定义 3 n个不同元素的集合 A，每个元素可重复选取，则 A中任意选择 r个（ r? n）进行排列称为 A
的一个 r-可重排列 /r-Permutation with repetition。
排列与组合的推广定理 7 n个不同元素的集合 A，每个元素可重复选取，则 A的 r-可重排列总数为 nr。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,19
定义 4 k个不同元素的重集 A，其中每个元素的重数分别为 n1,n2,…,nk,n1+n2+…+n k =n。则 A中 n个元素进行的一个排列称为 A的一个 n-限重排列 /n-Permutation with
limited repetition。
排列与组合的推广定理 8 A的 r-限重排列总数为
n!/ (n1!n2!…n k!)
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,20
定义 5 n个元素的集合 A中任意选择 r个（ r? n）
进行排列且头尾相连称为 A的一个 r-循环排列 / r-圆排列 / r- Circle Permutation
排列与组合的推广定理 9 n个元素的集合 A的 r-循环排列数为
P(n,r)/r
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,21
定义 6 n个不同元素的集合 A，每个元素可重复选取，则 A中任意选择 r个（ r? n）的方式称为 A的一个 r-可重组合 /r-Combination with repetition。
排列与组合的推广定理 10 n个不同元素的集合 A，每个元素可重复选取，则 A的 r-可重组合总数为
C（ n-1+r,r）
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,22
小 结
1、排列,r-排列、全排列、
r-可重排列,r-限重排列,r-循环排列
2、组合,r-组合,r-可重组合
3、二项式定理与二项式系数：
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,23
进一步的思考
1、其他排列组合问题：
r-可重排列和 r-限重排列的结合
2,二项式定理的进一步考虑,x=1,y=z
3、排列组合的表示
4、应用问题计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,24
练 习
pp.258 17,22,39,62
pp.294 20,35（参考 pp258 t55),38
