44排列与组合.pptx

12/17/20192:11PMDerenChen,、计数原理/:11PMDerenChen,:n个元素的集合A中任意选择r个(rn)进行排列称为A的一个r-排列/r-Permutation定理1:n个元素的集合A的r-排列数为n(n-1)(n-2)…(n-r+1)记为P(n,r)排列/Permutations12/17/20192:11PMDerenChen,,每排8个。14个同学上课,5人喜欢前排,4人喜欢后排,求满足要求的座法。Example1P(8,5)P(8,4)P(7,5)12/17/20192:11PMDerenChen,: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的一个全排列排列/Permutations12/17/20192:11PMDerenChen,:|A|=n,B={1,2,…,r},F:BA(1)F是一个单射A的一个r-排列(2)B到A的所有单射总数P(n,r)排列/Permutations12/17/20192:11PMDerenChen,:|A|=nn个盒子B={1,2,…,r}r个不同的球F:BA且是单射每个盒子最多放一个球A的一个r-排列B到A的所有单射总数球放入盒子的放法总数P(n,r)排列/Permutations12/17/20192:11PMDerenChen,:n个元素的集合A中任意选择r个(rn)称为A的一个r-组合/bination定理2:n个元素的集合A的r-组合数为n(n-1)(n-2)…(n-r+1)/r!记为C(n,r)binations12/17/20192:11PMDerenChen,、12名女士。选出4人组成董事会。(1)至少包含2名女士;(2)同时满足某男某女不能同时参加。Example2(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)12/17/20192:11PMDerenChen,:|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}|}|binations12/17/20192:11PMDerenChen,:B={0,1}两个盒子An个不同的球F:BA且使得A中的r个元素的象为1指定一个盒子恰好放r个球A的一个r-组合满足条件的F总数=C(n,r)=binations