第二节全排列及其逆序数

1、第二节 全排列及其逆序数 从上节的例子我们知道，对角线法则只适用于二阶与三阶行列式，对四阶和四阶以上的行列式就不适用了. 怎样计算四阶和四阶以上的行列式呢?我们先从二阶与三阶行列式的计算中找一找规律先看二阶行列式 二阶行列式一共有两项，每一项均由不同行不同列的元素组成。其组成的规律是 如果行标都取自然数1，2；列标只能取1，2或2，1。所以二阶行列式中有两项 ， 。再看三阶行列式 三阶行列式一共有6项，每一项均由不同行不同列的元素组成。其组成的规律是 如果行标都取自然数1，2，3；列标只能取1，2，3；2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。所以三阶行列式中有6项 通过上述

2、分析，我们知道了二阶行列式和三阶行列式项的组成方法。既和排列有关。一、全排列 二阶行列式和三阶行列式项的组成方法 1）行标取自然排列时，列标分别取全排列. 2）项的个数就是全排列的个数。 另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取“+”，一些项的前面取“-”。怎样确定那些项的前面取“+”， 那些项的前面取“-”呢？我们发现和排列的顺序有关。定义3把n个不同的自然数按一定次序排成一列,称为一个n元排列.记为p1,pn。例如1，2，3是一个三元排列，2，3，1也是一个三元排列。排列1，2，,n称为n元自然排列 n个不同的自然数的所有排列，称为n元全排列, n元全排列的个数通常

3、用Pn表示. 二阶行列式和三阶行列式项的组成方法1）行标取自然排列时，列标分别取全排列 2）项的个数就是全排列的个数。 另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取“+”，一些项的前面取“-”。怎样确定那些项的前面取“+”， 那些项的前面取“-”呢？我们发现和排列的顺序有关排列的逆序数 我们规定各元素之间有一个标准次序, n 个不同的自然数，规定由小到大为标准次序.定义4 在一个n元排列中，若一个大的数排在一个小的数的前面，则称这个排列有一个逆序。定义 5 一个n元排列p1,pn中所有逆序的总数称为此排列的逆序数，记为计算排列逆序数的方法分别计算出排列中每个元素前面比它大的

4、数码个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆序数.例4 求排列3,2,5,1,4的逆序数解在排列3,2,5,1,4中排在首位,逆序数为0;2的前面比2大的数只有一个3,故逆序数为1;5的前面没有比5大的数,其逆序数为0;1的前面比1大的数有3个,故逆序数为3;4的前面比4大的数有1个,故逆序数为1; 3 2 5 1 4于是排列的逆序数为例5 计算下列排列的逆序数，并讨论它们的奇偶性.解逆序数的性质排列的奇偶性逆序数为奇数的排列称为奇排列逆序数为偶数的排列称为偶排列定义5 将一个排列中的某两个数的位置互换而其余的数不动,这样得到一个新的排列.这种变换称为对

5、排列作一次对换,将相邻的两个数对换称为相邻对换.定理1 对排列进行一次对换将改变其奇偶性.证：首先证明对排列进行一次相邻的对换将改变其奇偶性设原排列为a1,an,a,b,b1,bm将a,b对换后所得新排列为a1,an,b,a,b1,bm由于在新排列中a1,an,b1,bm的位置没有改变，所以它们的逆序数没有改变。只有a,b的位置改变了。因此对排列进行一次相邻的对换将改变其奇偶性。再证一般情况 由定理1可得下列推论推论1 将奇排列变成自然排列所需的对换次数为奇数, 将偶排列变成自然排列所需的对换次数为偶数. 证：因为自然排列的逆序数为零，所以是偶排列。如果原排列是奇排列，变成偶排列需要的对换次数

6、为奇数，所以奇排列变成自然排列所需的对换次数为奇数。同理可证偶排列的情况。证毕推论2 在全体n元排列(n1)中,奇排列和偶排列各占一半.证：设在全体n元排列(n1)中,奇排列一共有s个，偶排列一共有t个.将每个奇排列的前面两个数字对换，可得到s个偶排列，所以st。将每个偶排列的前面两个数字对换，可得到t个偶排列，所以ts。因此s=t,奇排列和偶排列各占一半.证毕 我们有了逆序数的概念后，再来讨论行列式的项前面的符号就很方便了。先看二阶行列式如果行标都取自然数1，2；列标的排列为1，2或2，1其中1，2是偶排列， 前面的符号为“+”；2，1是奇排列， 前面的符号为“-”；再看三阶行列式 如果行标都取自然数1，2，3；列标排列为1，2，3；2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。其中，1，2，3；2，3，1；3，1，2是偶排列，相应的项前面的符号为“+”；3，2，1；2，1，3；1，3，2是奇排列，相应的项前面的符号为“-”