线性代数2.2-排列

1、1/162/16一、排列一、排列定义定义称为一个称为一个 级级排列排列n由由1，2，n 组成的一个有序数组组成的一个有序数组, ,123，132，213，231，312，321如如: 所有的所有的3级排列是级排列是 共共6=3！个个.n!1 2(1)nnnnP ( (阶乘阶乘)注：注：所有不同级排列的总数是所有不同级排列的总数是n3/16二、逆序逆序数二、逆序逆序数 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序, , n 个个不同的自然数，规定由小到大为不同的自然数，规定由小到大为标准次序标准次序. .定义定义一个排列中逆序的一个排列中逆序的总数称为这个排列的总数称为这个排

2、列的逆序数逆序数在一个排列中，如果一对数的前后位置在一个排列中，如果一对数的前后位置与标准次序相反，即前面的数大于后面的数，与标准次序相反，即前面的数大于后面的数，则称这对数为一个则称这对数为一个逆序逆序；4/16 排列排列 123 称为称为标准排列标准排列，其逆序数为其逆序数为n注：注： 排列排列 的逆序数常记为的逆序数常记为1 2().nj jj 1 2nj jj例例1排列排列 31542 中，逆序有中，逆序有(31542)5 31， 32， 54， 52， 425/16求逆序数的方法求逆序数的方法 后面比后面比 小的数的个数小的数的个数1 21()nj jjj 1j1nj 后面比后面比

3、小的数的个数小的数的个数.1nj 2j 后面比后面比 小的数的个数小的数的个数2j或或前面比前面比 大的数的个数大的数的个数1 22()nj jjj 2j3j 前面比前面比 大的数的个数大的数的个数3j nj 前面比前面比 大的数的个数大的数的个数nj方法一方法一方法二方法二6/16的逆序数的逆序数. . 例例2求求 级排列级排列2n135(21)(2 )(22)42nnn解：解：135(21)(2 )(22)42nnn121n 1n 方法一方法一12(1)(1)21(1)nnn n 17/16逆序数为奇数的排列称为逆序数为奇数的排列称为奇排列奇排列；逆序数为偶数的排列称为逆序数为偶数的排列称

4、为偶排列偶排列三三 、奇排列、偶排列、奇排列、偶排列定义定义标准排列标准排列 123 为偶排列为偶排列n注：注：练习练习：求下列排列的逆序数并讨论其奇偶性：求下列排列的逆序数并讨论其奇偶性(1)321n n （1）(2 )1(21)2(22)3(1)nnnnn（2）8/16答案答案:2(1)(1)22n nn nn12(1)(2)21nnn （2）当当 时为偶排列；时为偶排列；4 , 41nkk当当 时为奇排列时为奇排列.42, 43nkk当当 为偶数时为偶排列，为偶数时为偶排列，k当当 为奇数时为奇排列为奇数时为奇排列.k方法一方法一方法二方法二(1)(1)(1)(2)212n nnn 9/

5、16四四 、对换、对换定义定义把一个排列中某两个数的位置互换，而把一个排列中某两个数的位置互换，而其余的数不动，得到另一个排列，这一变换其余的数不动，得到另一个排列，这一变换称为一个称为一个对换对换将相邻两个元素对调，叫做将相邻两个元素对调，叫做相邻对换相邻对换10/16证明证明1) 特殊情形：作相邻对换特殊情形：作相邻对换mlbbabaa11对换对换 与与abmlbbbaaa11除除 外，其它元素所成逆序不改变外，其它元素所成逆序不改变.b,aab对换改变排列的奇偶性即经过一次对换，对换改变排列的奇偶性即经过一次对换，奇排列变成偶排列，偶排列变成奇排列奇排列变成偶排列，偶排列变成奇排列定理定

6、理1设排列为设排列为11/16当当 时，时，ba ab所成逆序不变所成逆序不变;经对换后经对换后 的逆序增加的逆序增加1个个 ,经对换后经对换后 所成逆序不变所成逆序不变 ， 的逆序减少的逆序减少1个个.ab因此对换相邻两个元素，排列改变奇偶性因此对换相邻两个元素，排列改变奇偶性.设排列为设排列为nmlcbcbabaa111当当 时，时，ba 现来对换现来对换 与与a.b2)一般情形一般情形12/16次相邻对换次相邻对换mnmlccbbabaa111次相邻对换次相邻对换1 mnmlccabbbaa111,111nmlcbcbabaa次相邻对换次相邻对换12 m,111nmlcacbbbaa所以

7、一个排列中的任意两个元素对换，排列改变所以一个排列中的任意两个元素对换，排列改变奇偶性奇偶性.abnmlccbbbaaa111abab13/16所有所有 级排列中，奇、偶排列各半，级排列中，奇、偶排列各半，n!2n均为均为 个个. 设在全部设在全部 阶排列中，有阶排列中，有 个奇排列，个奇排列， 个个偶排列，下证偶排列，下证 nstts 将将 个奇排列的前两个数对换，则这个奇排列的前两个数对换，则这 个奇排列个奇排列全变成偶排列，并且它们彼此不同，全变成偶排列，并且它们彼此不同，ss 同理，将同理，将 个偶排列的前两个数对换，则这个偶排列的前两个数对换，则这 个个偶排列全变成奇排列，并且它们彼此不同，偶排列全变成奇排列，并且它们彼此不同，tt推论推论证明证明.st.ts故故!.2nst14/16一系列对换互换，并且所作对换的次数与这个一系列对换互换，并且所作对换的次数与这个任意一个排列与标准排列任意一个排列与标准排列 都可经过都可经过123n排列的奇偶性相同排