定义
由自然数 $1,2,3,\dots,n$ 按一定次序排成的数组 $p_{1}p_{2}\dots p_{n}$ ，简称为排列，$p_{i}$ 表示排列中的第 i 个元素。
所有 n 元排列共 $n!$ 个
自然排列
在所有 n 元排列中 $123\dots n$ 这样按标准次序（即从小到大）排成的排列称为自然排列
逆序数
定义
在一个长度为 $n$ 的排列 $p_{1}p_{2}\dots p_{n}$ 中,如果存在一对 $p_{i} < p_{j}(i< j)$ ,则数对 $p_{i},p_{j}$ 构成该排列的一个顺序;如果存在一对 $p_{i} > p_{j}$ $(i< j)$ ,则数对 $p_{i},p_{j}$ 构成该排列的一个逆序.
所有逆序的 总数 就称为该排列的 逆序数（Inversion Number），记为 $\boldsymbol{\tau (p_{1}p_{2}\dots p_{n})}$.
eg:
$32514 \Rightarrow 3>2,3>1,2>1,5>1,5>4$
$\boldsymbol{\tau} (32514)=5$
计算方法
分别计算出排列中每一个元素右边比它小的数码个数，即算出排列中每个元素的逆序数，这每个元素的逆序数之和即为所求排列的逆序数
eg:
$$\begin{aligned} &32514 \Rightarrow \begin{cases} 3 &\rightarrow 3>2,3>1 \rightarrow 2 \\ 2 &\rightarrow 2>1 \rightarrow 1 \\ 5 &\rightarrow 5>1,5>4 \rightarrow 2 \\ 1 &\rightarrow 0 \\ 4 &\rightarrow 0 \end{cases}\Rightarrow 2+1+2+0+0 \Rightarrow 5 \\ &\Rightarrow \tau(32514)=5 \end{aligned} $$
奇排列和偶排列
-
逆序数为奇数为奇排列
eg:
$\because\tau(32514)=5$
32514 为奇排列 -
逆序数为偶数为偶排列
eg:
$\because\tau(16352487)=8$
$\therefore$ 16352487 为偶排列
对换
定义
在一个 n 元排列 $p_{1}\dots p_{s}\dots p_{t}\dots p_{n}$ 中,对调 $p_{s}$ 和 $p_{t}$ 的位置，其他元素不动，得到一个新的排列 $p_{1}\dots p_{t}\dots p_{s}\dots p_{n}$ ,这种变换称为一次对换。
对换排列中两个相邻元素，称为相邻对换
性质
定理一 ：排列经过一次对换后改变其奇偶性
$$ \begin{aligned} \\ &32514 \xrightarrow{交换（2，3）} 23514 \\ \tau &(32514)=5 \quad \tau (23514)=4 \end{aligned} $$
推论一 ：奇排列变成自然排列的对换次数为奇数；偶排列变成自然排列的对换次数为偶数
eg:
奇排列：$32514 \xrightarrow{(5,4)} 32415 \xrightarrow{(4,1)}32145 \xrightarrow{(3,1)}12345\;共三次对换$
偶排列：$23514 \xrightarrow{(5,4)} 23415 \xrightarrow{(4,1)}23145 \xrightarrow{(3,1)}21345\xrightarrow{(1,2)}12345\;共四次对换$