1.2全排列和对换ppt课件

1、;.1第二节第二节 全排列及其逆序数全排列及其逆序数;.2一、概念的引入引例引例用用1、2、3三个数字，可以组成多少个没有重复数字的三位数？三个数字，可以组成多少个没有重复数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位1232种放法种放法1种放法种放法种放法种放法.共有共有6123 ;.3同同的的排排法法？，共共有有几几种种不不个个不不同同的的元元素素排排成成一一列列把把 n问题问题定义定义1由由1，2，,n组成的一个有序数组称为一个组成的一个有序数组称为一个n 级全排列（简称排级全排列（简称排列）。列）。 个不同的元素的所有排列的种数，通常用个不同的元素的所

2、有排列的种数，通常用 表示表示.nnP由引例由引例1233 P. 6 nPn )1( n)2( n123 !.n 同理同理二、全排列及其逆序数;.4例如例如 排列排列32514 中，中， 定义2 在一个排列中，如果两个数（称为数对）的前后位置与大小顺序相反，即前面的数大于后面的数，那么称它们构成一个逆序（反序）。排列的逆序数排列的逆序数3 2 5 1 4逆序逆序逆序逆序逆序逆序;.5 定义定义 一个排列中所有逆序的总数称为此排列的一个排列中所有逆序的总数称为此排列的逆序数逆序数.一个排列一个排列j1, j2,jn的逆序数，一般记为的逆序数，一般记为 (j1, j2,jn) 例如例如 排列排列3

3、2514 中，中， 3 2 5 1 4逆序数为逆序数为31010故此排列的逆序数为故此排列的逆序数为3+1+0+1+0=5.即即（32514）=5;.6计算排列逆序数的方法计算排列逆序数的方法方法方法1 1分别计算出排在分别计算出排在 前面比它大的数前面比它大的数码之和即分别算出码之和即分别算出 这这 个元素个元素的逆序数，这个元素的逆序数的总和即为所求的逆序数，这个元素的逆序数的总和即为所求排列的逆序数排列的逆序数.n,n,121 n,n,121 n逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列; ;逆序数为偶数的排列称为偶排列逆序数为偶数的排列称为偶排列. .排列的奇偶性排列的奇

4、偶性;.7 分别计算出排列中每个元素前面比它大的分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数码个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列数，这每个元素的逆序数之总和即为所求排列的逆序数的逆序数.方法方法2 2例例1 1 求排列求排列32514的逆序数的逆序数.解解在排列在排列32514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;.83 2 5 1 40 1 0 3 1于是排列于是排列32514的逆序数为的逆序数为13010 t. 5 5的前面没有比的

5、前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;.9例例2 2 计算下列排列的逆序数，并讨论它们的奇偶性计算下列排列的逆序数，并讨论它们的奇偶性. 2179863541解解453689712544310010 t18 此排列为偶排列此排列为偶排列.54 0100134 ;.10 321212 nnn解解12 ,21 nn当当 时为偶排列；时为偶排列；14 ,4 kkn当当 时为奇排列时为奇排列.34 , 24 kkn 1 nt 2 n 32121 nnn1

6、n 2 n;.11 kkkkkk132322212123 解解0 t kkk 21112,2k 当当 为偶数时，排列为偶排列，为偶数时，排列为偶排列，k当当 为奇数时，排列为奇排列为奇数时，排列为奇排列.k1 1 2 kkk 112 kkkkk0 1 1 2 2 k;.12定义定义在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手续叫做对换续叫做对换将相邻两个元素对调，叫做相邻对换将相邻两个元素对调，叫做相邻对换mlbbbaaa11例如例如bamlbbabaa11abnmlccbbbaaa111

7、nmlccabbbaa111baab三、对换;.13;.14定理一个排列中的任意两个元素对换，排列改变奇偶性定理一个排列中的任意两个元素对换，排列改变奇偶性证明证明设排列为设排列为mlbbabaa11对换对换 与与abmlbbbaaa11除除 外，其它元素的逆序数不改变外，其它元素的逆序数不改变.a b,NoImageba即经过一次对换，奇排列变成偶排列，即经过一次对换，奇排列变成偶排列， 偶排列变成奇排列。偶排列变成奇排列。;.15当当 时，时，ba ab的逆序数不变的逆序数不变;经对换后经对换后 的逆序数增加的逆序数增加1 ,经对换后经对换后 的逆序数不变的逆序数不变 ， 的逆序数减少的逆

8、序数减少1.ab因此对换相邻两个元素，排列改变奇偶性因此对换相邻两个元素，排列改变奇偶性.设排列为设排列为nmlcbcbabaa111当当 时，时，ba 现来对换现来对换 与与a.b;.16次相邻对换次相邻对换mnmlccbbabaa111次相邻对换次相邻对换1 mnmlccabbbaa111,111nmlcbcbabaa次相邻对换次相邻对换12 m,111nmlcacbbbaa所以一个排列中的任意两个元素对换，排列改变所以一个排列中的任意两个元素对换，排列改变奇偶性奇偶性.abnmlccbbbaaa111abab;.17推论推论奇排列调成标准排列的对换次数为奇数，奇排列调成标准排列的对换次数

9、为奇数，偶排列调成标准排列的对换次数为偶数偶排列调成标准排列的对换次数为偶数. .证明证明 由定理由定理1知对换的次数就是排列奇偶性的变化次数知对换的次数就是排列奇偶性的变化次数,而标准排列是偶而标准排列是偶排列排列(逆序数为逆序数为0),因此知推论成立因此知推论成立.;.182 排列具有奇偶性排列具有奇偶性.3 计算排列逆序数常用的方法有计算排列逆序数常用的方法有2 种种.1 个不同的元素的所有排列种数为个不同的元素的所有排列种数为n!.n 4 一个排列中的任意两个元素对换，排列一个排列中的任意两个元素对换，排列改变奇偶性改变奇偶性 小 结;.19分别用两种方法求排列的逆序数分别用两种方法求排列的逆序数.;.20思考题解答思考题解答解解用方法用方法1 11 6 3 5 2 4 8 7 用方法用方法2 201012130 t8 由前向后求每个数的逆序数由前向后求每个数的逆序数. 810231100 t;.21思考题思考题证明证明 在全部在全部 阶排列中阶排列中 , ,奇偶排列各占一半奇偶排列各占一半. . n 2 n;.22思考题解答思考题解答证证 设在全部设在全部 阶排列中有阶排列中有 个奇排列个奇排列, , 个偶排列个偶排列, ,现来证现来证 . . nstts 将将 个奇排列的前两个数对换个奇排列的前两个数对换, ,则这则这 个奇排列全变成