1.2　排列

1.2.1　排列的概念

定义1　由1，2，…，n这n个不同的数码组成的一个有序组称为一个n级排列.

显然，1，2，…，n也是一个n级排列，这个排列具有自然顺序，即按递增的顺序排列，其他的排列或多或少地破坏自然顺序.

例如，12345，14532，13452都是由1，2，3，4，5组成的一个5级排列.

定义2　在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么就称它们构成一个逆序（反序），一个排列中逆序的总数就称为这个排列的逆序数.

排列j1j2…jn的逆序数记为

τ（j1j2…jn）.

例如上面的第一个排列的逆序数τ（12345）=0，因为不存在较大的数字排在较小的数字前面，都是按自然顺序排列的，所以没有逆序，逆序数为0.

一般地，将1，2，…，n这种按照从小到大的自然顺序排成的排列称为标准排列.

例　计算排列14532的逆序数.

解　第一个位置是1，1小于后面的所有数字，所以这里有0个逆序；

第二个位置是4，后面比4小的数有3，2，所以这里有2个逆序；

第三个位置是5，后面比5小的数有3，2，所以这里有2个逆序；

第四个位置是3，后面比3小的数有2，所以这里有1个逆序；

第五个位置是2，2后面没有数字，所以这里有0个逆序；得，这个排列的逆序数τ（14532）=0+2+2+1+0=5.

定义3　逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列.

第一个排列12345是偶排列，第二个排列14532是奇排列.

应该指出，同样可以考虑由任意n个不同的自然数所组成的排列，一般也称为n级排列，对这样一般的n级排列，同样可以类似地定义上面这些概念.