计数原理、排列组合-精简题型.ppt

1、1,例1、 用0，2，3，4，5，五个数字，组成没有重复数字的三位 数，其中偶数共有（ ）。 A 24个 B.30个 C.40个 D.60个 分析由于该三位数为偶数，故末尾数字必为偶数，又因为0不能排首位，故0就是其中的“特殊”元素，应该优先安排，按0排在末尾和0不排在末尾分两类： 1）0排末尾时，有A42个， 2）0不排在末尾时，则有C21A31A31个，由分数计数原理， 共有偶数A42 + C21A31A31=30个，选B。,一、特殊元素和特殊位置优先排,2,*由0,1,2,3,4,5可以组成多少个没有重复数字的五位奇数？ 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了

2、这两个位置。 先排末位共有C31 然后排首位共有C41 最后排其它位置共有A43 由分步计数原理得 C31 C41 A43=288,一、特殊元素和特殊位置优先排-续,3,例2. 5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?,二、 相邻问题捆绑法,解： 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有A66 种排法,其中女生内部也有A33 种排法,根据乘法原理,共有A66A33种不同的排法.,捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须进行排

3、列！,4,例3.一个晚会的节目有4个舞蹈，2个相声，3个独唱，舞蹈节目不能连续出场，则节目的出场顺序有多少种？ 解:分两步进行，第一步排2个相声和3个独唱共有A55种，第二步将4个舞蹈插入第一步排好的5个元素中间及两端的6个空位，共有A64种不同的方法,由分步计数原理,节目的不同顺序共有A55 A64种。,三、 不相邻问题插空法,插空法：元素相隔问题可先把没有位置要求的元素进行排队，再把不相邻元素插入其中间和两端。,5,例4. 9人排成一行，要求甲、乙、丙从左到右排列（不要求必须相邻），有多少种排法？,四、 定序问题倍缩法,定序问题-倍缩法：对于某几个元素顺序一定的排列问题，可先将这几个元素与

4、其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数。,6,例5. 用1、2、3、4、5组成没有重复数字的五位数，其中恰有两偶数夹在1、两个奇数之间，这样的五位数有多少个？,五、小集团问题先整体后局部,小集团排列问题-先整体后局部：小集团排列问题中，先将小集团看做一个元素，进行全排列，再对小集团内部进行全排列 。,解：把、当作一个元素（小集团）与排队，共有 种排法，再排小集团内部，共有 种排法，由分步计数原理，共有 种排法。,7,例6. 把6名学生分配到7个车间实习,共有多少种不同的分法？,六、重排问题 住店法,重排问题-住店法：允许重复的排列问题，是以元素为研究对象，元素不受位置的

5、约束，可以逐一安排各个元素的位置。通常，n个不同的元素没有限制地安排在m个位置上的排列数为mn种。,解：完成此事共分六步:把第1名学生分配到车间有 7 种分法，把第2名学生分配到车间也有7种分法，依此类推,由分步计数原理，共有 76 种不同的分法。,或：7名学生争夺5项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有 75 种。,8,例7. 8人围桌而坐，共有多少种坐法?,七、环排问题 线性排列,环排问题：一般地，n个不同元素作圆形排列，共有(n-1)!种排法。,解：围桌而坐与坐成一排的不同点是：坐成圆形没有首尾之分，所以先固定一人，并从此位置把圆形展成直线，其余7人任意排列，共有(8-1

6、)！种排法，即7！,9,例8. 8人排成前后两排，每排4人，其中甲乙在前排，丙在后排，共有多少排法？,八、分排问题 直排法,分排问题-：一般地，元素分成多排的排列问题，可按一排考虑，有特殊要求，再分段研究。,解：8人排前后两排，相当于8人坐8把椅子，可以把椅子排成一排。前排特殊元素甲、乙先排，有A42种排法，再排后排的特殊元素丙，有A41种排法，其余的5人在5个位置上任意排列，有A55种,则共有A42 A41 A55种排法。,10,例9.有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？,九、相同元素分份(名额分配)问题隔板法,相同元素分份问题-隔板法：一般地，将n个相同的元素分

7、成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法数为Cn-1m-1。,解：10个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。在个空档中选个位置插入隔板，可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法，共有 A96 种分法。,11,例10. 6本不同的书平均分成3堆,每堆2本共有多少分法？,十、平均分组问题用除法,平均分组问题-除法：平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后一定要除以Ann ( n为均分的组数)，以免重复计数。,解：分三步取书得 种方法,但这里出现重复计数的现象,不妨记6本书为

8、ABCDEF，若第一步取AB,第二步取CD,第三步取EF，该分法记为(AB,CD,EF),则 中还有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有 种取法，而这些取法仅是(AB,CD,EF)一种取法,故共有 种分法。,12,例11.由0，1，2，3，4，5六个数字可以组成多少个没有重复的比324105大的数？,十一、数字排序问题查字典法,数字排序问题-查字典法：查字典法应从高位向低位查,依次求出符合要求的个数,根据分类计数原理求出其总数。,解：第1位选4或5时，后5位可以用其余5个数进行全排列；2A55 第1位是3，第2位选4或5

9、时，后4位可以用其余4个数全排列；2A44 第1位是3，第2位是2，第3位是5时，后3位可以用其余3个数全排列；A33 第1位是3，第2位是2，第3位是4，第4位是5时，后2位可以用其余2个数全排列；A22 第1位是3，第2位是2，第3位是4，第4位是1，第5位是5时，第6位只能是0；A11,13,例12. 有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法？,十二、混合问题先选后排,解：第一步从5个球中选出2个，组成复合元共有C52种方法，再把这4个元素(包含一个复合元素)装入4个不同的盒内有A44种方法，根据分步计数原理，装球的方法共有C52 A44种。,14,例1

10、3.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其和为不小于10的偶数,不同的取法有多少种？,十三、正难则反总体淘汰法,分析：三个数的和为偶数，则这三个数必为3个偶数或1偶2奇。 解：直接求不小于10的偶数很困难,可先不考虑和小于10这个条件，用总体淘汰法。这十个数字中有5个偶数5个奇数,所取的三个数，含有3个偶数的取法有C53,含有1个偶数2个奇数的取法有C51C52,和为偶数的取法共有C53 + C51C52 。再淘汰和小于10的偶数共9种，符合条件的取法共有 C53 + C51C52 - 9,15,例14 如图，用5种不同的颜色给图中A、B、C、D四个区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，求有多少种不同的涂色方法？,十四、涂色问题,如题图分四个步骤来完成涂色