【定义】排列及其逆序数

定义1（全排列）　把 $n$ 个不同的元素排成一列，叫做这 $n$ 个元素的 全排列（也简称排列）。

$n$ 个不同元素的所有排列的种数，通常用 $A_n$ 表示（也可以用 $P_n$ 表示），有：
$$A_n=n!\text{\hspace{1em}(1)}$$
定义2（排序的逆序数）　对于 $n$ 个不同的元素，先规定各元素之间有一个标准次序（例如 $n$ 个不同的自然数，可规定由小到大为标准次序），于是在这 $n$ 个元素的任一排列中，当某一对元素的先后次序与标准次序不同时，就说它构成 1 个 逆序。一个排列中所有逆序的总数叫做这个 排列的逆序数。

逆序数为奇数的排列叫做 奇排列，逆序数为偶数的排列叫做 偶排列。