44排列与组合.pptx

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