4、解排列组合问题常用方法(二十种)

解排列组合问题常用方法（共8页）1解排列组合问题常用方法（二十种）一、定位问题优先法（特殊元素和特殊位置优先法）例1、由01,2,3,4,5，可以组成多少个没有重复数字五位奇数？分析：特殊元素和特殊位置有特殊要求，应优先考虑。末位和首位有特殊要求。先排末位，从1,3,5三个数中任选一个共有13C种组合；然后排首位，从2,4和剩余的两个奇数中任选一个共有14C种组合；最后排中间三个数，从剩余四个数中任选三个共有34A种排列。由分步计数原理得113344288CCA。变式1、7种不同的花种在排成一列的花盆里，若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？分析：先种两种不同的葵花在不受限制的四个花盒中共有24A种排列，再种其它葵花有55A种排列。由分步计数原理得25451440AA。二、相邻问题捆绑法例2、7人站成一排，其中甲乙相邻且丙丁相邻，共有多少种不同的排法？分析：分三步。先将甲乙两元素捆绑成整体并看成一个复合元素，将丙丁两元素也捆绑成整体看成一个复合元素，再与其它元素进行排列，同时在两对相邻元素内部进行自排。由分步计数原理得522522480AAA。变式2、某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为。分析：命中的三枪捆绑成一枪，与命中的另一枪插入未命中四枪形成的五个空位，共有25A种排列。三、相离问题插空法例3、一个晚会节目有4个舞蹈，2个相声，3个独唱，舞蹈不能连续出场，则节目出场顺序有多少种？分析：相离问题即不相邻问题。分两步。第一步排2个相声和3个独唱共有55A种排列，第二步将4个舞蹈插入第一步排好后形成的6个空位中（包含首尾两个空位）共有46A种排列，由分步计数原理得545643200AA。变式3、某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目，如果将这两个新节目插入原节目单中且不相邻，那么不同插法的种数为。分析：将2个新节目插入原定5个节目排好后形成的6个空位中（包含首尾两个空位）共有26A种排列，由分步计数原理得2630A。四、定序问题除序（去重复）、空位、插入法例4、7人排队，其中甲、乙、丙3人顺序一定，共有多少种不同的排法？分析：（除序法）除序法也就是倍缩法或缩倍法。对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。共有不同排法种数为：7733840AA。（空位法）设想有7把椅子，让除甲、乙、丙以外的四人就坐，共有47A种坐法；甲、乙、丙坐其余的三个位置，共有1种坐法。总共有47840A种排法。思考：可以先让甲乙丙就坐吗？（可以）（插入法）先选三个座位让甲、乙、丙三人坐下，共有37C种选法；余下四个空座位让其余四人就坐，共有44A种坐法。总共有3474840CA种排法。变式4、10人身高各不相等，排成前后排，每排5人，要求从左至右身高逐渐增加，共有多少种不同的排法？分析：10人身高各不相等且从左至右身高逐渐增加，说明顺序一定。若排成一排，则只有一种排法；现排成前后两排，因此共有510252C种排法。五、平均分组问题倍除法（去重复法）解排列组合问题常用方法（共8页）2例5、6本不同的书平均分成3堆，每堆2本，有多少种不同的分法？分析：分三步取书有222642CCC种分法，但存在重复计数。记6本书为ABCDEF，若第一步取AB，第二步取CD，第三步取EF，该分法记为ABCDEF，，，则在222642CCC中还有ABCDEF，，、ABCDEF，，、ABCDEF，，、ABCDEF，，、ABCDEF，，共33A种分法，而这些分法仅是ABCDEF，，一种分法。总共应有22264233CCCA种分法。平均分成的组，不管它们的顺序如何，都是一种情况，分组后一定要除以nnA（n为均分的组数），避免重复计数。变式5①、将13个球队分成3组，一组5个队，其它两组4个队，有多少种不同的分法？分析：分三步。第一步取5个队为一组，有513C种分法；余下8个队平均分成两组，每组4个队，有4484CC种分法，但存在重复计数。记8个队为ABCDEFGH，若第二步取ABCD，第三步取EFGH，该分法记为ABCDEFGH，，则在4484CC中还有EFGHABCD，共22A种分法，而这22A种分法是同一种分法。总共应有445841322CCCA种分法。变式5②、10名学生分成3组，其中一组4人，另两组3人，正、副班长不能分在同一组，有多少种不同的分组方法？分析：㈠总的分组方法：分三步。第一步取4人为一组，有410C种分法；余下6个人平均分成两组，每组3个人，有3363CC种分法，但存在重复计数。记6个人为ABCDEF，若第二步取ABC，第三步取DEF，该分法记为ABCDEF，，则在3363CC中还有DEFABC，共22A种分法，而这22A种分法是同一种分法。总共应有3346310222100CCCA种分法。㈡正、副班长同分在4人一组：分三步。第一步在8人中取2人，加上正、副班长共4人为一组，有28C种分法；余下6个人平均分成两组，每组3个人，有3363CC种分法，但存在重复计数。记6个人为ABCDEF，若第二步取ABC，第三步取DEF，该分法记为ABCDEF，，则在3363CC中还有DEFABC，共22A种分法，而这22A种分法是同一种分法。总共应有33263822280CCCA种分法。㈢正、副班长同分在3人一组：分三步。第一步在8人中取4人，有48C种分法；第二步在余下的4人中取3人，有34C种分法；第三步余下1人加上正、副班长形成一组，只有一种分法。总共应有4384280CC种分法。㈠减㈡减㈢得：总共有33334243636310884222221002802801540CCCCCCCCAA种分法。变式5③、某校高二年级共有6个班级，现从外地转入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排种数为。分析：分三步。前两步将转入的4名学生平均分成两组，每组2名学生，有2242CC种分法，但存在重复计数。记4名学生为ABCD，若第一步取AB，第二步取CD，该分法记为ABCD，，则在2242CC中还有CDAB，共22A种分法，而这22A种分法是同一种分法。第三步将分成的两组分配到6个班级，有26A种分法。总共应有2224262290CCAA种分法。六、元素相同问题隔板法例6、有10个运动员名额，分给7个班，每班至少一个，有多少种分配方案？分析：隔板法也就是档板法。分两步。第一步：每班分配1个名额，只有1种分法；第二步：将剩下的解排列组合问题常用方法（共8页）33个名额分配给7个班。取716块相同隔板，连同3个相同名额排成一排，共9个位置。由隔板法知，在9个位置中任取6个位置排上隔板，有69C种排法。每一种插板方法对应一种分法，由分步计数原理知，共有6984C种分法。变式6①、10个相同的球装入5个盒中，每盒至少一球，有多少中装法？分析：分两步。第一步：每盒先装入1个球，只有1种装法；第二步：将剩下的5个球装入5个盒中。取514块相同隔板，连同5个相同的球排成一排，共9个位置。由隔板法知，在9个位置中任取4个位置排上隔板，有49C种排法。每一种插板方法对应一种装法，由分步计数原理知，共有49126C种装法。变式6②、100xyzw，求这个方程的自然数解的组数。分析：取413块相同隔板，连同100个相同的1排成一排，共103个位置。由隔板法知，在103个位置中任取3个位置排上隔板，有3103C种排法。每一种插板方法对应一组数，共有3103176851C组数。七、正难问题则反总体淘汰法（若直接法难，则用间接法）例7、从0123456789，，，，，，，，，十个数字中取出三个，使其和为不小于10的偶数，不同的取法有多少种？分析：直接求不小于10的偶数很困难，可用总体淘汰法。十个数字中有5个偶数5个奇数，所取的三个数字含有3个偶数的取法有35C，只含有1个偶数的取法有1255CC，和为偶数的取法共有123555CCC。淘汰和小于10的偶数共9种024、026、013、015、017、019、213、215、413，符合条件的取法共有1235559CCC。变式7、一个班有43名同学，从中任抽5人，正、副班长、团支部书记至少抽到一人的抽法有多少种?分析：未抽到正、副班长、团支部书记的抽法有540C种；正、副班长、团支部书记至少抽到一人的抽法有554340CC种。八、重排问题求幂法例8、把6名实习生分配到7个车间实习，共有多少种不同的分法？分析：完成此事共分六步：把第一名实习生分配到车间有7种分法，把第二名实习生分配到车间也有7种分法，依此类推，由分步计数原理共有67种不同的分法。变式8①、某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目，如果将这两个新节目插入原节目单中，那么不同插法的种数为。分析：完成此事共分两步：把第一个新节目插入原定5个节目排后形成的六个空中，有6种插法；把第二个新节目插入前面6个节目排后形成的七个空中，有7种插法。由分步计数原理共有6742种不同的插法。变式8②、某8层大楼一楼电梯上来8名乘客，他们到各自的一层下电梯，下电梯的下法有多少种？分析：完成此事共分八步：第一名乘客下电梯有7种下法，第二名乘客下电梯也有7种下法，依此类推，由分步计数原理共有87种不同的下法。九、环（圆）排问题直排法①环形排列问题：如果在圆周上m个不同的位置编上不同的号码，那么从n个不同的元素的中选取m个不同的元素排在圆周上不同的位置，这种排列和直线排列是相同的；如果从n个不同的元素的中选取m个不同的元素排列在圆周上，位置没有编号，元素间的相对位置没有改变，不计顺逆方向，这种排列和直线排列是不同的，这就是环形排列的问题。②环形排列数：一个m个元素的环形排列，相当于一个有m个顶点的多边形，沿相邻两个点的弧线剪断，再拉直就是形成一个直线排列，即一个m个元素的环形排列对应着m个直线排列。设从n个元素中取出m个元素组成的环形排列数为N个，则对应的直线排列数为mN个。又因为从n个元素中取出m个元素排成一排的排列数为mnA个，所以mnmNA，即1mnNAm。③环形排列数公式：解排列组合问题常用方法（共8页）4㈠从n个元素中取出m个元素组成的环形排列数为1mnNAm。㈡n个元素的环形排列数为1!1!nnnNAnnn。例9、8人围桌而坐，共有多少种坐法？分析：围桌而坐与坐成一排的不同点在于坐成圆形没有首尾之分，所以固定一人并从此位置把圆形展成直线（如图所示），其余7人共有81!7!76543215040种不同的坐法。HFDCAABCDEABEGHGF变式9、6颗颜色不同的钻石，可穿成几种钻石圈？分析：可穿成61!5!54321120种不同的钻石圈。十、多排问题单排法例10、8人排成前后两排，每排4人，其中甲、乙在前排，丙在后排，共有多少种排法？分析：8人排前后两排，相当于8人坐8把椅子，可以把椅子排成一排。先排前4个位置上的2个特殊元素甲、乙有24A种排法；再排后4个位置上的2个特殊元素丙有14A种；其余的5人在5个位置上任意排列有55A种。共有2154455760AAA种不同的排法。排好后，按前4人为前排，后4人为后排分成两排即可。变式10、有两排座位，前排11个座位，后排12个座位。现安排2人就坐，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同坐法的种数为。分析：①前后两排共有23个座位。②前排中间第567，，号3个座位甲、乙二人不能坐。③甲、乙二人不能左右相邻。前排第14811，，，号和后排第112，号6个座位，甲、乙中任一人就坐，有16C种坐法，与之相邻座位只能排除一个，另一人有112331118CC