计数 4、计数原理 Counting 44排列与组合 Permutations and combinations 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 1 4、计数原理/Counting 4.4 排列与组合 Permutations and Combinations
排列/ Permutations 计数原廷 定义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) 2/24/202111:15PM Deren Chen Zhejiang univ 2
计数原理 2/24/2021 11:15 PM 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
Example 1 计数原廷 例1教室里有两排座位,每排8个。 14个同学上课,5人喜欢前排,4人 喜欢后排,求满足要求的座法。 P(8,5)P(8,4)P(7,5) 2/24/202111:15PM Deren Chen Zhejiang univ 3
计数原理 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 3 例1 教室里有两排座位，每排8个。 14个同学上课，5人喜欢前排，4人 喜欢后排，求满足要求的座法。 Example 1 P（8，5）P（8，4）P（7，5）
排列/ Permutations 计数原廷 定义1:n个元素的集合A中任意选择r个(r≤n 进行排列称为A的一个r排列/r- Permutation 定理1:n个元素的集合A的r排列数为 n(n-1)(n-2)、(nr+1)=P(n,r) 特别地,当r=n时,记P(n,r)=n! 称为A的一个全排列 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM 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
排列/ Permutations 计数原廷 排列的函数表示: 1A|=n,B={1,2,,r},F:B→>A (1)F是一个单射分A的一个r排列 (2)B到A的所有单射总数台→P(n,r) 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM 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
排列/ Permutations 计数原 排列的球盒模型表示: 台n个盒子 B={1,2,,r}兮r个不同的球 FB→A且是单射分每个盒子最多放一个球 分A的一个r-排列 B到A的所有单射总数分球放入盒子的放法总数 分P(n,r 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 6 排列的球盒模型表示： |A| = n n个盒子 B={1,2,…,r} r个不同的球 F:B→A且是单射 每个盒子最多放一个球 A的一个r-排列 B到A的所有单射总数 球放入盒子的放法总数 P(n,r) 排列/Permutations
组合 Combinations 计数原廷 定义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) 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM 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
Example 2 计数原 例2一个CLUB有10名男士、12名女士。选出4 人组成董事会。 (1)至少包含2名女士; (2)同时满足某男某女不能同时参加。 (1)C(12,2)C(10,2)C(12,3)C(10,1)+C(2,4) (2)上式-C(11,1)C(9,1-C(12,2) 2021N
计数原理 2/24/2021 11:15 PM 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)
组合 Combinations 计数原廷 组合的函数表示: A|=n,B={0,1},F:A→>B 使得A中的r个元素的象为1的F 分A的一个r组合 C(n,r)={FF:A>B∧r={aa∈A∧F(a)=13 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM 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|a A F(a)=1}|}| 组合/Combinations
组合 Combinations 计数原廷 组合的球盒模型表示: B=0,1}兮两个盒子 台n个不同的球 FB→A且使得A中的r个元素的象为1 分指定一个盒子恰好放r个球 分A的一个r组合 满足条件的F总数=C(n,r)=满足条件的球的放法总数 2/24/202111:15PM Deren Chen Zhejiang univ
计数原理 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 10 组合的球盒模型表示： B={0，1} 两个盒子 A n个不同的球 F:B→A且使得A中的r个元素的象为1 指定一个盒子恰好放r个球 A的一个r-组合 满足条件的F总数 = C(n,r) = 满足条件的球的放法总数 组合/Combinations