n元排列

定义

由自然数 $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\;共四次对换$