排列与组合.ppt

定义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
Date
1
Deren Chen, Zhejiang Univ.
例1 教室里有两排座位，每排8个。
14个同学上课，5人喜欢前排，4人喜欢后排，求满足要求的座法。
Example 1
P（8，5）P（8，4）P（7，5）
Date
2
Deren Chen, Zhejiang Univ.
定义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
Date
3
Deren Chen, Zhejiang Univ.
排列的函数表示：
|A| = n，B={1,2,…,r}，F:BA
（1）F是一个单射  A的一个r-排列
（2）B到A的所有单射总数  P(n,r)
排列/Permutations
Date
4
Deren Chen, Zhejiang Univ.
排列的球盒模型表示：
|A| = n  n个盒子
B={1,2,…,r}  r个不同的球
F:BA且是单射  每个盒子最多放一个球
 A的一个r-排列
B到A的所有单射总数  球放入盒子的放法总数
 P(n,r)
排列/Permutations
Date
5
Deren Chen, Zhejiang Univ.
定义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
Date
6
Deren Chen, Zhejiang Univ.
例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)
Date
7
Deren Chen, Zhejiang Univ.
组合的函数表示：
|A| = n，B={0，1}，F:AB
使得A中的r个元素的象为1 的F
 A的一个r-组合
C(n,r) = | { F| F:AB  r=|{a|aA F(a)=1}|}|
组合/Combinations
Date
8
Deren Chen, Zhejiang Univ.
组合的球盒模型表示：
B={0，1}  两个盒子
A  n个不同的球
F:BA且使得A中的r个元素的象为1
 指定一个盒子恰好放r个球
 A的一个r-组合
满足条件的F总数 = C(n,r) = 满足条件的球的放法总数
组合/Combinations
Date
9
Deren Chen, Zhejiang Univ.
定理2推论（组合推论） ：
C（n，r）= C（n，n-r）
组合/Combinations
Date
10
Deren Chen, Zhejiang Univ.