排列4ppt课件.ppt

排列4ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 一般地说，从 n 个不同元素中，任取 m(mn)个元素（本章只研究被取出的元素各不相同的情况），按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列排列。定义定义2.排列数公式排列数公式 从 n 个不同元素中取出 m(mn)个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 表示。排列数公式排列数公式选排列数选排列数 3 2 1全排列数全排列数简写为简写为选排列数选排列数一般地对于有限制条件的排列应用题，可以有两种不同的计算方法：（l）直接计算法）直接计算法 排列问题的限制条件一般表现为：某些元素不能在排列问题的限制条件一般表现为：某些元素不能在某个（或某些）位置、某个（或某些）位置只能放某些某个（或某些）位置、某个（或某些）位置只能放某些元素，因此进行算法设计时，常优先处理这些特殊要求元素，因此进行算法设计时，常优先处理这些特殊要求便有了：先处理特殊元素或先处理特殊位置的方法便有了：先处理特殊元素或先处理特殊位置的方法这些统称为这些统称为“特殊元素（位置）优先考虑法特殊元素（位置）优先考虑法”（2）间接计算法）间接计算法 先不考虑限制条件，把所有的排列种数算出，再从先不考虑限制条件，把所有的排列种数算出，再从中减去全部不符合条件的排列数，间接得出符合条件中减去全部不符合条件的排列数，间接得出符合条件的排列种数这种方法也称为的排列种数这种方法也称为“去杂法去杂法”在去杂时，在去杂时，特别注意特别注意要不重复，不遗漏（去尽）要不重复，不遗漏（去尽）6个队员排成一列进行操练，其中新队员个队员排成一列进行操练，其中新队员甲不能站排头，也不能站排尾，问有多少甲不能站排头，也不能站排尾，问有多少种不同的站法？种不同的站法？根据分步计数原理，共有站法根据分步计数原理，共有站法 对对于中于中间间的四个位置，的四个位置，4个人有个人有 种站法。种站法。分析分析1（特殊位置）：（特殊位置）：由于甲不站排由于甲不站排头头和排尾，和排尾，这这两个位置只能在其余两个位置只能在其余5个人中个人中选选2个人站，有个人站，有 种站法；种站法；6个队员排成一列进行操练，其中新队员个队员排成一列进行操练，其中新队员甲不能站排头，也不能站排尾，问有多少甲不能站排头，也不能站排尾，问有多少种不同的站法？种不同的站法？根据分步计数原理，共有站法根据分步计数原理，共有站法 然后对其余然后对其余5人在另外人在另外5个位置上作全排列有个位置上作全排列有 种站法。种站法。分析分析2（特殊元素）：（特殊元素）：要使甲不在排头和排尾，要使甲不在排头和排尾，可先让甲在中间可先让甲在中间4个位置中任选个位置中任选1个位置，有个位置，有 种站法；种站法；6个队员排成一列进行操练，其中新队员甲不能站排个队员排成一列进行操练，其中新队员甲不能站排头，也不能站排尾，问有多少种不同的站法？头，也不能站排尾，问有多少种不同的站法？分析分析3（间间接法）：若接法）：若对对甲没有限制条件，甲没有限制条件，共有共有 种站法，这里面包含下面三种情种站法，这里面包含下面三种情况况（1）甲在排头；（）甲在排头；（2）甲在排尾；）甲在排尾；（3）甲不在排头，也不在排尾）甲不在排头，也不在排尾 这都不符合题设条件，从总数中减去这两种情这都不符合题设条件，从总数中减去这两种情况的排列数即得所求的站法数，共有况的排列数即得所求的站法数，共有 甲在排尾有甲在排尾有 种站法种站法，甲在排甲在排头头有有 种站法种站法；有名同学，按如下要求站成一排，问：（）共有多少种排法（）甲必须站中间，有多少种排法（）甲站中间，乙站甲的旁边，有多少种排法（）甲，乙两人不能站在排头和排尾，有多少种排法（）甲不站排头，乙不站排尾，有多少种排法（）甲乙两人必须相邻，有多少种排法（）甲乙两人不能相邻，有多少种不同排法小结：某些元素必须排在某些具体位置先排好这些元素，再排其它元素某些元素不能排在某些具体位置转化为（）种类型或采用间接法.某些元素要排在一起采用“捆绑法”首先将要排在一起的元素通过“捆绑”后视为一个元素与其它元素一起进行排列，然后再将“捆绑”的元素内部进行排列，最后按照分步记数原理求出总的排列数某些元素不能排在一起采用“插空法”将其他元素排好，再插入这些不能排在一起的元素练习：某班级上午要上语文，数学，体育，英语四节课，体育课不能排在第一节，数学课不能排在第四节，则不同的排法有种由数字，可以组成没有重复的数字且比大的自然数的个数是个人站成一排，其中不排在左端，也不同相邻的不同排法种数是