排列组合问题常见解法.doc

排列组合问题常见解法解决排列组合综合性问题的一般过程如下: 1. 认真审题弄清要做什么事 2. 怎样做才能完成所要做的事, 即采取分步还是分类, 或是分步与分类同时进行, 确定分多少步及多少类。 3. 确定每一步或每一类是排列问题( 有序) 还是组合( 无序) 问题, 元素总数是多少及取出多少个元素.※解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略一、元素分析法在解有限定元素的排列问题时, 首先考虑特殊元素的安排方法, 再考虑其他元素的排法。例1( 06 全国) 安排 7 位工作人员在 5月1 日至 5月7 日值班, 每人值班一天, 其中甲、乙二人都不安排在 5月1 日和 2 日。不同的安排方法共有种(用数字作答) 解: 因甲、乙二人都不安排在 5月1 日和 2日, 所以先安排甲、乙,在5月3 日至 5 月7日5 天中选 2 天安排甲、乙有 25A 种方法,再安排其余 5 人,有 55A 种方法,故共有 55A 25A =2400 种二、位置分析法在解有限定位置的排列问题时, 首先考虑特殊位置的安排方法, 再考虑其他位置的排法。例2 题同例 1解:因5月1 日和 2 日不能安排甲、乙, 所以先安排 5月1日、2日, 在除甲、乙外 5 人中选 2 人安排到 5月1 日、 2 日,有 25A 种方法,再安排其余 5 天,有 55A 种方法,故共有25A 55A =2400 种三、间接法又叫排除法,在解有限定条件的排列问题时,首先求出不加限定条件的排列数,再减去不符合条件的排列数。例3 题同例 1 解:安排 7 人在 5月1 日至 5月7 日值班,有 77A 种方法,其中甲、乙二人都安排在5月1 日和 2 日有 55 22AA 种,甲、乙仅一人安排在 5月1 日和 2 日有 55 22 15 种。不同的安排方法共有 77A -55 22AA -55 22 15 =2400 种四、树图法又称框图法,用树图或框图列出所有排列(或组合) ,从而求出排列数。适合限定条件在 3 个以上,排列组合问题。例4 已知集合 M={a ,b, c}, N={1 ,0 ,-1 }, 在从集合 M 到集合 N 的所有映射 f中, 满足 f(a)+f(b)=f(c) 的映射有多少个? 解:满足条件的映所以满足条件的映射有 7 个。五、逐一插入法若干元素必须按照特定的顺序排列的问题,先将这些“特殊元素”按指定顺序排列,再将“普通元素”逐一插入其间或两端。例5( 06 湖北) 某工程队有 6 项工程需要单独完成, 其中工程乙必须在工程甲完成后才能进行,工程丙必须在工程乙完成后才能进行,有工程丁必须在工程丙完成后立即进行。那么安排这 6 项工程的不同排法种数是。(用数字作答) 解: (逐一插入法)先将工程甲、乙、丙、丁按指定的顺序排成一排,有 1 种方法, 将丙丁看成一项工程,再在甲、乙、丙(丁)之间和两端的 4 个空档安排其余 2 项工程 1 项工程,有14A 种方法, 再在这 4 项工程之间和两端的 5 个空档安排其余 1 项工程,有15A 种方法,所以共有 14A 15A =20 种方法。六、消序法若干元素必须按照特定的顺序排列的问题, 先将所有元素全排列, 再将特殊元素在其位置上换位情况消去(通常除以特殊元素的全排列数) ,只保留指定的一种顺序。例6(