计数原理排列组合精简题型课件

1 *由由0,1,2,3,4,50,1,2,3,4,5可以组成多少个没有重复数字的五位奇数？可以组成多少个没有重复数字的五位奇数？解解:由于末位和首位有特殊要求由于末位和首位有特殊要求,应该优先安排应该优先安排,以免不合要求的元素占了这两以免不合要求的元素占了这两个位置。个位置。先排末位共有先排末位共有C C3 31 1 然后排首位共有然后排首位共有C C4 41 1 最后排其它位置共有最后排其它位置共有A A4 43 3 由分步计数原理得由分步计数原理得 C C3 31 1 C C4 41 1 A A4 43 3=288=288一、特殊元素和特殊位置优先排一、特殊元素和特殊位置优先排-续续2例例2.2.5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起,有多少种不同的排法有多少种不同的排法?二、二、相邻问题相邻问题捆绑法捆绑法解：解：因为女生要排在一起因为女生要排在一起,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一个人,与与5 5个男生作全排列个男生作全排列,有有A A6 66 6 种排法种排法,其中女生其中女生内部也有内部也有A A3 33 3 种排法种排法,根据乘法原理根据乘法原理,共有共有A A6 66 6A A3 33 3种不同种不同的排法的排法.捆绑法捆绑法:要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题,可以用捆绑法来可以用捆绑法来解决问题解决问题.即将需要相邻的元素合并为一个元素即将需要相邻的元素合并为一个元素,再与其它元素再与其它元素一起作排列一起作排列,同时要注意合并元素内部也必须进行排列！同时要注意合并元素内部也必须进行排列！3例例3 3.一个晚会的节目有一个晚会的节目有4 4个舞蹈，个舞蹈，2 2个相声，个相声，3 3个独唱，舞蹈节目个独唱，舞蹈节目不能连续出场，则节目的出场顺序有多少种？不能连续出场，则节目的出场顺序有多少种？解解:分两步进行，第一步排分两步进行，第一步排2 2个相声和个相声和3 3个独唱共有个独唱共有A A5 55 5种，第二种，第二步将步将4 4个舞蹈插入第一步排好的个舞蹈插入第一步排好的5 5个元素中间及两端的个元素中间及两端的6 6个空个空位，共有位，共有A A6 64 4种不同的方法种不同的方法,由分步计数原理由分步计数原理,节目的不同顺序节目的不同顺序共有共有A A5 55 5 A A6 64 4种。种。三、三、不相邻问题不相邻问题插空法插空法插空法插空法：元素相隔问题可先把没有位置要求的：元素相隔问题可先把没有位置要求的元素进行排队，再把不相邻元素插入其中间和元素进行排队，再把不相邻元素插入其中间和两端。两端。4例例4 4.9.9人排成一行，要求甲、乙、丙从左到右排列（不要求必人排成一行，要求甲、乙、丙从左到右排列（不要求必须相邻），有多少种排法？须相邻），有多少种排法？四、四、定序问题定序问题倍缩法倍缩法定序问题定序问题-倍缩法倍缩法：对于某几个元素顺序一定的排：对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排排列，然后用总的排列数除以这几个元素的全排列数。列数。96993360480ANAA5例例5 5.用用1 1、2 2、3 3、4 4、5 5组成没有重复数字的五位数组成没有重复数字的五位数，其中恰有其中恰有两偶数夹在两偶数夹在1 1、两个奇数之间两个奇数之间，这样的五位数有多少个？这样的五位数有多少个？五、五、小集团问题小集团问题先整体后局部先整体后局部小集团排列问题小集团排列问题-先整体后局部先整体后局部：小集团排列问题中，先将小集团排列问题中，先将小集团看做一个元素，进行全排列，再对小集团内部进行全小集团看做一个元素，进行全排列，再对小集团内部进行全排列排列。解解：把：把、当作一个当作一个元素（元素（小集团小集团）与排队与排队，共有共有 种排法，再排小集团内部种排法，再排小集团内部，共有共有 种排法，种排法，由分步计数原理由分步计数原理，共有共有 种排法种排法。22A2222A A222222A A A6例例6 6.把把6 6名名学学生分配到生分配到7 7个车间实习个车间实习,共有多少种不同的分法？共有多少种不同的分法？六、六、重排问题重排问题 住店法住店法重排问题重排问题-住店法住店法：允许重复的排列问题，是以元素为研究允许重复的排列问题，是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置对象，元素不受位置的约束，可以逐一安排各个元素的位置。通常，。通常，n个个不同的元素没有限制地安排在不同的元素没有限制地安排在m m个位置上的排列个位置上的排列数为数为mn种种。解解：完成此事共分六步：完成此事共分六步:把第把第1 1名名学学生分配到车间有生分配到车间有 7 7 种种分法分法，把第把第2 2名名学学生分配到车间也有生分配到车间也有7 7种分种分法，法，依此类推依此类推,由分步计数原理由分步计数原理，共有共有 7 76 6 种不同的种不同的分分法法。或或：7 7名学生争夺名学生争夺5 5项冠军，每项冠军只能由一人获得，获项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有得冠军的可能的种数有 7 75 5 种。种。7例例7 7.8.8人围桌而坐，共有多少种坐法人围桌而坐，共有多少种坐法?七、七、环环排问题排问题 线性排列线性排列环排问题环排问题：一般地一般地，n个不同元素作圆形排列个不同元素作圆形排列，共有共有(n-1)!种种排法排法。解解：围桌而坐与坐成一排的不同点是：坐成圆形没有首尾围桌而坐与坐成一排的不同点是：坐成圆形没有首尾之分，所以先固定一人，并从此位置把圆形展成直线，之分，所以先固定一人，并从此位置把圆形展成直线，其余其余7 7人任意排列，共有人任意排列，共有(8-1)(8-1)！种排法，即！种排法，即7 7！HFDCAABCDEABEGHGF8例例8 8.8 8人排成前后两排人排成前后两排，每排每排4 4人人，其中甲乙在前排其中甲乙在前排，丙在后排丙在后排，共有多少排法共有多少排法？八、八、分分排问题排问题 直排法直排法分排问题分排问题-：一般地，元素分成多排的排列问题，可按一排：一般地，元素分成多排的排列问题，可按一排考虑，有特殊要求，再分段研究。考虑，有特殊要求，再分段研究。解解：8 8人排前后两排人排前后两排，相当于相当于8 8人坐人坐8 8把椅子把椅子，可以把椅子可以把椅子排成一排排成一排。前排。前排特殊元素特殊元素甲、乙先排，甲、乙先排，有有A A4 42 2种种排法，排法，再再排后排后排排的特殊元素丙的特殊元素丙，有有A A4 41 1种种排法，排法，其余的其余的5 5人在人在5 5个位个位置上任意排列置上任意排列，有有A A5 55 5种种,则共有则共有A A4 42 2 A A4 41 1 A A5 55 5种种排法。排法。9例例9 9.有有1010个运动员名额，分给个运动员名额，分给7 7个班，每班至少一个个班，每班至少一个,有多少种有多少种分配方案？分配方案？九、九、相同元素相同元素分份分份(名额分配名额分配)问题问题隔板隔板法法相同元素相同元素分份分份问题问题-隔板隔板法法：一般地，将：一般地，将n个相同的元素分成个相同的元素分成m份（份（n，m为正整数）为正整数）,每份至少一个元素每份至少一个元素,可以用可以用m-1块隔块隔板，插入板，插入n个元素排成一排的个元素排成一排的n-1个空隙中，所有分法数为个空隙中，所有分法数为Cn-1m-1。解解：1010个名额没有差别，把它们排成一排。相邻名额之间形成个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。在个空档中选个位置插个空隙。在个空档中选个位置插入入隔板，可把名额分成隔板，可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法份，对应地分给个班级，每一种插板方法对应一种分法，共有共有 A A9 96 6 种分法种分法。一一班班二二班班三三班班四四班班五五班班六六班班七七班班10例例1010.6 6本不同的书平均分成本不同的书平均分成3 3堆堆,每堆每堆2 2本共有多少分法？本共有多少分法？十、十、平均分组平均分组问题问题用除法用除法平均分组平均分组问题问题-除法除法：平均分成的组：平均分成的组,不管它们的顺序如何不管它们的顺序如何,都都是一种情况是一种情况,所以分组后一定要除以所以分组后一定要除以Ann(n为为均分的组数均分的组数)，以免重复计数。以免重复计数。解解：分三步取书得分三步取书得 种方法种方法,但这里出现重复计数的现象但这里出现重复计数的现象,不不妨记妨记6 6本书为本书为ABCDEFABCDEF，若第一步取，若第一步取AB,AB,第二步取第二步取CD,CD,第三步取第三步取EFEF，该分法记为，该分法记为(AB,CD,EF),(AB,CD,EF),则则 中还有中还有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有共有 种取法，而这些取法仅是种取法，而这些取法仅是(AB,CD,EF)(AB,CD,EF)一种取法一种取法,故共有故共有 种分法。种分法。222642C C C222642C C C33A22236423/C C CA11例例1111.由由0 0，1 1，2 2，3 3，4 4，5 5六个数字可以组成多少个没有重复六个数字可以组成多少个没有重复的比的比324105324105大的数？大的数？十一、十一、数字排序问题数字排序问题查字典查字典法法数字排序数字排序问题问题-查字典法查字典法：查字典法应从高位向低位查：查字典法应从高位向低位查,依次依次求出符合要求的个数求出符合要求的个数,根据分类计数原理求出其总数。根据分类计数原理求出其总数。解解：第第1 1位选位选4 4或或5 5时，后时，后5 5位可以用其余位可以用其余5 5个数进行全排列；个数进行全排列；2A2A5 55 5 第第1 1位是位是3 3，第，第2 2位选位选4 4或或5 5时，后时，后4 4位可以用其余位可以用其余4 4个数全排列；个数全排列；2A2A4 44 4 第第1 1位是位是3 3，第，第2 2位是位是2 2，第，第3 3位是位是5 5时，后时，后3 3位可以用其余位可以用其余3 3个数全排列；个数全排列；A A3 33 3 第第1 1位是位是3 3，第，第2 2位是位是2 2，第，第3 3位是位是4 4，第，第4 4位是位是5 5时，后时，后2 2位可以用其余位可以用其余2 2个个数全排列；数全排列；A A2 22 2 第第1 1位是位是3 3，第，第2 2位是位是2 2，第，第3 3位是位是4 4，第，第4 4位是位是1 1，第，第5 5位是位是5 5时，第时，第6 6位只位只能是能是0 0；A A1 11 1297221122334455AAAAAN12例例1212.有有5 5个不同的小球个不同的小球,装入装入4 4个不同的盒内个不同的盒内,每盒至少装一个每盒至少装一个球球,共有多少不同的装法？共有多少不同的装法？十二、十二、混合问题混合问题先选后排先选后排 解解：第一步从第一步从5 5个球中选出个球中选出2 2个，组成复合元共有个，组成复合元共有C C5 52 2种方法种方法，再把这，再把这4 4个元素个元素(包含一个复合元素包含一个复合元素)装入装入4 4个不同的盒内个不同的盒内有有A A4 44 4种方法，根据分步计数原理，装球的方法共有种方法，根据分步计数原理，装球的方法共有C C5 52 2 A A4 44 4种。种。13例例1313.从从0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其这十个数字中取出三个数，使其和为不小于和为不小于1010的偶数的偶数,不同的不同的取法有多少种？取法有多少种？十三、十三、正难则反正难则反总体淘汰总体淘汰法法 分析分析：三个数的和为偶数，则这三个数必为：三个数的和为偶数，则这三个数必为3 3个偶数或个偶数或1 1偶偶2 2奇。奇。解解：直接求不小于：直接求不小于1010的偶数很困难的偶数很困难,可可先不考虑和小于先不考虑和小于1010这个条件，这个条件，用用总体淘汰法。这十个数字中有总体淘汰法。这十个数字中有5 5个偶数个偶数5 5个奇数个奇数,所取的三个数所取的三个数，含有含有3 3个偶数的取法有个偶数的取法有C C5 53 3,含有含有1 1个偶数个偶数2 2个奇数个奇数的取法有的取法有C C5 51 1C C5 52 2,和为偶数的和为偶数的取法共有取法共有C C5 53 3+C C5 51 1C C5 52 2 。再淘汰和小于。再淘汰和小于1010的偶数共的偶数共9 9种，符合条件的取种，符合条件的取法共有法共有 C C5 53 3+C C5 51 1C C5 52 2-9-9 14 例例14 14 如如图，用图，用5种不同的颜色给图中种不同的颜色给图中A、B、C、D四个区域涂色，规定每个区域只涂一种四个区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，求有多少种不同颜色，相邻区域颜色不同，求有多少种不同的涂色方法？的涂色方法？十四、十四、涂色问题 如题图分四个步骤来完成涂色这件事需分为四步，第一步如题图分四个步骤来完成涂色这件事需分为四步，第一步涂涂A区有区有5种涂法；第二步涂种涂法；第二步涂B有有4种方法；第三步涂种方法；第三步涂C有有3种方种方法；第四步涂法；第四步涂D有有3种方法种方法(还可以使用涂还可以使用涂A的颜色的颜色)，根据分步，根据分步计数原理共有计数原理共有5433180种涂色方法种涂色方法15 变式变式1 如下图，一个地区分为如下图，一个地区分为5个行政区，现给地图着色，要个行政区，现给地图着色，要求相邻区域不得使用同一颜色，现有求相邻区域不得使用同一颜色，现有4种颜色可供选择，种颜色可供选择，则不同的着色方法共有则不同的着色方法共有_ 种种。