的难题排列组合大全

丙丁史上最全的排列组合难题大总结丙丁一.特殊元素和特殊位置优先策略4,5可以组成多少个没有重复数字五位奇数.解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.先排末位共有C13然后排首位共有C144A344A3434分步计数原理得C1C1A3=288434位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一端的花盆里，问有多少不同的种法二.相邻元素捆绑策略例2.7人站成一排,其中甲乙相邻且丙丁相邻,共有多少种不同的排法.解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有A5A2A2=480种不同的排法522甲甲乙要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需 数为20 三.不相邻问题插空策略目的出场顺序有多少种5步排好的6个元素中间包含首尾两个空位共有种A4不同的方法,由分步计数原6理,节目的不同顺序共有A5A4种元素相离问题可先把没有位置要求的元素进行排队再把不相邻元练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同 插法的种数为30 四.定序问题倍缩空位插入策略例人排队,其中甲乙丙3人顺序一定共有多少不同的排法解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数,则同排法种数是：A7/A373(空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有A4种方法，其余的7三个位置甲乙丙共有1种坐法，则共有A4种方法。7思考:可以先让甲乙丙就坐吗(插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有方法定序问题可以用倍缩法，还可转化高逐渐增加，共有多少排法5五.重排问题求幂策略解:完成此事共分六步:把第一名实习生分配到车间有7种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原理共有76种不同的排法允允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以排各个元素的位置，一般地n不同的元素没有限制地安排在m个位置上1．某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目. 如果将这两个节目插入原节目单中，那么不同插法的种数为42 方法 六.环排问题线排策略4并从此位置把圆形展成直线其余7人共有(8-1)！种排法即7！CDBABCDEFGHAG一般地,一般地,n个不同元素作圆形排列,共有(n-1)!种排法.如果从n个不同元素nnn七.多排问题直排策略例人排成前后两排,每排4人,其中甲乙在前排,丙在后排,共有多少排法4 54455前排4 后排一一般地,元素分成多排的排列问题,可归结为一排考前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是346八.排列组合混合问题先选后排策略装法.5一个复合元素)装入4个不同的盒内有A4种方法，根据分步计数原理装球4的方法共有C2A454解决排列组合混合问题,先选后排是最基本的指导思想.此法与相邻元素务,每人完成一种任务,且正副班长有且只有1人参加,则不同的选法有192种九.小集团问题先整体后局部策略个奇数之间,这样的五位数有多少个解：把1,5,2,4当作一个小集团与3排队共有A2种排法，再排小集团内部2共有A2A2种排法，2共有A2A2种排法，2 222 小集团排列问题中，先整体后局部，再结合其它策要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列 254 255 十.元素相同问题隔板策略解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成9个空隙。在9个空档中选6个位置插个隔板，可把名额分成7份，对应地分给7个班级，每一种插板方法对应一种分法共有C6种分法。9一班五班二班三班六班七班一班五班二班三班六班七班四四班将将n个相同的元素分成m份(n，m为正整数),每份至少一个元素,可xyz+w=100求这个方程组的自然数解的组数十一.正难则反总体淘汰策略493偶数,不同的取法有多少种解：这问题中如果直接求不小于10的偶数很困难,可用总体淘汰法。这十个5C55555数共9种，符合条件的取法共有C1C2+C39555有有些排列组合问题,正面直接考虑比较复杂,而它的反面往往比较人在内的抽法有多少种十二.平均分组问题除法策略解:分三步取书得C2C2C2种方法,但这里出现重复计数的现象,不妨记6本书为 则中还有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有A3种取3法,而这些分法仅是(AB,CD,EF)一种分法,故共有C2C2C2/A3种分法。3平平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以An(n为均分的组数)避免重复计数。n种不同的分组方法(1540)3.某校高二年级共有六个班级，现从外地转个班级且每班安十三.合理分类与分步策略入4名学生，要安排到该年级的两4262为标准进行研究 33 53455种，由分类计数原理共有3353455男生又有女生，则不同的选法共有34方法.(27)下分类标准：否选上跳舞人员为标准都可经得到正确结果十四.构造模型策略不能关掉相邻的2盏或3盏,也不能关掉两端的2盏,求满足条件的关灯方法有多少种5 种一一些不易理解的排列组合题如果能转化为非常熟悉的模型，如占位填空模坐法有多少种(120)十五.实际操作穷举策略投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同,有多少投法分解成几个小问题逐一解决,然后依据问题分解后的结构,用分类计数原理分解成几个小问题逐一解决,然后依据问题分解后的结构,用分类计数原理十七.化归策略5装法,由分步计数原理有2C2种5534对对于条件比较复杂的排列组合问题，不易用公式进行运算，往往利用穷举法1.同一寝室4人,每人写一张贺年卡集中起来,然后每人各拿一张别人的贺年卡，则四张贺年卡不同的分配方式有多少种(9)2.给图中区域涂色,要求相邻区域不同色,现有4种可选颜色,则不同的着色方法11425十六.分解与合成策略依题意可知偶因数必先取2,再从其余5个因数中任取若干个组成乘C1+C2+C3+C4+C555555个顶点可连成多少对异面直线 8 面体有分分解与合成策略是排列组合问题的一种最基本的解题策略,把一个复杂问题同的选法有多少种化成一个简要的问题，通过解决这个简要的问化成一个简要的问题，通过解决这个简要的问:行必有1人从其中的一行中选取1继续下去.从3×3方队中选3人的 1 55 55321处处理复杂的排列组合问题时可以把一个问题退练习题:某城市的街区由12个全等的矩形区组成其中实线表示马路，从A走到B的最短路径有多少种(C3=35)7BA十八.数字排序问题查字典策略数解:N=2A5+2A4+A3+A2+A1=29754321数字排序问题可用查字典法,查字典的法应从高位向低位查,依次求出其符合要求的个数,根据分类计练习:用0,1,2,3,4,5这六个数字组成没有重复的四位偶数,将这些数字从小到大 十九.树图策略例19．3人相互传球,由甲开始发球,并作为第一次传球,经过5次传求后,球仍回到对于条件比较复杂的排列组合问的不同坐法有多少种N=44二十.复杂分类问题表格策略5只,要求各字母均有且三色齐备,则共有多少种不同的取法红红黄兰取法53221311212122131113532545454一一些复杂的分类选取题,要满足的条件比较多,无从入手,二十一：住店法策略解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解.家“店”，五项冠军看作5名“客”，每个“客”有7种住宿法，由乘法原理得75种.染色问题的计数方法根据乘法原理，对各个区域分步染色，这是处理这类问题的基本的要用四种颜色给四川、青藏、西藏、云南四省(区)的地图染色(图1)每一省(区)一种颜色，只要求相邻的省(区)不同色，则不同染色的方法有多少种西藏根据乘法原理，不同的染色方法共有4×3×2×2＝48种2.根据共用了多少种颜色分类讨论，分别计算出各种情形的种数，再用加法原理求出不同年拾方法种数。544例2(2003年全国高考题)如图2，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有多少种23154图2分析依题意至少要选用3种颜色。4444由加法原理可知满足题意的着色方法共有A3＋2A4＝24＋2×24＝72种。443.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不例3用红、黄、蓝、白、黑五种颜色涂在“田”字形的四个小方格内(图3)，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法2134(1)四格涂不同的颜色，方法数为A4；5(2)有且仅有两格涂相同的颜色，即只有一组对角小方格涂相同颜色，涂(1)两组对角小方格涂相同颜色，涂法种数为A2。因此，所求的涂法种数5为A4＋2C1A2＋A2＝260种55453.根据相间区域使用颜色的种类分类讨论着色，要求同一区域染同一种颜色，相邻的两个区域不得使用FFABEDC同一颜色，现有4种不同的颜色可供选择，则有多少种不同的着色方法。44(1)当相间区域A、C、E着三种不同颜色时，有A3种着色方法，此时B、D、44＋192＝732种方法二点染色问题点染色问题，要注意对各点依次染色，主要方法有:(1)根据共用了多少种颜色分类讨论；(2)根据相对顶点是否同色分类讨论。种颜色，并使同一条棱的两端点异色，如果有5种颜色可供使用，那么不同的染色方法SSDCA序序色这总数是多少解法1满足题设条件的染色至少要用三种颜色(1)若恰用三种颜色，可先从五种颜色中任选一种染顶点S，再从余下的(1)若恰用四种颜色，可先从五种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A与B，由于A、B颜色可以交换，故有A2种染法；45422(1)若恰用五种颜色，有A5＝120种染法。综上，满足题意的染色方法数5SSDCA原理，总的染色方法数是60×7＝420种的两个问题，尽管与例5表述方式不同，但具有相同的数学模型，所以都可(1)用五种颜色给图中的5个车站的候DC车牌A、B、C、D、E染色，要求相邻两个车站间E的候车牌的颜色不同，有多少种不同的染色方AB法(图6)着色，要求相邻的区域不同色，共有多少种方案三、线段染色问题，要注意对各条线段依次讨论，主要方法有：(1)根据共用了多少种颜色分类讨论；(2)根据相对的线段是否同色分类讨论。例5用红、黄、蓝、白、四种颜色染矩形ABCD的四条边，每条边只染一种颜色，且使相邻两边染不同的颜色，如果颜色可能反复使用，共有多少种不同的染色方法(图8)解法1(1)使用四种颜色有A4种；4(2)使用三种颜色染色，则必须将一组对染成同色，故有C1C1A2种；423(3)使用两种颜色时，则两组对边必须分CCADB边别同色，有A2种。4因此，所求的染色方法数为A4＋C1C1A2＋A2＝84种44234由乘法原理，总的染色方法数为12×7＝84种。利用相同的方法可解决例7同种颜色的服装，且相邻两个区域的颜色不同，不相邻区域颜色相同与否不14受限制，那么不同的着色方法共有多少种例7用六种颜色给正四面体A－BCD的每条棱染色，要求每条棱只能染一种颜色且共顶点的棱染不同的颜色，问有多少种不同的染色方法(图染色至少要用三种颜色。解(1)若恰用三种颜色染色，则每组对棱必须染同一颜色，而这三组间的颜色不同，故有A3种方法。6(2)若恰用四种颜色染色，则三组对棱中有两组对棱