1.2全排列和对换

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

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

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

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

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

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

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

8、mlcbcbabaa111当当 时，时，ba 现来对换现来对换 与与a.b次相邻对换次相邻对换mnmlccbbabaa111次相邻对换次相邻对换1 mnmlccabbbaa111,111nmlcbcbabaa次相邻对换次相邻对换12 m,111nmlcacbbbaa所以一个排列中的任意两个元素对换，排列改变所以一个排列中的任意两个元素对换，排列改变奇偶性奇偶性.abnmlccbbbaaa111abab推论推论奇排列调成标准排列的对换次数为奇数，奇排列调成标准排列的对换次数为奇数，偶排列调成标准排列的对换次数为偶数偶排列调成标准排列的对换次数为偶数. .证明证明 由定理由定理1知对换的次数就是排

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