《排列组合问题的几种基本方法》由会员分享，可在线阅读，更多相关《排列组合问题的几种基本方法（5页珍藏版）》请在金锄头文库上搜索。
1、排列组合问题的几种基本方法1. 1. 分组（堆）问题分组（堆）问题分组（堆）问题的六个模型：分组（堆）问题的六个模型：无序不等分；无序等分；无序局部等分；有序不等分；有序等分；有序局部等分.处理问题的原则：处理问题的原则：若干个不同的元素“等分”为 个堆,要将选取出每一个堆的组合数的乘积除以 m! 若干个不同的元素局部“等分”有 个均等堆,要将选取出每一个堆的组合数的乘积除以 m! 非均分堆问题，只要按比例取出分完再用乘法原理作积.要明确堆的顺序时，必须先分堆后再把堆数当作元素个数作全排列.1. 1. 分组（堆）问题分组（堆）问题例例 1. 1.有四项不同的工程，要发包给三个工程队，要求每个工
2、有四项不同的工程，要发包给三个工程队，要求每个工程队至少要得到一项工程程队至少要得到一项工程. . 共有多少种不同的发包方式？共有多少种不同的发包方式？解：要完成发包这件事，可以分为两个步骤：先将四项工程分为三“堆” ，有 种分法；再将分好的三“堆”依次给三个工程队，有 3!6 种给法.共有 6636 种不同的发包方式.211 421 2 26C C C A2. 2.插空法：插空法：解决一些不相邻问题时，可以先排解决一些不相邻问题时，可以先排“一般一般”元素然后插入元素然后插入“特殊特殊”元素，使问题得以解决元素，使问题得以解决. .例例 2 2 . . 7 7 人排成一排人排成一排. .甲、
3、乙两人不相邻，有多少种不同的排甲、乙两人不相邻，有多少种不同的排法？法？解：分两步进行：第 1 步，把除甲乙外的一般人排列：第 2 步，将甲乙分别插入到不同的间隙或两端中(插孔)： 几个元素不能相邻时几个元素不能相邻时, ,先排一般元素，再让特殊元素先排一般元素，再让特殊元素插孔插孔. .3.3.捆绑法捆绑法相邻元素的排列，可以采用相邻元素的排列，可以采用“局部到整体局部到整体”的排法，即将的排法，即将相邻的元素局部排列当成相邻的元素局部排列当成“一个一个”元素，然后再进行整体元素，然后再进行整体5 5A有=120种排法2 6A有=30种插入法120 30 3600共有种排法排列排列. .例例
4、 3 3 . . 6 6 人排成一排人排成一排. .甲、乙两人必须相邻甲、乙两人必须相邻, ,有多少种不的排法有多少种不的排法? ?解：（1）分两步进行：第一步，把甲乙排列(捆绑)：第二步，甲乙两个人的梱看作一个元素与其它的排队： 甲甲 乙乙几个元素必须相邻时几个元素必须相邻时, ,先捆绑成一个元素，再与其它先捆绑成一个元素，再与其它的进行排列的进行排列. .4. 4.消序法消序法( (留空法留空法) )几个元素顺序一定的排列问题，一般是先排列，再消几个元素顺序一定的排列问题，一般是先排列，再消去这几个元素的顺序去这几个元素的顺序. .或者，先让其它元素选取位置或者，先让其它元素选取位置排列，
5、留下来的空位置自然就是顺序一定的了排列，留下来的空位置自然就是顺序一定的了. .例例 4. 4. 5 5 个人站成一排，甲总站在乙的右侧的有多少个人站成一排，甲总站在乙的右侧的有多少种站法？种站法？解法 1：将 5 个人依次站成一排，有 种站法，2 2A有2种捆法5 5A有120种排法2 120240共有种排法5 5A然后再消去甲乙之间的顺序数甲总站在乙的右侧的有站法总数为解法 2：先让甲乙之外的三人从 5 个位置选出 3 个站好，有 种站法，留下的两个位置自然给甲乙有 1种站法甲总站在乙的右侧的有站法总数为变式：如下图所示变式：如下图所示, ,有有 5 5 横横 8 8 竖构成的方格图竖构成
6、的方格图, ,从从 A A 到到B B 只能上行或右行共有多少条不同的路线只能上行或右行共有多少条不同的路线? ? BA解解: : 如图所示如图所示2 2A 5 35 52 25 4 3AAA 3 5A33 551AA BA将一条路经抽象为如下的一个排法将一条路经抽象为如下的一个排法(5-1)+(8-1)=11(5-1)+(8-1)=11 格格: :1 12 23 34 45 56 67 7其中必有四个其中必有四个和七个和七个组成组成! !所以所以, , 四个四个和七个和七个一个排序就对应一条路经一个排序就对应一条路经, ,所以从所以从 A A 到到 B B 共有共有 条不同的路径条不同的路径. . 也可以看作是也可以看作是1,2,3,4,5,6,7,顺序一定的排列有顺序一定的排列有种排法种排法.11 11 47 47A AA5 14 (5 1) (8 1)11CC
