排列组合问题题型方法总结(二)

1、排列组合常用方法题型总结【知识内容】1基本计数原理加法原理分类计数原理：做一件事，完成它有n 类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2 种方法，在第 n 类办法中有 mn 种不同的方法那么完成这件事共有 N m1 m2 L mn 种不同的方法又称加法原理乘法原理分步计数原理：做一件事，完成它需要分成n 个子步骤，做第一个步骤有m1 种不同的方法，做第二个步骤有m2 种不同方法，做第n 个步骤有 mn 种不同的方法那么完成这件事共有 N m1 m2L mn 种不同的方法又称乘法原理加法原理与乘法原理的综合运用如果完成一件事的各种方法是相互独立的，那么计算完成这件事的方法

2、数时，使用分类计数原理如果完成一件事的各个步骤是相互联系的，即各个步骤都必须完成，这件事才告完成，那么计算完成这件事的方法数时，使用分步计数原理分类计数原理、分步计数原理是推导排列数、组合数公式的理论基础，也是求解排列、组合问题的基本思想方法，这两个原理十分重要必须认真学好，并正确地灵活加以应用2 排列与组合排列： 一般地，从 n 个不同的元素中任取m( m n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出m 个元素的一个排列 （其中被取的对象叫做元素）排列数：从 n 个不同的元素中取出m( m n) 个元素的所有排列的个数，叫做从n 个不同元素中取出 m 个元素的排列数，用

3、符号A nm 表示排列数公式： A m(n1)(2)L(nm1)， m， n N ，并且 m n nnn全排列： 一般地， n 个不同元素全部取出的一个排列，叫做 n 个不同元素的一个全排列n 的阶乘：正整数由1到 n 的连乘积，叫作n 的阶乘，用n! 表示规定： 0!1 组合：一般地，从n 个不同元素中，任意取出m ( m n) 个元素并成一组，叫做从n 个元素中任取m 个元素的一个组合组合数：从 n 个不同元素中， 任意取出 m (m n ) 个元素的所有组合的个数， 叫做从 n 个不同元素中，任意取出 m 个元素的组合数，用符号 Cmn 表示组合数公式： Cnm n(n1)(n 2) L

4、 (nm 1)n !， m, n N ，并且 m n m!m!( n m)!组合数的两个性质：性质1： CnmCnnm ；性质 2： Cnm1CnmCnm 1 （规定 Cn01 ）1排列组合综合问题解排列组合问题， 首先要用好两个计数原理和排列组合的定义， 即首先弄清是分类还是分步，是排列还是组合，同时要掌握一些常见类型的排列组合问题的解法：1特殊元素、特殊位置优先法元素优先法：先考虑有限制条件的元素的要求，再考虑其他元素；位置优先法：先考虑有限制条件的位置的要求，再考虑其他位置；2分类分步法：对于较复杂的排列组合问题，常需要分类讨论或分步计算，一定要做到分类明确，层次清楚，不重不漏3排除法，

5、从总体中排除不符合条件的方法数，这是一种间接解题的方法4捆绑法：某些元素必相邻的排列，可以先将相邻的元素“捆成一个”元素，与其它元素进行排列，然后再给那“一捆元素”内部排列5插空法：某些元素不相邻的排列，可以先排其它元素，再让不相邻的元素插空6插板法： n 个相同元素，分成m(m n) 组，每组至少一个的分组问题把n 个元素排成一排，从n1个空中选 m1 个空，各插一个隔板，有Cnm 11 7分组、分配法：分组问题（分成几堆，无序）有等分、不等分、部分等分之别一般地平均分成n 堆（组），必须除以 n ！，如果有 m 堆（组）元素个数相等， 必须除以 m ！8错位法：编号为1 至 n 的 n 个

6、小球放入编号为1 到 n 的 n 个盒子里，每个盒子放一个小球，要求小球与盒子的编号都不同，这种排列称为错位排列，特别当n 2 ， 3， 4， 5时的错位数各为 1，2， 9， 44关于 5、 6、7 个元素的错位排列的计算，可以用剔除法转化为 2 个、 3 个、 4 个元素的错位排列的问题1排列与组合应用题，主要考查有附加条件的应用问题，解决此类问题通常有三种途径：元素分析法：以元素为主，应先满足特殊元素的要求，再考虑其他元素；位置分析法：以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置；间接法：先不考虑附加条件，计算出排列或组合数，再减去不符合要求的排列数或组合数求解时应注意先把具体

7、问题转化或归结为排列或组合问题； 再通过分析确定运用分类计数原理还是分步计数原理；然后分析题目条件，避免“选取”时重复和遗漏；最后列出式子计算作答22具体的解题策略有：对特殊元素进行优先安排；理解题意后进行合理和准确分类，分类后要验证是否不重不漏；对于抽出部分元素进行排列的问题一般是先选后排，以防出现重复；对于元素相邻的条件， 采取捆绑法； 对于元素间隔排列的问题， 采取插空法或隔板法；顺序固定的问题用除法处理；分几排的问题可以转化为直排问题处理；对于正面考虑太复杂的问题，可以考虑反面对于一些排列数与组合数的问题，需要构造模型【排列组合题型总结】直接法1 . 特殊元素法例 1 用 1，2， 3

8、， 4， 5，6 这 6 个数字组成无重复的四位数，试求满足下列条件的四位数各有多少个（ 1）数字 1 不排在个位和千位（ 2）数字 1 不在个位，数字 6 不在千位。分析：（ 1）个位和千位有5 个数字可供选择 A52，其余 2 位有四个可供选择 A42，由乘法原理： A52A42=2402特殊位置法（2）当 1 在千位时余下三位有A53=60，1 不在千位时， 千位有 A41种选法，个位有 A41种，余下的有 A42，共有 A41 A41 A42=192 所以总共有 192+60=252二间接法当直接法求解类别比较大时，应采用间接法。如上例中（2）可用间接法A642 A53A42=252E

9、g 有五张卡片，它的正反面分别写0 与 1，2 与 3，4 与 5，6 与 7，8 与 9，将它们任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？分析：任取三张卡片可以组成不同的三位数C5323A33个，其中 0 在百位的有C 4222A22个 ， 这 是 不 合 题 意 的 。 故 共 可 组 成 不 同 的 三 位 数C5323A33- C 4222A22=432Eg三个女生和五个男生排成一排女生必须全排在一起有多少种排法（捆绑法）3女生必须全分开（插空法须排的元素必须相邻）两端不能排女生两端不能全排女生如果三个女生占前排，五个男生站后排，有多少种不同的排法插空法 当需排元素中

10、有不能相邻的元素时，宜用插空法。例 3 在一个含有 8 个节目的节目单中，临时插入两个歌唱节目，且保持原节目顺序，有多少中插入方法？分析：原有的 8 个节目中含有9 个空档，插入一个节目后，空档变为10 个，故有A91A101=100 中插入方法。捆绑法当需排元素中有必须相邻的元素时，宜用捆绑法。1四个不同的小球全部放入三个不同的盒子中，若使每个盒子不空，则不同的放法有种（ C 42 A33 ）,2 ，某市植物园要在30 天内接待 20 所学校的学生参观，但每天只能安排一所学校，其中有一所学校人数较多，要安排连续参观2 天，其余只参观一天，则植物园30 天内不同的安排方法有（C 129A192

11、8 ）（注意连续参观 2 天，即需把 30 天种的连续两天捆绑看成一天作为一个整体来选有C 291其余的就是 19 所学校选 28 天进行排列）阁板法名额分配或相同物品的分配问题，适宜采阁板用法例 5某校准备组建一个由12 人组成篮球队，这 12 个人由 8 个班的学生组成，每班至少一人，名额分配方案共种 。分析：此例的实质是 12 个名额分配给 8 个班，每班至少一个名额，可在12 个名额种的11 个空当中插入 7 块闸板，一种插法对应一种名额的分配方式，故有C117种五 平均分推问题eg 6本不同的书按一下方式处理，各有几种分发？平均分成三堆，平均分给甲乙丙三人一堆一本，一堆两本，一对三本

12、甲得一本，乙得两本，丙得三本（一种分组对应一种方案）一人的一本，一人的两本，一人的三本分析： 1，分出三堆书（ a1,a2 ）,(a3,a4)，（a5,a6 ）由顺序不同可以有A33 =6 种，而C62C42 C22这 6 种分法只算一种分堆方式，故6 本不同的书平均分成三堆方式有A33=15 种2，六本不同的书，平均分成三堆有x 种，平均分给甲乙丙三人3222就有 x A3 种C 6C4C 212331233 ， C6C5C 35 ， A3 C 6C5C34合并单元格解决染色问题Eg 如图 1，一个地区分为5 个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则不

13、同的着色方法共有种（以数字作答）。分析：颜色相同的区域可能是2、3、4、 5下面分情况讨论 :( ) 当 2、4 颜色相同且3、5颜色不同时，将2、 4 合并成一个单元格，此时不同的4着色方法相当于4 个元素2,4A4的全排列数4（）当 2、4 颜色不同且3、5 颜色相同时，与情形 ( ) 类似同理可得 A4种着色法（）当 2、4 与3、5 分别同色时，将2、4；3、 5 分别合并，这样仅有三个单元格2,43,533从 4 种颜色中选3 种来着色这三个单元格，计有C4 A3 种方法433由加法原理知：不同着色方法共有2 A4C4A3 =48+24=72（种）练习 1（天津卷（文）将 3 种作物种植12345在如图的 5 块试验田里，每快种植一种作物且相邻的试验田不能种植同一作物，不同的种植方法共种（以数字作答） （ 72）2某城市中心广场建造一个花圃，花圃6 分为个部分（如图 3），现要栽种4 种颜色的花，每部分栽种一种且相邻部分不能栽种同一样颜色的话，不同的栽种方法有种（以数字作答） （ 120）5B614D23ACE图 3图 43如图 4，用不同的 5 种颜色分别为 ABCDE五部分着色， 相邻部分不能用同一颜色，但同一种颜色可