排列与逆序

123这三个数有几种排法？123,132,213,231,312,321
由1,2，3, …，n组成的一个有序数组，叫作一个n级排列.
n级排列共有n!个种排列方式。
1,2,3,4…n 称为标准排列（自然排列）

---

在一个n级排列$i_1{i}_2....i_n$中，如果较大的数$i_s$排在较小的数$i_t$的前面，则称$i_s$与$i_t$构成一个逆序。
排列$i_1{i}_2....i_n$中逆序的个数称为它的逆序数，记作$N(i_1{i}_2....i_n)$

$$N(54123)=4+3+0=7$$

求7级排列6471325的逆序数$N(6471325)$
$N(6471325)=5+3+4+1+0=13$
求下列n级排列的逆序数
123…(n-1)n

$$N(\mathrm{123....}(n-1)n)=0$$

n(n-1)…321

$$N(n(n-1)...321)=n-1+n-2+3+2+1=\frac{(1+n-1)(n-1)}{2}=\frac{n(n-1)}{2}$$

奇排列 偶排列

逆序数为奇数的排列称为奇排列；
逆序数为偶数的排列称为偶排列。

n级标准排列是偶排列。$N(\mathrm{123....}(n-1)n)=0$