排列组合问题经典题型与通用方法讲义-高二下学期数学人教A版（2019）选择性必修第三册.docx

《排列组合问题经典题型与通用方法讲义-高二下学期数学人教A版（2019）选择性必修第三册.docx》由会员分享，可在线阅读，更多相关《排列组合问题经典题型与通用方法讲义-高二下学期数学人教A版（2019）选择性必修第三册.docx（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、排列组合问题经典题型与通用方法1.分类计数原理(加法原理)完成一件事，有类办法，在第1类办法中有种不同的方法，在第2类办法中有种不同的方法，在第类办法中有种不同的方法，那么完成这件事共有：种不同的方法2.分步计数原理（乘法原理）完成一件事，需要分成个步骤，做第1步有种不同的方法，做第2步有种不同的方法，做第步有种不同的方法，那么完成这件事共有：种不同的方法3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法不能完成整个事件一.特殊元素和特殊位置：优先法例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇

2、数.解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有，然后排首位共有，最后排其它位置共有位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件 由分步计数原理得练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素：捆绑法例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法.解：可先将甲乙两

3、元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有种不同的排法要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须排列. 练习:1、某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 2、五人并排站成一排，如果必须相邻且在的右边，则不同的排法有（ ）A、60种 B、48种 C、36种 D、24种解析：把视为一人，且固定在的右边，则本题相当于4人的全排列，种，答案：.三.不相邻：插空法例3.一个晚会

4、节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端解:分两步进行第一步排2个相声和3个独唱共有种，第二步将4舞蹈插入第一步排好的5个元素中间包含首尾两个空位共有种不同的方法,由分步计数原理,节目的不同顺序共有 种练习题1：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30变式：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数

5、为 42 练习题2：马路上有编号为1，2，3，9九只路灯，现要关掉其中的三盏，但不能关掉相邻的二盏或三盏，也不能关掉两端的两盏，求满足条件的关灯方案有多少种？解析：把此问题当作一个排对模型，在6盏亮灯的5个空隙中插入3盏不亮的灯种方法,所以满足条件的关灯方案有10种.四.顺序一定：倍缩、空位、插入例4.7人排队,其中甲乙丙3人顺序一定共有多少不同的排法解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数,则共有不同排法种数是： (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有种方法，其余的三个位置甲乙丙共有 1种

6、坐法，则共有种方法。思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有 方法定序问题可以用倍缩法，还可转化为占位插空模型处理练习1、10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？2、由数字0，1，2，3，4，5组成没有重复数字的六位数，其中个位数字小于十位数字的共有（ ）A、210种 B、300种 C、464种 D、600种解析：按题意，个位数字只可能是0，1，2，3，4共5种情况，分别有个，个，合并总计300个,选（种）五.相同元素分组、分配问题：隔板法例5、有6个相同的小球放入4个编号为1, 2,3,4 的

7、盒子中，求下列问题中不同放法的种数.（1）每个盒子都不空；（2）恰有1个空盒子；（3）恰有2个空盒子.解：（1）先把6个相同的小球排成一行，在首尾2个球的外侧各放置一块隔板，然后在小球之间的5个空隙中任选3个空隙各插一块隔板即可，故共有（种）放法.（2）恰有1个空盒子，插板分两步进行.先在首尾2个球的外侧各放置一块隔板，并在5个空隙中任选2个空隙各插一块隔板，如|0|000|00|，有种插法；然后将剩下的一块隔板与前面任意一块隔板并放形成空盒，如|0|000|00| ,有种插法.故共有 （种）放法.（3）恰有2个空盒子，插板分两步进行.先在首尾2个球的外侧各放置一块隔板，并在5个空隙中任选1个

8、空隙插一块隔板，有种插法，如|00|0000|,然后将剩下的两块隔板插入形成空盒.分两种情况：这两块隔板与前面三块隔板形成不相邻的2个空盒子，如|00|0000|，有种插法.将两块隔板与前面三块隔板之一并放，如|00|0000|，有种插法.故共有（种）放法.变式：某校准备参加高中数学联赛,把16个选手名额分配到高三年级的1,2,3,4四个班，每班至少1个名额.（1）不同的分配方案共有多少种？（2）若每班名额不少于该班的序号数，则不同的分配方案共有多少种？解：（1）问题相当于将16个小球串成一串，插入3块隔板，截为4段，16个小球间有15个空隙，从中选3个插入隔板，插法种数为.故不同的分配方案共

9、有455种.（2）问题等价于先给2班1个小球，3班2个小球，4班3个小球，再把余下的10个相同的小球分给4个班级，求每个班至少分有1个小球的分配方法种数.将10个小球串成一串，截为4段，截法种数为，因此不同的分配方案共有84种.素养小结：相同元素分配问题的处理策略隔板法：将放有小球的盒子紧挨着成一行放置，便可看作排成一行的小球的空隙中插入了若干隔板，相邻两块隔板形成一个“盒”.每一种插入隔板的方法对应着小球放入盒子的一种方法，此法称为隔板法.隔板法专门解决相同元素的分配问题.将n个相同的元素分给m个不同的对象(nm)，每个对象至少分得一个元素，有 种方法.可描述为n1个空中插入m1块板.练习1

10、、有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？ 解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法共有种分法。2、10个相同的球装5个盒中,每盒至少一有多少装法？ 3、求这个方程组的自然数解的组数 变式：方程的正整数解的个数问题：（隔板法）方程（，）的正整数解有多少个？有多少非负整数解个？解析：；4、将20个完全相同的球放入编号为1，2，3，4，5的五个盒子中。（1）若要求每个盒子至少放一个球，则一共有多少种放法？（2）若每个盒子可放任意个球，则一共有多少种放法？（3）

11、若要求每个盒子放的球的个数不小于其编号数，则一共有多少种放法？解析：（1）；（2）；（3）先在编号为1，2，3，4，5的五个盒子中依次放入0,1,2,3,4个球，再只要保证余下的10个球每个盒子至少放一个，则六.不同元素平均分配、平均分组问题除法策略例6（2021全国高二课时练习）按下列要求分配6本不同的书,各有多少种不同的分配方式?（1）分成三份,1份1本,1份2本,1份3本;（2）甲、乙、丙三人中,一人得1本,一人得2本,一人得3本;（3）平均分成三份,每份2本;（4）平均分配给甲、乙、丙三人,每人2本;（5）分成三份,1份4本,另外两份每份1本;（6）甲、乙、丙三人中,一人得4本,另外两

12、人每人得1本;（7）甲得1本,乙得1本,丙得4本.【解析】（1）无序不均匀分组问题.先选本有种选法;再从余下的本中选本有种选法;最后余下的本全选有种选法.故共有 (种)选法.（2）有序不均匀分组问题.由于甲、乙、丙是不同三人,在题的基础上,还应考虑再分配,共有.（3）无序均匀分组问题.先分三步,则应是种选法,但是这里出现了重复.不妨记六本书为,若第一步取了,第二步取了,第三步取了,记该种分法为(,),则种分法中还有(,),(,),(,),(,),(,),共有种情况,而这种情况仅是,的顺序不同,因此只能作为一种分法,故分配方式有.（4）有序均匀分组问题.在题的基础上再分配给个人,共有分配方式 (

13、种).（5）无序部分均匀分组问题.共有 (种)分法.（6）有序部分均匀分组问题.在题的基础上再分配给个人,共有分配方式 (种).（7）直接分配问题.甲选本有种,乙从余下本中选本有种,余下本留给丙有种,共有 (种)选法.素养小结：不同元素分组问题属于“组合”问题，常见的分组问题有三种：完全均匀分组，每组的元素个数均相等.部分均匀分组，应注意不要重复，有n组均匀，最后必须除以n！ .完全非均匀分组，这种分组不考虑重复现象.平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以(为均分的组数)避免重复计数。练习题：1、将13个球队分成3组,一组5个队,其它两组4个队, 有多少分法？（

14、）2.10名学生分成3组,其中一组4人, 另两组3人但正副班长不能分在同一组,有多少种不同的分组方法 （1540）3.某校高二年级共有六个班级，现从外地转 入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为_（）七.重排问题求幂策略例7.把6名实习生分配到7个车间实习,共有多少种不同的分法允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n不同的元素没有限制地安排在m个位置上的排列数为种解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分法，依此类推,由分步计数原理共有种不同的排

15、法练习1.某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为 42 2. 某8层大楼一楼电梯上来8名乘客人,他们到各自的一层下电梯,下电梯的方法八.圆排问题线排法:把个不同元素放在圆周个无编号位置上的排列，顺序（例如按顺时钟）不同的排法才算不同的排列，而顺序相同（即旋转一下就可以重合）的排法认为是相同的，它与普通排列的区别在于只计顺序而无首位、末位之分，下列个普通排列：在圆排列中只算一种，因为旋转后可以重合，故认为相同，个元素的圆排列数有种.因此可将某个元素固定展成单排，其它的元素全排列.例8. 8人围桌而坐,共有多少种坐法

16、?解：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人并从此位置把圆形展成直线其余7人共有（8-1）！种排法即！ 练习1、有6颗颜色不同的钻石，可串成几种钻石圈？60 2、有5对姐妹站成一圈，要求每对姐妹相邻，有多少种不同站法？解析：首先可让5位姐姐站成一圈，属圆排列有种，然后在让妹妹插入其间，每位均可插入其姐姐的左边和右边，有2种方式，故不同的安排方式种不同站法.一般地,n个不同元素作圆形排列,共有(n-1)!种排法.如果从n个不同元素中取出m个元素作圆形排列共有九.多排问题单排法:把元素排成几排的问题可归结为一排考虑，再分段处理。例9.有8人排成前后两排,每排4人,其中甲

17、乙在前排,丙在后排,共有多少排法解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.个特殊元素有种,再排后4个位置上的特殊元素丙有种,其余的5人在5个位置上任意排列有种,则共有种一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究. 练习1、有两排座位，前排11个座位，后排12个座位，现安排2人就座规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 346 2、有8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？解析：看成一排，某2个元素在前半段四个位置中选排2个，有种，某1个元素排在后半段的四个位

18、置中选一个有种，其余5个元素任排5个位置上有种，故共有种排法.十.有选择有排列：从几类元素中取出符合题意的几个元素，再安排到一定的位置上，可用先选后排策略。例10.有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法.解:第一步从5个球中选出2个组成复合元共有种方法.再把4个元素(包含一个复合元素)装入4个不同的盒内有种方法，根据分步计数原理装球的方法共有解决排列组合混合问题,先选后排是最基本的指导思想。此法与相邻元素捆绑策略相似吗?练习1、一个班有6名战士,其中正副班长各1人现从中选4人完成四种不同的任务,每人完成一种任务,且正副班长有且只有1人参加,则不同的选法有 1

19、92 种2、四个不同球放入编号为1，2，3，4的四个盒中，则恰有一个空盒的放法有多少种？解析：先取四个球中二个为一组，另二组各一个球的方法有种，再排：在四个盒中每次排3个有种，故共有种.（区别隔板法）3、9名乒乓球运动员，其中男5名，女4名，现在要从中选4人进行混合双打训练，有多少种不同的选法？解析：先取男女运动员各2名，有种，这四名运动员混和双打练习有中排法，故共有种.十一.小集团：先整体后局部策略例11.用1,2,3,4,5组成没有重复数字的五位数其中恰有两个偶数夹在1,两个奇数之间,这样的五位数有多少个？解：把,当作一个小集团与排队共有种排法，再排小集团内部共有种排法，由分步计数原理共有

20、种排法. 小集团排列问题中，先整体后局部，再结合其它策略进行处理。练习题：.计划展出10幅不同的画,其中1幅水彩画,幅油画,幅国画, 排成一行陈列,要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为2. 5男生和女生站成一排照像,男生相邻,女生也相邻的排法有种十二.正难则反：总体淘汰（特别适合至多至少问题）例12.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其和为不小于10的偶数,不同的 取法有多少种？有些排列组合问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中淘汰.解：这问题中如果直接求不小于10的偶数很困难,可用

21、总体淘汰法。这十个数字中有5个偶数5个奇数,所取的三个数含有3个偶数的取法有,只含有1个偶数的取法有,和为偶数的取法共有。再淘汰和小于10的偶数共9种，符合条件的取法共有练习题：我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?十三染色问题【例4】（2021陕西金台）如图，节日花坛中有5个区域，现有四种不同颜色的花卉可供选择，要求相同颜色的花不能相邻栽种，则符合条件的种植方案有（ ）种A36 B48 C54 D72【解析】由题意，如图，假设5个区域为分别为1、2、3、4、5，分2种情况讨论：当选用3种颜色花卉的时，2、4同色且3、5同色，共有涂色方法种，当

22、4种不同颜色的花卉全选时，即2、4或3、5用同一种颜色，共有种，则不同的种植方法共有种；故选：D.【一隅三反】1（2021广东深圳 ）现有5种不同颜色要对如图所示的五个部分进行着色，要求有公共边界的两块不能用同一种颜色，则不同的着色方法共有（ ）A420种B780种C540种D480种【解析】依题意可知，完成涂色任务可以使用5种，4种，或3种颜色，将区域标号如图.若用5种颜色完成涂色，则种方法；若用4种颜色完成涂色，颜色有种选法，需要2，4同色，或者3，5同色，或者1，3同色，或者1，4同色，故有种；若用3种颜色完成涂色，颜色有种选法，需要2，4同色且3，5同色，或者1，4同色且3，5同色，或

23、者1，3同色且 2，4同色，故有种.所以不同的着色方法共有种.故选：B.2（2021天津滨海）如图，现要用四种不同的颜色，对四边形中的四个区域进行着色，要求有公共边的两个区域不能用同一种颜色，则不同的着色方法数为（ ）A B C D【解析】将四个区域标记为，如下图所示：第一步涂：种涂法，第二步涂：种涂法，第三步涂：种涂法，第四步涂：种涂法，根据分步乘法计数原理可知，一共有种着色方法，故选：A.3（2021全国（理）现有5种不同颜色的染料，要对如图中的四个不同区域进行着色，要求有公共边的两块区域不能使用同一种颜色，则不同的着色方法的种数是A120B140C240D260解：由题意，先涂A处，有5

24、种涂法，再涂B处4种涂法，第三步涂C，若C与A同，则D有四种涂法，若C与A不同，则D有三种涂法，由此得不同的着色方案有54(14+33)=260种,故选D.4（2021吉林汪清县汪清第四中学）如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有（ ）种.A24B48C72D96【解析】首先涂区域有种，其次区域有种，再次区域有种，若区域与区域同色有种，则区域有种，若区域与区域不同色有种，则区域有种，所以不同的着色方法共有，故选：C.5（2021上海市金山中学高二期末）用五种不同颜色给三棱柱的六个顶点涂色，要求每个顶点涂一种颜色，且

25、每条棱的两个顶点涂不同颜色，则不同的涂法有（ ）A种B种C种D种【解析】分以下几种情况讨论：若种颜色全用上，先涂、三点，有种，然后在、三点中选择两点涂另外两种颜色，有种，最后一个点有种选择，此时共有种；若用种颜色染色，由种选择方法，先涂、三点，有种，然后在、三点中需选择一点涂最后一种颜色，有种，不妨设涂最后一种颜色的为点，若点与点同色，则点只有一种颜色可选，若点与点同色，则点有两种颜色可选，此时共有种；若用种颜色染色，则有种选择方法，先涂、三点,有种，点有种颜色可选,则、的颜色只有一种选择，此时共有.由分类加法计数原理可知，共有种涂色方法.故选D.1234566.在如图所示的六个空格里涂上红黄

26、蓝三种颜色，每种颜色只能涂两次，要求相邻空格不同色，请问一共有多少种涂法？解：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次，分为两类：第一类可按一下步骤进行：第1步：涂第一格，有3种方法； 第2步：涂第二格，有2种方法；第3步：用与第一格不同的颜色涂第三格，有1种方法；第4步：第四格可以涂与第三格颜色不同的，有2种方法。第5步：用不同的两色涂剩下的两格，有2种方法； 所以有3*2*1*2*224种第二类可按一下步骤进行：第1步：涂第一格，有3种方法；第2步：涂第二格，有2种方法；第3步：用与第一格相同的颜色涂第三格，有1种方法；第4步：第四格只能用没有用过的颜色涂，有种方法。第5步：第五格只能

27、用涂第二格的颜色，第六格只能用涂第四格的颜色，有1种方法；所以有3*2*1*1*16种所以，共有24+630种涂法。7. 某城市在中心广场建造一个花圃，花圃分为6个部分（如图），现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，则不同的栽种方法有多少种？（变式：若要栽种5种颜色的花？）解析:注意4种颜色的花都有种上。（变式：）十四配对（配凑）问题：例14. 5双相异的鞋共10只，现随机地取出6只，恰好能配成2双鞋的取法是多少？解析：练习1、50名选手参加乒乓球淘汰赛比赛,需要打多少场才能产生冠军? 淘汰赛比赛规则是:要淘汰1名选手必须进行1场比赛;反之,每进行1场比赛则淘

28、汰1名选手。答案：49.2、有11名翻译人员，其中5名是英语翻译人员，4名是日语翻译人员，另2人英、日语均精通。现从中选出8人组成两个翻译小组，其中4人翻译英语，另4人翻译日语，则有多少种不同的选派方式？解析：十五. 合理分类与分步策略例15.在一次演唱会上共10名演员,其中8人能能唱歌,5人会跳舞,现要出一个2人唱歌2人伴舞的节目,有多少选派方法解：10演员中有5人只会唱歌，2人只会跳舞3人为全能演员。选上唱歌人员为标准进行研究 只会唱的5人中没有人选上唱歌人员共有种,只会唱的5人中只有1人选上唱歌人员种,只会唱的5人中只有2人选上唱歌人员有种，由分类计数原理共有 种。 本题还有如下分类标准

29、： *以3个全能演员是否选上唱歌人员为标准 *以3个全能演员是否选上跳舞人员为标准 *以只会跳舞的2人是否选上跳舞人员为标准解含有约束条件的排列组合问题，可按元素的性质进行分类，按事件发生的连续过程分步，做到标准明确。分步层次清楚，不重不漏，分类标准一旦确定要贯穿于解题过程的始终。练习题：1.从4名男生和3名女生中选出4人参加某个座谈会，若这4人中必须既有男生又有女生，则不同的选法共有34 2. 3成人2小孩乘船游玩,1号船最多乘3人, 2号船最多乘2人,3号船只能乘1人,他们任选2只船或3只船,但小孩不能单独乘一只船, 这3人共有多少乘船方法. （27）十六.构造模型策略例16. 马路上有编

30、号为1,2,3,4,5,6,7,8,9的九只路灯,现要关掉其中的3盏,但不能关掉相邻的2盏或3盏,也不能关掉两端的2盏,求满足条件的关灯方法有多少种？一些不易理解的排列组合题如果能转化为非常熟悉的模型，如占位填空模型，排队模型，装盒模型等，可使问题直观解决解：把此问题当作一个排队模型在6盏亮灯的5个空隙中插入3个不亮的灯有 种练习题：某排共有10个座位，若4人就坐，每人左右两边都有空位，那么不同的坐法有多少种？（120）十七.实际操作穷举策略例17.设有编号1,2,3,4,5的五个球和编号1,2,3,4,5的五个盒子,现将5个球投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒

31、子的编号相同,有多少投法（贺卡问题）解：从5个球中取出2个与盒子对号有种还剩下3球3盒序号不能对应，利用实际操作法，如果剩下3,4,5号球, 3,4,5号盒3号球装4号盒时，则4,5号球有只有1种装法，同理3号球装5号盒时,4,5号球有也只有1种装法,由分步计数原理有种 3号盒 4号盒 5号盒 练习题：同一寝室4人,每人写一张贺年卡集中起来,然后每人各拿一张别人的贺年卡，则四张贺年卡不同的分配方式有多少种？ (9)对于条件比较复杂的排列组合问题，不易用公式进行运算，往往利用穷举法或画出树状图会收到意想不到的结果十八. 分解与合成策略例18. 30030能被多少个不同的偶数整除分析：先把3003

32、0分解成质因数的乘积形式30030=235 7 1113依题意可知偶因数必先取2,再从其余5个因数中任取若干个组成乘积，所有的偶因数为：练习:正方体的8个顶点可连成多少对异面直线解：我们先从8个顶点中任取4个顶点构成四体共有体共,每个四面体有3对异面直线,正方体中的8个顶点可连成对异面直线分解与合成策略是排列组合问题的一种最基本的解题策略,把一个复杂问题分解成几个小问题逐一解决,然后依据问题分解后的结构,用分类计数原理和分步计数原理将问题合成,从而得到问题的答案 ,每个比较复杂的问题都要用到这种解题策略十九.化归策略例19. 25人排成55方阵,现从中选3人,要求3人不在同一行也不在同一列,不

33、同的选法有多少种？处理复杂的排列组合问题时可以把一个问题退化成一个简要的问题，通过解决这个简要的问题的解决找到解题方法，从而进下一步解决原来的问题解：将这个问题退化成9人排成33方阵,现从中选3人,要求3人不在同一行也不在同一列,有多少选法.这样每行必有1人从其中的一行中选取1人后,把这人所在的行列都划掉，如此继续下去.从33方队中选3人的方法有种。再从55方阵选出33方阵便可解决问题.从55方队中选取3行3列有选法所以从55方阵选不在同一行也不在同一列的3人有选法。练习题:某城市的街区由12个全等的矩形区组成其中实线表示马路，从A走到B的最短路径有多少种？解析：可将图中矩形的一边叫一小段，从

34、到最短路线必须走7小段，其中：向东4段，向北3段；而且前一段的尾接后一段的首，所以只要确定向东走过4段的走法，便能确定路径，因此不同走法有种.二十.数字排序问题查字典策略例20由0，1，2，3，4，5六个数字可以组成多少个没有重复的比324105大的数？解:数字排序问题可用查字典法,查字典的法应从高位向低位查,依次求出其符合要求的个数,根据分类计数原理求出其总数。 练习:用0,1,2,3,4,5这六个数字组成没有重复的四位偶数,将这些数字从小到大排列起来,第71个数是 3140 二十一.树形图穷举策略例21人相互传球,由甲开始发球,并作为第一次传球,经过次传求后,球仍回到甲的手中,则不同的传球

35、方式有_ 对于条件比较复杂的排列组合问题，不易用公式进行运算，树图会收到意想不到的结果练习: 分别编有1，2，3，4，5号码的人与椅，其中号人不坐号椅（）的不同坐法有多少种？二十二.复杂分类问题表格策略例22有红、黄、兰色的球各5只,分别标有A、B、C、D、E五个字母,现从中取5只,要求各字母均有且三色齐备,则共有多少种不同的取法红111223黄123121兰321211取法 解:一些复杂的分类选取题,要满足的条件比较多, 无从入手,经常出现重复遗漏的情况,用表格法,则分类明确,能保证题中须满足的条件,能达到好的效果.二十三：住店法策略解决“允许重复排列问题”要注意区分两类元素：一类元素可以重

36、复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解.例23.七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有 .分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，将七名学生看作7家“店”，五项冠军看作5名“客”，每个“客”有7种住宿法，由乘法原理得7种.二十四：交叉问题集合法：某些排列组合问题几部分之间有交集，可用集合中求元素个数公式例24.从6名运动员中选出4人参加4100米接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同的参赛方案？解析：设全集=6人中任取4人参赛的排列，A=甲跑第一棒的排列，B=乙跑第四棒的排列，根据求集合元素个数的公式得参赛方法共有：种.练习：有3名男生和4名女生按照不同的要求排队，全体站成一排，甲不在最左端，乙不在最右端，求不同的排队方法数解析：法一（间接法）由题知甲在最左端或乙在最右端的排法均有种，甲在最左端且乙在最右端的排法有 种，故排法有（种）法二（直接法）根据题意，分2种情况讨论：甲在最右边，有A66720，甲不站最左边也不在最右边，有A51A51A553000，则有720+30003720种排法12学科网（北京）股份有限公司