1、问题问题2什么叫做排列数?排列数的公式是怎样的?什么叫做排列数?排列数的公式是怎样的?问题问题1什么叫做排列?什么叫做排列?从从n个个不同不同元素中取出元素中取出m(mn)个元素,)个元素,按照一定的顺序按照一定的顺序排成一列,叫做从排成一列,叫做从n个不同元素中取出个不同元素中取出m个元素的一个排个元素的一个排列列从从n个不同元素中取出个不同元素中取出m(mn)个元素的所有排列的个)个元素的所有排列的个数,叫做从数,叫做从n个不同元素中取出个不同元素中取出m个元素的排列数,记作个元素的排列数,记作mnA mnA=n(n-1)(n-2)(n-m+1)mnn!A=(n-m)!(n+1)n!=(n
2、+1)!例例1某年全国足球甲级(某年全国足球甲级(A组)联赛共有组)联赛共有14个队参加,每队个队参加,每队都要与其余各队在主、客场分别比赛一次,共进行多少场比都要与其余各队在主、客场分别比赛一次,共进行多少场比赛?赛?2141413182A解解:任何任何2队间进行一次主场比赛和一次客场比赛,对应于从队间进行一次主场比赛和一次客场比赛,对应于从14个元素中任取个元素中任取2个元素的一个排列,因此总共进行的比赛场个元素的一个排列,因此总共进行的比赛场次数等于排列数次数等于排列数答:共进行了答:共进行了182场比赛场比赛小结:小结:在解排列应用题时,先要认真审题,看这个问题能不能在解排列应用题时,
3、先要认真审题,看这个问题能不能归结为排列问题来解,归结为排列问题来解,(1)n个不同元素是指什么?个不同元素是指什么?(2)m个元素是指什么?个元素是指什么?(3)从)从n个不同元素中取出个不同元素中取出m个元素的每一种排列,对应着什个元素的每一种排列,对应着什么事情?么事情?如果能够的话,再考虑在这个问题里:如果能够的话,再考虑在这个问题里:例例2(l)有)有5本本不同的书,从中选不同的书,从中选3本送给本送给3名同学,每人名同学,每人1本,本,共有多少种不同送法?共有多少种不同送法?(2)有)有5种种不同的书,要买不同的书,要买3本送给本送给3名同学,每人名同学,每人1本,共有本,共有多少
4、种不同的送法?多少种不同的送法?解:解:(l)从)从5本不同的书中选出本不同的书中选出3本分别送给本分别送给3名同学,对应于名同学,对应于从从5个元素中任取个元素中任取3个元素的一个排列,因此不同的送法种数是个元素的一个排列,因此不同的送法种数是3554360A(2)由于有)由于有5种不同的书,送给每个同学的书都有种不同的书,送给每个同学的书都有5种不同种不同的方法,因此送给的方法,因此送给3名同学每人名同学每人1本书的不同方法的种数是本书的不同方法的种数是555125例例3某信号共用红、黄、蓝某信号共用红、黄、蓝3面旗从上到下挂在竖直的旗杆上面旗从上到下挂在竖直的旗杆上表示,每次可以任挂表示
5、,每次可以任挂l面、面、2面或面或3面,并且不同的顺序表示不面,并且不同的顺序表示不同的信号,一共可以表示多少种不同的信号?同的信号,一共可以表示多少种不同的信号?解:解:如果把如果把3面旗看成面旗看成3个元素,则从个元素,则从3个元素中每次取出个元素中每次取出1个、个、2个或个或3个元素的一个排列对应一种信号个元素的一个排列对应一种信号13A23A33A于是,用于是,用1面旗表示的信号有面旗表示的信号有 种,用种,用2面旗表示的信号有面旗表示的信号有种,用种,用3面旗表示的信号有面旗表示的信号有 根据分类计数原理,所求信号的种数是根据分类计数原理,所求信号的种数是12333333232115
6、AAA答:一共可以表示答:一共可以表示15种不同的信号。种不同的信号。注:注:解排列应用题时,要注意分类计数原理与分步计数原理的解排列应用题时,要注意分类计数原理与分步计数原理的运用运用【演练反馈演练反馈】14辆不同公交车,有辆不同公交车,有4位司机,位司机,4位售票员,每辆车上配一位售票员,每辆车上配一位司机和一位售票员,问有多少种不同的搭配方案?位司机和一位售票员,问有多少种不同的搭配方案?2由数字由数字1,2,3,4,5,6可以组成多少个没有重复数字可以组成多少个没有重复数字的正整数?的正整数?320位同学互通一封信,那么通信的次数是多少?位同学互通一封信,那么通信的次数是多少?4444
7、576A A1234566666661956AAAAAA220380A4.7人坐两排座位,第一排坐人坐两排座位,第一排坐3人,第二排坐人,第二排坐4人,不同的坐人,不同的坐法有多少种?法有多少种?5、在、在100名选手之间进行单循环淘汰赛(即一场比赛失败要名选手之间进行单循环淘汰赛(即一场比赛失败要退出比赛),最后产生一名冠军,问要举行几场比赛?退出比赛),最后产生一名冠军,问要举行几场比赛?把两排看作一排来处理把两排看作一排来处理775040A996、一条铁路原有、一条铁路原有n个车站,为适应客运需要,新增加了个车站,为适应客运需要,新增加了m个个车站,客运车站,客运车票增加了车票增加了62
8、种,问原有多少个车站,现有多种,问原有多少个车站,现有多少个车站?少个车站?2262n mnAA(n+m)(n+m-1)-n(n-1)=62m(2n+m-1)=3122,15mn 排列问题与元素的位置有关,解排列排列问题与元素的位置有关,解排列应用题时应从元素或位置出发去分析,结应用题时应从元素或位置出发去分析,结合框图去排列,同时注意分类计数原理与合框图去排列,同时注意分类计数原理与分步计数原理的运用分步计数原理的运用一个问题是否为排列问题,关键是看与元素的顺序是否有一个问题是否为排列问题,关键是看与元素的顺序是否有关,在计算中除运用排列数公式外,还要结合分类计数原理与关,在计算中除运用排列
9、数公式外,还要结合分类计数原理与分步计数原理分步计数原理看下面的问题:看下面的问题:6个队员排成一列进行操练,其中新队员甲不能站排头,也个队员排成一列进行操练,其中新队员甲不能站排头,也不能站排尾,问有多少种不同的站法?不能站排尾,问有多少种不同的站法?分析:分析:这是一个有限制条件的问题,需要在正确理解题意的这是一个有限制条件的问题,需要在正确理解题意的前提下,细致地分析与考察可能的情况,进行恰当的算法设前提下,细致地分析与考察可能的情况,进行恰当的算法设计计mnA=n(n-1)(n-2)(n-m+1)mnn!A=(n-m)!6个队员排成一列进行操练,其中新队员甲不能站排头,也不能站排尾,问
10、个队员排成一列进行操练,其中新队员甲不能站排头,也不能站排尾,问有多少种不同的站法?有多少种不同的站法?14A55A分析分析1:要使甲不在排头和排尾,可先让甲在中间:要使甲不在排头和排尾,可先让甲在中间4个位置中任个位置中任选选1个位置,有个位置,有种站法;种站法;然后对其余然后对其余5人在另外人在另外5个位置上作个位置上作全排列有全排列有种站法。种站法。根据分步计数原理,共有站法根据分步计数原理,共有站法1545480A A分析分析2:由于甲不站排头和排尾,这两个位置只能在其余:由于甲不站排头和排尾,这两个位置只能在其余5个人个人中选中选2个人站,有个人站,有 种站法;种站法;25A 对于中
11、间的四个位置,对于中间的四个位置,4个人有个人有 种站法。种站法。44A 根据分步计数原理,共有站法根据分步计数原理,共有站法 2454480A A分析分析3:若对甲没有限制条件,共有:若对甲没有限制条件,共有 种站法,这里面包含种站法,这里面包含下面三种情况:(下面三种情况:(1)甲在排头;()甲在排头;(2)甲在排尾;()甲在排尾;(3)甲不)甲不在排头,也不在排尾在排头,也不在排尾66A 55A55A甲在排头有甲在排头有 种站法;种站法;甲在排尾有甲在排尾有 种站法,种站法,这都不符合题这都不符合题设条件,从总数中减去这两种情况的排列数即得所求的站法数,设条件,从总数中减去这两种情况的排
12、列数即得所求的站法数,共有共有65652480AA一般地对于有限制条件的排列应用题,可以有两种不同的计算方法:(l)直接计算法)直接计算法 排列问题的限制条件一般表现为:某些元素不能在某个排列问题的限制条件一般表现为:某些元素不能在某个(或某些)位置、某个(或某些)位置只能放某些元素,因(或某些)位置、某个(或某些)位置只能放某些元素,因此进行算法设计时,常优先处理这些特殊要求便有了:先此进行算法设计时,常优先处理这些特殊要求便有了:先处理特殊元素或先处理特殊位置的方法这些统称为处理特殊元素或先处理特殊位置的方法这些统称为“特殊特殊元素(位置)优先考虑法元素(位置)优先考虑法”(2)间接计算法
13、)间接计算法先不考虑限制条件,把所有的排列种数算出,再从中减先不考虑限制条件,把所有的排列种数算出,再从中减去全部不符合条件的排列数,间接得出符合条件的排列种去全部不符合条件的排列数,间接得出符合条件的排列种数这种方法也称为数这种方法也称为“去杂法去杂法”在去杂时,特别注意在去杂时,特别注意要不要不重复重复,不遗漏不遗漏(去尽)(去尽)例例1:5个人站成一排个人站成一排.(l)共有多少种不同的排法?)共有多少种不同的排法?(2)其中甲必须站在中间有多少种不同排法?)其中甲必须站在中间有多少种不同排法?(3)其中甲、乙两人必须相邻有多少种不同的排法?)其中甲、乙两人必须相邻有多少种不同的排法?(
14、4)其中甲、乙两人不相邻有多少种不同的排法?)其中甲、乙两人不相邻有多少种不同的排法?解:(解:(1)由于没有条件限制,)由于没有条件限制,5个人可作全排列,有个人可作全排列,有(2)由于甲的位置已确定,其余)由于甲的位置已确定,其余4人可任意排列,有人可任意排列,有55A44A(3)因为甲、乙两人必须相邻,可视甲、乙在一起为一个元)因为甲、乙两人必须相邻,可视甲、乙在一起为一个元素与其他素与其他3人排列有人排列有 44A而甲、乙又有而甲、乙又有 22A根据分步计数原理共有根据分步计数原理共有4242A A48(捆绑法)(捆绑法)(4)甲、乙两人外的其余)甲、乙两人外的其余3人先排有人先排有
15、33A要使甲、乙不相邻只有排在他们的空档位置,有要使甲、乙不相邻只有排在他们的空档位置,有 24A所以共有所以共有种排法种排法3234A A72或用(或用(1)()(3)(间接法)(间接法)(插空法)(插空法)例例1:5个人站成一排个人站成一排.(5)其中甲、乙两人不站排头和排尾有多少种不同的排法?)其中甲、乙两人不站排头和排尾有多少种不同的排法?(6)其中甲不站排头,乙不站排尾有多少种不同的排法?)其中甲不站排头,乙不站排尾有多少种不同的排法?(5)甲、乙两人不站排头和排尾,则这两个位置可从其余)甲、乙两人不站排头和排尾,则这两个位置可从其余3人中选人中选2人来站有人来站有,23A剩下的人有
16、剩下的人有33A共有共有2333A A36(特殊位置)(特殊位置)或或:甲、乙两人不站排头和排尾,则这两人可从中间:甲、乙两人不站排头和排尾,则这两人可从中间3个位个位置中选置中选2个来站有个来站有,23A剩下的人有剩下的人有33A共有共有2333A A36(特殊元素)(特殊元素)(6)甲站排头有)甲站排头有种排法,乙站排尾有种排法,乙站排尾有种排法,但两种种排法,但两种情况都包含了情况都包含了“甲站排头,乙站排尾甲站排头,乙站排尾”的情况,有的情况,有种排法,种排法,故共有故共有44A44A33A543543A2AA78(间接法)(间接法)思考:用直接法如何解?思考:用直接法如何解?【演练反
17、馈演练反馈】1某一天的课程表要排入语文、数学、英语、物理、体育、某一天的课程表要排入语文、数学、英语、物理、体育、音乐六节课,如果第一节不排体育,最后一节不排数学,一音乐六节课,如果第一节不排体育,最后一节不排数学,一共有多少种不同的排法?共有多少种不同的排法?6546542504AAA51145444504AA A A2在在7名运动员中选出名运动员中选出4名组成接力队,参加名组成接力队,参加4100米接力米接力赛,那么甲、乙两人都不跑中间两棒的安排方法有多少种?赛,那么甲、乙两人都不跑中间两棒的安排方法有多少种?可将接力队分为可将接力队分为“甲、乙两人都不在内甲、乙两人都不在内”“”“甲、乙
18、两人只有甲、乙两人只有一人在内一人在内”,“甲、乙两人都在内甲、乙两人都在内”三种情况:三种情况:“甲、乙两人都不在内甲、乙两人都不在内”有有种方法种方法45A“甲、乙两人只有一人在内甲、乙两人只有一人在内”有有种方法种方法113225A A A“甲、乙两人都在内甲、乙两人都在内”有有种方法种方法2225A A所以共有所以共有400种排法种排法比较复杂的排列应用题往往都有某些限制条件(一般是比较复杂的排列应用题往往都有某些限制条件(一般是对元素或者位置作某些限制)解题时,首先要对这些有限对元素或者位置作某些限制)解题时,首先要对这些有限制条件的元素或位置作仔细分析,然后再考虑解法当直接制条件的
19、元素或位置作仔细分析,然后再考虑解法当直接计算比较复杂时,可从反面考虑先求出不符合条件的所有排计算比较复杂时,可从反面考虑先求出不符合条件的所有排列的种数,从而间接求出符合条件的排列的种数无论是从列的种数,从而间接求出符合条件的排列的种数无论是从“元素元素”考虑还是从考虑还是从“位置位置”分析,采用直接计算法还是间分析,采用直接计算法还是间接计算法,要防止重复或遗漏接计算法,要防止重复或遗漏解排列应用题的基本思路解排列应用题的基本思路基本思路:基本思路:直接法:即从条件出发,直接考虑符合条件的排列数;直接法:即从条件出发,直接考虑符合条件的排列数;间接法:即先不考虑限制条件,求出所有排列数,然后再间接法:即先不考虑限制条件,求出所有排列数,然后再从中减去不符合条件的排列数。从中减去不符合条件的排列数。常用方法:常用方法:特殊元素、特殊位置分析法,排除法(也称特殊元素、特殊位置分析法,排除法(也称去杂法),对称分析法,捆绑法,插空挡法,构造法等。去杂法),对称分析法,捆绑法,插空挡法,构造法等。