1.1.2　排列与逆序

作为定义n阶行列式的准备,先给出一些有关排列的基本概念.

由n个不同数码1,2,…,n组成的一个有序数组i1i2…in,称为一个n级排列.如由1,2,3组成的三级排列有且仅有3!=6个,即

123,132,213,231,312,321

同理,n级排列一共有n!个.

定义1　在一个n级排列i1i2…in中,任意找出两个数,若较大的数it排在较小的数is之前(is<it),则称it与is构成一个逆序.一个n级排列的逆序总数,称为这个排列的逆序数,记为τ(i1i2…in).

例如,在排列231中,2与1构成一个逆序,3与1构成一个逆序,共有2个逆序,这个排列的逆序数为2,记为τ(231)=2.

例4　计算排列的逆序数.

①2431　②n(n-1)(n-2)…321

解　分别计算逆序的个数,得到

①2431的逆序有21、43、41、31,故τ(2431)=4.

②n(n-1)(n-2)…321的逆序有

[n(n-1)、n(n-2)、…、n1],[(n-1)(n-2)、…、(n-1)1],…,[32、31],21

故得到

定义2　将逆序数τ(i1i2…in)是偶数或0的排列称为偶排列,逆序数τ(i1i2…in)为奇数的排列称为奇排列.

如:由于τ(2431)=4,排列2431是偶排列.τ(45321)=9,排列45321是奇排列.

把一个排列中某两个数的位置互换,而其余的数不动,就得到另一个排列,这样的一个变换称为一个对换.例如,排列2134施以对换(1,4)后得到排列2431.

定理1　对换改变排列的奇偶性.

也就是说,任意一个排列经过一次对换,奇排列变成偶排列,偶排列变成奇排列.

证明　先看一个特殊的情形,即对换的两个数在排列中是相邻的情形.设排列为

…jk…

经过(j,k)对换变成新排列

…kj…

这里,“…”表示那些不动的数,显然新排列仅比原排列增加或减少了一个逆序,显然与原排列的奇偶性相反.

再看一般的情形,设排列为

…ji1i2…isk…

经过(j,k)对换变成

…ki1i2…isj…

可以视为原排列将数码j依次与i1,i2,…,is,k作s+1次相邻对换,变为

…i1i2…iskj…

再将k依次与is,i2,…,i1作s次相邻对换得到新排列.即,新排列可以由原排列经过2s+1次相邻对换得到.2s+1是奇数,显然,奇数次这样的对换的最终结果还是改变奇偶性.

定理2　n个数码(n>1)共有n!个n级排列,其中奇偶排列各占一半.

证明　n级排列的总数n!为偶数个(n>1).若奇偶排列个数不等,则不妨设奇排列个数少于偶排列个数.若将所有的排列都施以相同对换,例如都对换(1,2),则n级排列的全体在施以相同对换后还是相同的n级排列全体.但由定理1,对换后的偶排列个数少于奇排列个数,因而矛盾.所以,奇偶排列数的个数相等,各占一半.