高考数学一轮复习第二十章计数原理20.1两个计数原理、排列与组合课件.ppt

第二十章计数原理20.1两个计数原理、排列与组合,高考数学,1.分类计数原理、分步计数原理(1)完成一件事有几类办法,各类办法相互独立,每类办法中又有多种不同的方法,则完成这件事的不同方法数是各类办法中不同方法种数的和,这就是分类计数原理.(2)完成一件事需要分成n个步骤,每一步的完成有多种不同的方法,则完成这件事的不同方法种数是各步不同的方法种数的乘积,这就是分步计数原理.,知识清单,2.分类计数原理与分步计数原理都涉及完成一件事的不同方法的种数.它们的区别在于:分类计数原理与分类有关,各种方法相互独立,用其中任意一种方法都可以完成这件事;分步计数原理与分步有关,各个步骤相互依存,只有各个步骤都完成了,这件事才算完成了.3.排列(1)定义:从n个不同元素中取出m(mn)个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.(2)排列数定义:从n个不同元素中取出m(mn)个元素的所有不同排列的个数,叫做从n个不同元素中取出m个元素的排列数,用表示.(3)排列数公式:=n(n-1)(n-m+1).(4)全排列:n个不同元素全部取出的一个排列,叫做n个不同元素的一个全排列,=n(n-1)(n-2)321=n!.于是排列数公式写成阶乘形式为,=,规定0!=1.4.组合(1)定义:从n个不同元素中取出m(mn)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合.(2)组合数:从n个不同元素中取出m(mn)个元素的所有不同组合个数,叫做从n个不同元素中取出m个元素的组合数,用表示.(3)计算公式:=.由于0!=1,所以=1.5.组合数的性质,(1)=,(2)=+.,两个基本原理应用的解题策略1.分类计数原理与分步计数原理的区别一个与分类有关,一个与分步有关.在综合运用这两个计数原理时,既要会合理分类,又能合理分步,一般情形是先分类后分步.分类计数原理中无论是哪一类方法都能单独完成这件事;分步计数原理的每一个步骤都依次完成后,这件事才完成.2.计数原理与涂色问题涂色问题是计数原理应用的典型问题.由于涂色本身就是策略的一个运用过程,能较好地考查学生的思维连贯性与敏捷性,加之涂色问题的趣味性,自然成为高考的热点之一.,方法技巧,例1如图,要给1,2,3,4,5五块区域分别涂上四种颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须不同颜色,则不同的涂色方法数为.,解析解法一:按区域顺序分步涂色.先涂5号区域,有4种不同的涂法;涂剩下的4个区域要分两种情形:若1,3号区域同色,则1,3号区域有3种涂法,此时2,4号区域各有2种涂法,由分步计数原理知有322=12种涂法.若1,3号区域不同色,则1,3号区域有32=6种涂法,此时2,4号区域各只有1种涂法,由分步计数原理知有611=6种涂法.由分类和分步计数原理知总共有4(12+6)=72种不同的涂色方法.解法二:按所用颜色种数分类涂色.第一类,4种颜色全用,则1,3号区域同色,且2,4号区域不同色;或1,3号区域不同色,且2,4号区域同色,故有2432=48种不同的涂色方法.,第二类,只用3种颜色,则1,3号区域同色,且2,4号区域也同色,故有=24种不同的涂色方法.由分类计数原理知总共有48+24=72种不同的涂色方法.,答案72,排列、组合及其应用的解题策略求解排列、组合问题的基本思路是“排组分清,加乘明确;有序排列,无序组合;分类相加,分步相乘”.1.简单问题直接法直接列式计算.例2将字母a,a,b,b,c,c排成三行两列,要求每行的字母互不相同,每列的字母也互不相同,则不同的排列方法共有种.,解析从a,b,c中任选两个排在第一行,有种方法,则另一个字母在第二行有种方法,其余则确定,共有=12种方法.,答案12,评析遇到有相同元素的排列问题时,一般应画出图表,这样比较直观,还能避免出现重复计数.,2.相邻问题捆绑法在特定条件下,将几个相关元素当成一个元素来考虑,待整个问题排好之后再考虑它们“内部”的排列,它主要用于解决相邻问题.,例3用字母A、Y,数字1、8、9构成一个字符不重复的五位号牌,要求字母A、Y不相邻,数字8、9相邻,则可构成的号牌个数是.(用数字作答),解析先把8、9捆绑,有2种方法,再把它与1排列,有2种排法,此时共有3个空供字母A、Y插入,有6种方法,故可构成的号牌个数是226=24.,答案24,评析本题考查“相邻”与“不相邻”问题,考查捆绑法和插空法.把相邻元素当成一个元素时,一定要注意这些相邻元素要作全排列.,3.相间问题插空法先把一般元素排列好,然后把特定元素插排在它们之间和两端的空中.例4在1,2,3,4,5,6,7的任一排列a1,a2,a3,a4,a5,a6,a7中,使相邻两数都互质的排列种数为.,解题导引把1,3,5,7作全排列把6插空排好,再把2,4插空排好用分步计数原理得结论,解析先把数字1,3,5,7作全排列,有=24种排法,再排数字6,由于数字6不与3相邻,在排好的排列中,除去3的左、右2个空隙,还有3个空隙可排数字6,故数字6有3种排法,最后排数字2,4,又数字2,4不与6相邻,故在剩下的4个空隙中排上2,4,有种排法,共有3=864种排法.,答案864,4.多元问题分类法将符合条件的排列分为几类(每一类的排列数较易求出),然后根据分类计数原理求出排列总数.例5方程ay=b2x2+c中的a,b,c-3,-2,0,1,2,3,且a,b,c互不相同.在所有这些方程所表示的曲线中,不同的抛物线共有条.,解析a,b均不为0,且b取互为相反数的两数时抛物线相同,故分a取1与a不取1两类:a取1时,b2的取值可分为4,9两类,当b2=4和b2=9时,c都有5种情况,此时有25=10(种);a不取1时,a有种取法,不妨设a取2,则b2的取值有1,4,9三类,当b2=1时,c有4种取法,当b2=4时,c有4种取法,当b2=9时,c有5种取法,此时有(4+4+5)=52(种).故共有10+52=62(种).即不同的抛物线有62条.,答案62,5.至少、至多间接法“至少”“至多”的排列组合问题需分类讨论,且一般分类的情况较多,所以通常用间接法,即排除法.它适用于反面明确且易于计算的问题.例6从5男2女中选3位代表(至少有1位女同志)分别到3个不同的工厂进行调研,不同的分派方法有种.,解析解法一:选出的3位代表为1男2女,则有=5种方法;选出的3位代表为2男1女,则有=20种方法.再将3位代表分配到3个不同的工厂调研,有=6种方法.故分派方法有(5+20)6=150种.解法二:选出的3位代表没有女同志,则有=10种方法,所以选出3位代表,至少有1位女同志的选法有-=25种方法.再将3位代表分配到3个不同的