解决排列问题的常用方法-ppt课件.ppt

1、解决排列问题的常解决排列问题的常用方法用方法1ppt课件复习引入：复习引入：什么叫做什么叫做从从n n个不同元素中取出个不同元素中取出m m个元素的一个排列个元素的一个排列？从从n个不同元素中取出个不同元素中取出m（mn）个元素，按照一定的）个元素，按照一定的顺序排成一列，叫做从顺序排成一列，叫做从n个不同元素中取出个不同元素中取出m个元素的个元素的一个排列一个排列从从n个不同的元素中取出个不同的元素中取出m（mn)个元素的所有排列的个个元素的所有排列的个数，叫做从数，叫做从n个不同元素中取出个不同元素中取出m个元素的个元素的排列数排列数. 用符号用符号 表示表示mnA什么叫做什么叫做从从n

2、n个不同元素中取出个不同元素中取出m m个元素的排列数个元素的排列数？排列数的两个公式是什么排列数的两个公式是什么？)1()2)(1(mnnnnAmn!()!mnnAnm（n，mN*，mn）2ppt课件（一一）特殊元素的特殊元素的“优先安排优先安排法法” 对于特殊元素的排列组合问题，一般应先考虑特殊元素，再考虑其他元素。 例1用0，1，2，3，4这五个数，组成没有重复数字的三位数，其中偶数共有（ ）A.24 B.30 C.40 D.60 分析：由于该三位数是偶数，所以末尾数字必须是偶数， 又因为0不能排首位，故0就是其中的“特殊”元素，应优先安排。按0排在末尾和不排在末尾分为两类；1) 0排在

3、末尾时，有 个2) 0不排在末尾时，有 个由分类计数原理，共有偶数30个.2A4111233A A A3ppt课件例例2：（：（1）7位同学站成一排，共有多少种位同学站成一排，共有多少种 不同的排法？不同的排法？分析：问题可以看作分析：问题可以看作7个元素的全排列个元素的全排列.775040A (2) 7位同学站成两排位同学站成两排(前前3后后4)，共有多少种，共有多少种不同的排法？不同的排法？分析分析:根据分步计数原理根据分步计数原理 7 6 5 4 3 2 17!5040 (3) 7位同学站成一排，其中甲站在中间的位位同学站成一排，其中甲站在中间的位置置,共有多少种不同的排法？共有多少种不

4、同的排法？分析分析:可看作甲固定可看作甲固定,其余全排列其余全排列 66720A 4ppt课件(4) 7位同学站成一排，甲、乙只能站在两位同学站成一排，甲、乙只能站在两端的排法共有多少种？端的排法共有多少种？解解:将问题分步将问题分步第一步第一步:甲乙站两端有甲乙站两端有 种种第二步第二步:其余其余5名同学全排列有名同学全排列有 种种22A55A25252400A A共共有有种种答：共有答：共有2400种不同的排列方法。种不同的排列方法。单三步单三步5ppt课件(5) 7位同学站成一排，甲、乙不能站在排位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？头和排尾的排法共有多少种？解法一解

5、法一:(特殊位置法特殊位置法)第一步第一步:从其余从其余5位同学中找位同学中找2人站排头和排尾人站排头和排尾,有有 种种;25A第二步第二步:剩下的全排列剩下的全排列,有有 种种;55A25552400A A共共有有种种答：共有答：共有2400种不同的排列方法。种不同的排列方法。单三步单三步6ppt课件解法二解法二:(特殊元素法特殊元素法)第一步第一步:将甲乙安排在除排头和排尾的将甲乙安排在除排头和排尾的5个个位置中的两个位置上位置中的两个位置上,有有 种种;25A第二步第二步:其余同学全排列其余同学全排列,有有 种种;55A25552400A A共共有有种种答：共有答：共有2400种不同的排

6、列方法。种不同的排列方法。(5) 7位同学站成一排，甲、乙不能站在排位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？头和排尾的排法共有多少种？单三步单三步7ppt课件解法三解法三:(排除法排除法)先全排列有先全排列有 种种,其中甲或乙站排头有其中甲或乙站排头有 种种,甲或乙站排尾的有甲或乙站排尾的有 种种,甲乙分别站在排头和甲乙分别站在排头和排尾的有排尾的有 种种.77A662A662A2525A A7625762542400AAA A共共有有种种答：共有答：共有2400种不同的排列方法。种不同的排列方法。(5) 7位同学站成一排，甲、乙不能站在排位同学站成一排，甲、乙不能站在排头和

7、排尾的排法共有多少种？头和排尾的排法共有多少种？单三步单三步8ppt课件（二）总体淘汰法（二）总体淘汰法 对于含有否定词语的问题，还可以从总体中把不符合要求的除去，此时应注意即不能多减又不能少减，例如在例1中，也可以用此方法解答。五个数组成三位数的全排列有 个，排好后发现0不能排在首位，而且3，1不能排在末尾，这两种不合条件的排法要除去，故有30个偶数。35A9ppt课件（三）合理分类和准确分步（三）合理分类和准确分步 解含有约束条件的排列组合问题，应按元素的性质进行分类，事情的发生的连续过程分步，做到分类标准明确，分步层次清楚，不重不漏。 例2.五人从左到右站成一排，其中甲不站排头，乙不站第

8、二个位置，那么不同的站法有（ ）A.120 B.96 C.78 D.72分析：由题意，可先安排甲，并按其进行分类讨论：1) 若甲在第二个位置上，则剩下的四人可自由安排，有 种方法.2) 若甲在第三或第四个位置上，则根据分布计数原理，不同的站法有 种站法。再根据分类计数原理，不同的站法共有44A113333A A A4113433378AA A A种10ppt课件（四）想邻问题（四）想邻问题捆绑法捆绑法 对于某几个元素要求相邻的排列问题，可先将相邻的元素“捆绑”在一起，看作一个“大”的元素，与其它元素排列，然后再对相邻的元素内部进行排列。例3）7人站成一排照相，要求甲，乙，丙三人相邻，分别有多少

9、种站法？分析：先将甲，乙，丙三人捆绑在一起看作一个元素，与其余4人共有5个元素做全排列，有 种排法，然后对甲，乙，丙三人进行全排列由分步计数原理可得： 种不同排法55A5353A A11ppt课件例例4：七个家庭一起外出旅游，若其中四家是一：七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。成一排照相留念。若三个女孩要站在一起，有多少种不同的排法？若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有 种排法，而三个女孩之间有 种排法，所以不同的排法共有： （种）。5353720A A

10、 55A33A捆 绑 法捆 绑 法单三步单三步12ppt课件若三个女孩要站在一起，四个男孩也要站在一若三个女孩要站在一起，四个男孩也要站在一起，有多少种不同的排法？起，有多少种不同的排法？不同的排法有：不同的排法有：234234288A A A （种）说一说说一说捆绑法一般适用于捆绑法一般适用于 问题的处理。问题的处理。 相邻相邻变式变式1：七个家庭一起外出旅游，若其中四家是：七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。站成一排照相留念。单三步单三步13ppt课件捆绑法捆绑法:对于对于相邻相邻问题问题,常常

11、先将要相邻的元素常常先将要相邻的元素捆绑捆绑在一起在一起,视作为一个元素视作为一个元素,与其余与其余元素全排列元素全排列,再再松绑松绑后它们之间进行全后它们之间进行全排列排列.这种方法就是这种方法就是捆绑法捆绑法.单三步单三步14ppt课件（五）不相邻问题（五）不相邻问题插空法插空法 对于某几个元素不相邻得排列问题，可先将其它元素排好，然后再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可。例4）7人站成一排照相，要求甲，乙，丙三人不相邻，分别有多少种站法？分析：可先让其余4人站好，共有 种排法，再在这4人之间及两端的5个“空隙”中选三个位置让甲，乙，丙插入，则有 种方法，这样共有 种

12、不同的排法。44A35A3445AA15ppt课件若三个女孩互不相邻，有多少种不同的排法？若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有解：先把四个男孩排成一排有 种排法，在每一排种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入列中有五个空档（包括两端），再把三个女孩插入空档中有空档中有 种方法，所以共有：种方法，所以共有： （种）（种）排法。排法。35A44A43451440A A 插 空 法插 空 法变式变式2：七个家庭一起外出旅游，若其中四家是：七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩一个男孩，三家是一个女孩，现将这七个小

13、孩站成一排照相留念。站成一排照相留念。16ppt课件男生、女生相间排列，有多少种不同的排法？男生、女生相间排列，有多少种不同的排法？解：先把四个男孩排成一排有解：先把四个男孩排成一排有 种排法，在每一排种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入列中有五个空档（包括两端），再把三个女孩插入空档中有空档中有 种方法，所以共有：种方法，所以共有： （种）（种）排法。排法。33A44A4343144A A 插 空 法插 空 法变式变式3：七个家庭一起外出旅游，若其中四家是：七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩一个男孩，三家是一个女孩，现将这七个小

14、孩站成一排照相留念。站成一排照相留念。17ppt课件甲、乙两人的两边必须有其他人，有多少种不甲、乙两人的两边必须有其他人，有多少种不 同的排法？同的排法？解：先把其余五人排成一排有 种排法，在每一排列中有四个空档（不包括两端），再把甲、乙插入空档中有 种方法，所以共有： （种）排法。24A55A52541440A A 插 空 法插 空 法变式变式4：七个家庭一起外出旅游，若其中四家是：七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。站成一排照相留念。18ppt课件插空法插空法:对于对于不相邻不相邻问题问题,先将

15、其余元素全排先将其余元素全排列列,再将这些不相邻的元素再将这些不相邻的元素插入空挡插入空挡中中,这种方法就是这种方法就是插空法插空法.单三步单三步19ppt课件（六）顺序固定问题用（六）顺序固定问题用“除法除法” 对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数.例5五人排队，甲在乙前面的排法有几种？分析：若不考虑限制条件，则有 种排法，而甲，乙之间排法有 种，故甲在乙前面的排法只有一种符合条件，故符合条件的排法有 种.55A22A5522AA20ppt课件（七）分排问题用（七）分排问题用“直排法直排法” 把n个元素排成若干排的

16、问题，若没有其他的特殊要求，可采用统一排成一排的方法来处理.例6七人坐两排座位，第一排坐3人，第二排坐4人，则有多少种不同的坐法？ 分析：7个人，可以在前后排随意就坐，再无其他限制条件，故两排可看作一排处理，所以不同的坐法有 种.77A21ppt课件（八）实验（八）实验 题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。 例7将数字1，2，3，4填入标号为1，2，3，4的四个方格内，每个方格填1个，则每个方格的标号与所填的数字均不相同的填法种数有（ ）A.6 B.9 C.11 D.23分析：此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。第一方

17、格内可填2或3或4。如填2，则第二方格中内可填1或3或4。若第二方格内填1，则第三方格只能填4，第四方格应填3。若第二方格内填3，则第三方格只能填4，第四方格应填1。同理，若第二方格内填4，则第三方格只能填1，第四方格应填3。因而，第一格填2有3种方法。不难得到，当第一格填3或4时也各有3种，所以共有9种。22ppt课件（九）消序（九）消序例8有4名男生，3名女生高矮互不相等，先将他们排成一行，要求从左到右，女生从矮到高排列，有多少种排法？分析：先在7个位置上任取4个位置排男生，有种排法。剩余的3个位置排女生，因要求“从矮到高”排，只有一种排法，所以共有 471=840A种23ppt课件（十）

18、住店法（十）住店法解决“允许重复排列问题”要注意区分两类元素： 一类元素可以重复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解。例9七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（ ）A. B. C D.分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，将七名学生看作7家“店”，五项冠军看作5名“客”，每个“客”有7种住宿法，由乘法原理得 种。注：对此类问题，常有疑惑，为什么不以五项冠军作为5家“店”呢？因为几个学生不能同时夺得同一冠军。57577557A57C24ppt课件(十一十一)对应对应【例10】在100名选手之间进行单循环淘汰赛（即一场比赛失败要退出比赛），最后产生一名冠军，问要举行几场？ 分析：要产生一名冠军，需要淘汰掉冠军以外的所有选手，即要淘汰99名选手，淘汰一名选手需要进行一场比赛，所以淘汰99名选手就需要99场比赛。25ppt课件