高中数学排列组合几种基本方法课件.ppt

1、解排列组合的几种基本方法解排列组合的几种基本方法2015年年12月月23日日相邻元素的排列相邻元素的排列，可以采用，可以采用“局部到整体局部到整体”的排的排法，即将相邻的元素局部排列当成法，即将相邻的元素局部排列当成“一个一个”元素，然元素，然后再进行整体排列后再进行整体排列.1.捆绑法捆绑法例例1 6人排成一排人排成一排.甲、乙两人必须相邻，有多少种不的甲、乙两人必须相邻，有多少种不的排法？排法？ 解：解：（1）分两步进行：分两步进行：甲甲 乙乙第一步，把甲乙排列第一步，把甲乙排列(捆绑捆绑)：55A有120种排法第二步，甲乙两个人的梱看作一个元素与其它的排队：第二步，甲乙两个人的梱看作一个

2、元素与其它的排队：22A有2种捆法2 120240共有种排法 几个元素必须相邻时，几个元素必须相邻时，先捆绑成一个元素，先捆绑成一个元素，再与其它的进行排列再与其它的进行排列.特殊元素优先考虑特殊元素优先考虑例例2 7人排成一排人排成一排.甲、乙两人不相邻，有多少种不同甲、乙两人不相邻，有多少种不同的排法？的排法？ 解：解：分两步进行：分两步进行： 几个元素不能相邻时几个元素不能相邻时,先排一般元素，再让先排一般元素，再让特殊元素插空特殊元素插空.第第1步，把除甲乙外的人排列：步，把除甲乙外的人排列：55A有=120种排法第第2步，将甲乙分别插入到步，将甲乙分别插入到不同的间隙或两端不同的间隙

3、或两端中中(插空插空)：26A有=30种插入法120 303600共有种排法 解决一些不相邻问题解决一些不相邻问题时，可以先排时，可以先排“一般一般”元素然后插入元素然后插入“特殊特殊”元素，使问题得以解决元素，使问题得以解决.2.插空法：插空法：例例3 5个人站成一排，甲总站在乙的右侧的有多少种站法？个人站成一排，甲总站在乙的右侧的有多少种站法？几个元素顺序一定的排列问题几个元素顺序一定的排列问题，一般是先排列，再，一般是先排列，再消去这几个元素的顺序或者，先让其它元素选取位消去这几个元素的顺序或者，先让其它元素选取位置排列，留下来的空位置自然就是顺序一定的了置排列，留下来的空位置自然就是顺

4、序一定的了.3.消序法消序法 /倍缩法倍缩法 (留空法留空法 / 空位法空位法)解法解法1：将将5个人依次站成一排，有个人依次站成一排，有解法解法2：先让甲乙之外的三人从先让甲乙之外的三人从5个位置选出个位置选出3个站好，有个站好，有55A种站法，种站法，然后再消去甲乙之间的顺序数然后再消去甲乙之间的顺序数22A甲总站在乙的右侧的有站法总数为甲总站在乙的右侧的有站法总数为5355225 4 3AAA 35A种站法，留下的两个位置自然给甲乙有种站法，留下的两个位置自然给甲乙有1种站法种站法甲总站在乙的右侧的有站法总数为甲总站在乙的右侧的有站法总数为33551AA 变式：变式：如下图所示如下图所示

5、,有有5横横8竖构成的方格图竖构成的方格图,从从A到到B只能上行或右行共只能上行或右行共有多少条不同的路线有多少条不同的路线? 解解: 如图所示如图所示1234567将一条路经抽象为如下的一个将一条路经抽象为如下的一个排法排法(5-1)+(8-1)=11格格:其中必有四个其中必有四个和七个和七个组成组成!所以所以, 四个四个和七个和七个一个排序就对应一条路经一个排序就对应一条路经,所以从所以从A到到B共有共有 条不同的路径条不同的路径. 3.消序法消序法(留空法留空法)也可以看作是也可以看作是1,2,3,4,5,6,7,顺序一定的排列，顺序一定的排列，有有种排法种排法.11114747AAA1

6、14C要明确堆的顺序要明确堆的顺序（分配）（分配）时，必须先分堆后再时，必须先分堆后再把堆数当作元素个数作全排列把堆数当作元素个数作全排列. 若干个不同的元素局部若干个不同的元素局部“等分等分”有有 个均等个均等堆，要将选取出每一个堆的组合数的乘积除以堆，要将选取出每一个堆的组合数的乘积除以m! 若干个不同的元素若干个不同的元素“等分等分”为为 n个堆，要将个堆，要将选取出每一个堆的组合数的乘积除以选取出每一个堆的组合数的乘积除以n! 非均分堆问题，只要按比例取出分完再用乘非均分堆问题，只要按比例取出分完再用乘法原理作积法原理作积.分组（堆）分配问题的六个模型：分组（堆）分配问题的六个模型：不

7、分配：不分配： 无序不等分；无序等分；无序局部等分；无序不等分；无序等分；无序局部等分； (分配：分配：有序不等分；有序等分；有序局部等分有序不等分；有序等分；有序局部等分.)处理问题的原则：处理问题的原则：4.分组（堆）分配问题分组（堆）分配问题 例例4 有四项不同的工程，要承包给三个工程队，要有四项不同的工程，要承包给三个工程队，要求每个工程队至少要得到一项工程求每个工程队至少要得到一项工程. 共有多少种不同的共有多少种不同的发包方式？发包方式？解法解法1：要完成承包这件事，可以分为两个步骤：要完成承包这件事，可以分为两个步骤：先将四项工程分为三先将四项工程分为三“堆堆”，有，有21142

8、1226C C CA种分法；种分法；再将分好的三再将分好的三“堆堆”依次给三个工程队，依次给三个工程队，有有3!6种给法种给法.共有共有6636种不同的发包方式种不同的发包方式.4.分组（堆）分配问题分组（堆）分配问题解法解法2：3342AC n个个 相同小球相同小球放入放入m (m n)个盒子里，要求每个个盒子里，要求每个盒子里盒子里至少有一个小球至少有一个小球的放法的放法 （等价于（等价于 n个相同小球串个相同小球串成一串从间隙里选成一串从间隙里选m-1个结点剪截成个结点剪截成m段段.）例例5 某校准备参加今年高中数学联赛，把某校准备参加今年高中数学联赛，把16个选手名个选手名额分配到高三

9、年级的额分配到高三年级的1-4 个教学班，个教学班，每班至少一个名额每班至少一个名额，则不同的分配方案共有则不同的分配方案共有_种种.5.隔板法（剪截法）：隔板法（剪截法）：解：解： 问题等价于把问题等价于把16个相同小球放入个相同小球放入4个盒子里，个盒子里，每个盒子至少有一个小球的放法种数问题每个盒子至少有一个小球的放法种数问题. 将将16个小球串成一串，截为个小球串成一串，截为4段有段有 315455C种截断法，对应放到种截断法，对应放到4个盒子里个盒子里.因此，不同的分配方案共有因此，不同的分配方案共有455种种 .变式变式1： 某校准备参加今年高中数学联赛，把某校准备参加今年高中数学

10、联赛，把16个选个选手名额分配到高三年级的手名额分配到高三年级的1-4 个教学班，个教学班，每班的名额每班的名额不少于该班的序号数不少于该班的序号数，则不同的分配方案共有，则不同的分配方案共有_种种.解：解： 问题等价于先给问题等价于先给2班班1个，个，3班班2个，个，4班班3个，再个，再把余下的把余下的10个相同小球放入个相同小球放入4个盒子里，每个盒子至个盒子里，每个盒子至少有一个小球的放法种数问题少有一个小球的放法种数问题. 将将10个小球串成一串，截为个小球串成一串，截为4段有段有 3984C 种截断法，对应放到种截断法，对应放到4个盒子里个盒子里.因此，不同的分配方案共有因此，不同的

11、分配方案共有84种种 .5.隔板法（剪截法）：隔板法（剪截法）：A10变式变式2：100wzyx（1）求这个方程组的正整数解的组数？）求这个方程组的正整数解的组数？（2）求这个方程组的自然数解的组数？）求这个方程组的自然数解的组数？993C104) 1() 1() 1() 1(wzyx或1033C439914299241993CCCCCC6.剔除法剔除法 （间接法）（间接法） 从总体中排除不符合条件的方法数，这是一种间从总体中排除不符合条件的方法数，这是一种间接解题的方法接解题的方法. （对立事件）（对立事件）例例6 从集合从集合0,1,2,3,5,7,11中任取中任取3个元素分别作为直个元素

12、分别作为直线方程线方程Ax+By+C=0中的中的A、B、C，所得的经过坐标，所得的经过坐标原点的直线有原点的直线有_条条.解：所有这样的直线共有解：所有这样的直线共有 条，条，其中不过原点的直线有其中不过原点的直线有 条，条，37210A 所得的经过坐标原点的直线有所得的经过坐标原点的直线有210-18030条条.1266180AA 排列组合应用题往往和代数、三角、立体几何、排列组合应用题往往和代数、三角、立体几何、平面解析几何的某些知识联系，从而增加了问题的综平面解析几何的某些知识联系，从而增加了问题的综合性，解答这类应用题时，要注意使用相关知识对答合性，解答这类应用题时，要注意使用相关知识

13、对答案进行取舍案进行取舍.3062A直接法： 编号为编号为1至至n的的n个小球放入编号为个小球放入编号为1到到 n的的n个盒个盒子里，每个盒子放一个小球子里，每个盒子放一个小球.要求小球与盒子的编号都要求小球与盒子的编号都不同，这种排列称为不同，这种排列称为错位排列错位排列.7.错位法：错位法：特别当特别当n=2, 3 , 4 , 5时的错位数各为时的错位数各为1, 2 , 9 , 44.（列举）（列举）例例7 编号为编号为1至至6的的6个小球放入编号为个小球放入编号为1至至6的的6个个盒子里，每个盒子放一个小球，其中恰有盒子里，每个盒子放一个小球，其中恰有2个小球个小球与盒子的编号相同的放法有与盒子的编号相同的放法有_种种.解：解： 选取编号相同的两组球和盒子的方法有选取编号相同的两组球和盒子的方法有 种，种， 2615C 其余其余4组球与盒子需错位排列有组球与盒子需错位排列有9种放法种放法.故所求方法有故所求方法有159135种种.B 巩固练习巩固练习2. 5个人排成一排，其中个人排成一排，其中甲、乙不相邻甲、乙不相邻的排法种数是（）的排法种数是（） A.6B.12C.72D.144C3. 5个人排成一排，其中个人排成一排，其中甲、乙相邻甲、乙相邻的排法种数是（）的排法种数是（） A.72B.42C.48D.56CA 4.