一、全排列及其逆序数

从n个不同的元素中取出n个排成一列 , 叫做这n个元素的全排列

n个不同元素的所有排列的种数 , 通常用P_n表示 , 可计算如下

从n个元素中任取一个放在第一个位置上 , 有n种取法

从剩下的n-1个元素中任取一个放在第二个位置上 , 有n-1种取法

这样继续下去 , 直到最后只剩下一个元素放在第n个位置上，只有1种取法

于是P_n=n·(n-1)⋯3·2·1=n!

例如用1 , 2 , 3三个数字作排列 , 排列总数P_n=3·2·1=6

它们是123 , 231 , 312 , 132 , 213 , 321

对于n个不同的元素 , 先约定各元素之间有一个标准次序

(例如n个不同的自然数 , 可约定由小到大为标准次序)

于是在这n个元素的任一排列中

当某一对元素的先后次序与标准次序不同时 , 就说这对元素构成1个逆序

一个排列中所有逆序的总数叫做这个排列的逆序数

逆序数为奇数的排列叫做奇排列 , 逆序数为偶数的排列叫做偶排列

下面来讨论计算排列的逆序数的方法

为简化起见 , 设n个元素为1至n这n个自然数 , 并约定由小到大为标准次序，

设p₁p₂⋯p_n为这n个自然数的一个排列 , 对于元素p_i(i=1 , 2 , ⋯ , n)

如果比p_i小的且排在p_i后面的元素有t_i个 , 就说p_i这个元素的逆序数是t_i

$$全体元素的逆序数之总和t = t_{i} + t_{2} + \cdots + t_{n} = \sum_{i = 1}^{n}t_{i}$$

即是这个排列的逆序数

例4求排列32514的逆序数

解: 在排列32514中

比3小，且排在3后面的数有2个(2,1) , 逆序数t₁=2

比2小，且排在2后面的数有1个(1) , 逆序数t₂=1

比5小，且排在5后面的数有2个(1,4) , 逆序数t₃=2

比1小，且排在1后面的数有0个 , 逆序数t₄=0

比4小，且排在4后面的数有0个 , 逆序数t₅=0

$$t = \sum_{i = 1}^{5}t_{i} = 2 + 1 + 2 + 0 + 0 = 5$$

是奇排列

二、对换

在排列中

将任意两个元素对调 , 其余的元素不动 , 这种作出新排列的操作叫做对换

将相邻两个元素对换 , 叫做相邻对换。

定理1：一个排列中的任意两个元素对换 , 排列改变奇偶性

证明：

1.相邻对换改变奇偶性

设排列中有两个相邻元素$p,q$，交换它们的位置。

若$p < q$，则原顺序对$(p,q)$在对换后变为逆序对$(q,p)$，逆序数增加$1$。

若$p > q$，则原逆序对$(p,q)$在对换后变为顺序对$(q,p)$，逆序数减少$1$。

其他元素对的顺序关系不变。

因此，相邻对换总使逆序数改变一个奇数（±1），排列的奇偶性改变。

2.任意对换可表示为奇数次相邻对换

设对换的两个元素在排列中的位置分别为$i$和$j$（$i < j$）。

先将位于$i$的元素逐步与右侧相邻元素交换，经过$j - i$次相邻对换到达位置$j$。

此时原位于$j$的元素被挤到位置$j - 1$，再将其逐步与左侧相邻元素交换，

经过$j - i - 1$次相邻对换到达位置$i$。

总相邻对换次数为：$(j - i) + (j - i - 1) = 2(j - i) - 1$

这是一个奇数。

3.结论，每次相邻对换改变排列的奇偶性，

奇数次相邻对换的复合效果仍是改变奇偶性。

因此，任意对换改变排列的奇偶性。

举例说明

例1：初始排列：$(1,2,3,4)$，逆序数$0$（偶排列）。

对换$2$与$4$，得排列$(1,4,3,2)$。逆序数$3$（奇排列）

故奇偶性改变。

推论 奇排列对换成标准排列的对换次数为奇数

偶排列对换成标准排列的对换次数为偶数

例1：$n = 4$

取奇排列$\sigma = (2,3,4,1)$，

对换分解：

一、$(1\ 4)$：$(2,3,4,1) \rightarrow (2,3,1,4)$；

二、$(1\ 3)$：$(2,3,1,4) \rightarrow (2,1,3,4)$；

三、$(1\ 2)$：$(2,1,3,4) \rightarrow (1,2,3,4)$；

对换次数$k =$3（奇数）。

例2：$n = 4$

取偶排列$\sigma = (2,1,4,3)$。

对换分解：

一、$(1\ 2)$：$(2,1,4,3) \rightarrow (1,2,4,3)$；

二、$(3\ 4)$：$(1,2,4,3) \rightarrow (1,2,3,4)$。

对换次数$k = 2$（偶数）。