排列组合问题的几种基本方法(复

1、排列组合问题的几种基本方法 （复习归纳）排列组合问题1 .分组（堆）问题分组（堆）问题的六个模型：无序不等分； 无序等分；无序局部等分；（有序不等分； 有序等分；有序局部等分.）处理问题的原则：若干个不同的元素“等分”为m个堆，要将选 取出每一个堆的组合数的乘积除以 m!若干个不同的元素局部“等分”有 m个均等 堆,要将选取出每一个堆的组合数的乘积除以 m 非均分堆问题，只要按比例取出分完再用乘法 原理作积.要明确堆的顺序时，必须先分堆后再把堆数当 作元素个数作全排列.2 .分组（堆）问题例1.有四项不同的工程，要发包给三个工程 队，要求每个工程队至少要得到一项工程.共有 多少种不同的发包方式

2、？解：要完成发包这件事，可以分为两个步骤： 先将四项工程分为三“堆”，有3 11c42c2c1 日AT种分法；再将分好的三“堆”依次给三个工程队，有3! =6种给法.共有6 X 6= 36种不同的发包方式.2 .插空法：解决一些不相邻问题时，可以先排“一般” 元素然后插入“特殊”元素，使问题得以解决辛 多辛 呈 呈1 11TtA例2.7人排成一排.甲、乙两人不相邻，有多 少种不同的排法？解：分两步进行：有A5=120种排法第1步，把除甲乙外的一般人排列：第2步，将甲乙分别插入到不同的间隙或两端中（插孔）：有解=30种插入法几个元素不能相邻时，先排一 般元素，再让特殊元素插孔.共有120 30=

3、 3600种排法有 P 66P 55 P 22种不同的排法3 .捆绑法相邻元素的排列，可以采用“局部到整体” 的排法，即将相邻的元素局部排列当成“一个” 元素，然后再进行整体排列.例3. 6人排成一排.甲、乙两人必须相邻，有多 少种不的排法？解：（1）分两步进行: 甲乙第一步，把甲乙排列（捆绑）：有A= 2种捆法第二步，甲乙两个人的相I看作一个元素与其它的 排队：有a5= 120种排法几个元素必须相邻时，先捆绑成一个元素，再与其它的进行排列.共有2 120= 240种排法有 P 66 P 55 P 22种不同的排法4 .消序法（留空法）几个元素顺序一定的排列问题，一般是先排 列，再消去这几个元

4、素的顺序.或者，先让其它 元素选取位置排列，留下来的空位置自然就是顺 序一定的了.例4. 5个人站成一排，甲总站在乙的右侧的有 多少种站法？A种站法，解法1:将5个人依次站成一排，有A然后再消去甲乙之间的顺序数§ 5 4 3 尺A一甲总站在乙的右侧的有站法总数为解法2:先让甲乙之外的三人从 5个位置选出3个站好，有A3种站法，留下的两个位置自然给甲乙有1种站法a3 i A甲总站在乙的右侧的有站法总数为4 .消序法（留空法）解：如图所示变式：如下图所示，有5横8竖构成的方格图 从A到B只能上行或右行共有多少条不同的路 线？也可以看作是 1,2,3,4,5,6,7,1回,顺 序荷排列，将

5、一条路经抽象为如下的一个排法(5-1)+(8-1)=11 格：一一一一一一一1234567其中必有四个1和七个一组成！所以，四个T和七个一一个排序就对应一条路 经，5 1 4C(5 1) (8 1) C11所以从A到B共有 条不同的路径.5 .剪截法(隔板法)：n 个 相同小球放入 m(m n)个盒子里， 要求每个盒子里至少有一个小球的放法等价于n个相同小球串成一串从间隙里选 m-1个结点剪 截成m段.例5.某校准备参加今年高中数学联赛，把16 个选手名额分配到高三年级的1-4个教学班，每 班至少一个名额，则不同的分配方案共有 _种. 解：问题等价于把16个相同小球放入4个盒子 里，每个盒子至

6、少有一个小球的放法种数问题.C135455将16个小球串成一串，截为4段有 种截断法，对应放到4个盒子里.因此，不同的分配方案共有 455种.5 .剪截法：n 个 相同小球放入 m(m n)个盒子里， 要求每个盒子里至少有一个小球的放法等价于n个相同小球串成一串从间隙里选 m-1个结点剪 截成m段.变式：某校准备参加今年高中数学联赛，把16个选手名额分配到高三年级的1-4个教学班，每 班的名额不少于该班的序号数，则不同的分配方 案共有 种.解：问题等价于先给2班1个，3班2个，4班3个，再把余下的10个相同小球放入4个盒子 里,每个盒子至少有一个小球的放法种数问题.C； 84将10个小球串成一

7、串，截为4段有种截断法，对应放到4个盒子里.因此，不同的分配方案共有 84种.6 .错位法：编号为1至n的n个小球放入编号为1到n的n 个盒子里，每个盒子放一个小球.要求小球与盒 子的编号都不同，这种排列称为错位排列.特别当n=2,3,4,5时的错位数各为1,2,9,44.例6.编号为1至6的6个小球放入编号为1 至6的6个盒子里，每个盒子放一个小球，其中恰 有2个小球与盒子的编号相同的放法有种.解：选取编号相同的两组球和盒子的方法有2C2 15种，其余4组球与盒子需错位排列有9种放法. 故所求方法有15X9= 135种.7 .剔除法从总体中排除不符合条件的方法数，这 是一种间接解题的方法.排

8、列组合应用题往往和代数、 三角、立 体几何、平面解析几何的某些知识联系，从而增 加了问题的综合性，解答这类应用题时，要注意 使用相关知识对答案进行取舍.中任取3个元素例 7.从集合0,1,2,3,5,7,11分别作为直线方程Ax+By+C=0的A、B、C,所得的经过坐标原点的直线有条.3A3 210解：所有这样的直线共有条,A1 A 180其中不过原点的直线有条，所得的经过坐标原点的直线有 210-180= 30条.巩固练习1 .将3封不同的信投入4个不同的邮筒，则不同的投法的种数是（）A. 34 B.43 C.A43D.C43B2 .从黄瓜、白菜、油菜、扁豆 4种蔬菜品种中选由3种，分别种在不同士质的三块地上， 其中黄瓜必须种植，不同的种植方法共有（）A.24 种 B.18 种C.12 种D.6 种B巩固练习3 . 12名同学分别到三个