最后更新: 2026-01-10 20:14 查看: 56 次纠错评论(0) 课件开VIP

排列及其逆序数

##   排列及其逆序数
为了解决$n$阶行列式计算的问题，需要引入一个概念：逆序数。

什么叫做顺序？按照规则排列的数叫做顺序，
比如
$1,2,3,4,5$ 是从小到大排列的，他是顺序的(从小到大)， 
再比如
$5,4,3,2,1$ 是从大到小排列的，他也是顺序的(从大到小)，

但是
$1,2,3,5,4$ 则不是顺序的，因为 $1,2,3,5$是从小到大，而$5,4$由从大到小，此时就不是顺序了。

从概念上说，$1,2,3,4,5$和$5,4,3,2,1$都是顺序的，但是显然前者更符合我们常规的从小到大的认识，因此一般我们把从 $1,2, \cdots, n$ 称为一个顺序排列。

## 全排列

**定义1** 将 $1,2, \cdots, n$ 这 $n$ 个不同的数排成一列，称为 $n$ 阶全排列，也简称为全排列。 根据[高中排列组合知识](https://kb.kmath.cn/kbase/detail.aspx?id=200)，一个全排列共有$n!$的可能性。

比如$(1,2,3)$ 这三个数共有$3!=6 $ 种情况，即
$1,2,3$
$1,3,2$
$2,1,3$
$2,3,1$
$3,1,2$
$3,2,1$
共 $3* 2* 1=6$ 种。

**定义2** 在一个全排列中，如果一对数的排列顺序与自然顺序相反，即排在左边的数比排在它右边的数大，那么它们就称为一个**逆序**，一个排列中逆序的总数就称为这个排列的**逆序数**.

逆序数可以正排序，也可以逆排序效果是一样的。

`例` 求3421各排列的逆序数
解：
固定3的位置，3的逆序数 0 （因为3的前面比他大的数为零个）
固定4的位置，4的逆序数 0 （因为4的前面比他大的数为零个）
固定2的位置，2的逆序数 2 （因为2的前面比他大的数为4和3共两个）
固定1的位置，1的逆序数 3 （因为1的前面比他大的数为3,42共三个）
所以，总的逆序数为：$0+0+2+3=5$

排列 $i_1 i_2 \cdots i_n$ 的逆序数记为 $\tau\left(i_1 i_2 \cdots i_n\right)$.

`例` 求$\tau (42153)$

$$①\textcolor{red}{4} \quad 2\quad 1\quad 5\quad 3$$

固定4的位置，他的逆序数 0 （因为4的前面比他大的数为0个）

$$② 4 \quad \textcolor{red}{2}\quad 1\quad 5\quad 3$$

固定2的位置，他的逆序数 1 （因为2的前面比他大的数为1个）

$$③ 4 \quad 2 \quad \textcolor{red}{1} \quad 5\quad 3$$

固定1的位置，他的逆序数 2 （因为2的前面比他大的数为2个）

$$④ 4 \quad 2 \quad 1 \quad \textcolor{red}{5}\quad 3$$

固定5的位置，他的逆序数 0 （因为5的前面比他大的数为0个）

$$⑤ 4 \quad 2 \quad 1 \quad 5 \quad \textcolor{red}{3}$$

固定3的位置，他的逆序数 2 （因为3的前面比他大的数为2个）

如下图
 ![图片](/uploads/2026-01/df4d93.jpg)

所以，
$$
\tau(42153)=0+1+2+0+2=5 .
$$

从而 $42153$ 的逆序数为 $\tau(42153)=5$.

## 逆序数的性质

### 自然排列是偶排列

比如$1,2,3,4$ 前面比后面大的总是0，所以他的值总是正的。

#### 奇排列与偶排列
**定义3** 逆序数为偶数的排列，称为偶排列；逆序数为奇数的排列，称为奇排列.
例如， $\tau(213)=1$ ，所以 213 是一个奇排列；而 $\tau(312)=2$ ，所以 312 是一个偶排列。

## 对换
**定义4** 只交换排列中某两个数的位置，其它的数保持不动而得到一个新排列的变换，称为一个对换. 若交换的是相邻位置的两个元素，则称该对换为相邻对换.
例如，经过2、1对换，排列 42153就变成了排列 41253，这个对换是相邻对换；
经过 $2 、 5$ 对换，排列 42153 就变成了排列 45123 ，这个对换不是相邻对换.

> **定理1** 对换改变排列的奇偶性.

显然， $a, b$ 与其它数构成的逆序在排列(1-1)和排列(1-2)中是一样的，不同的只是 $a, b$ 的次序.
当 $a<b$ 时， $a b$ 原来是标准序，对换后 $b a$ 构成一个逆序，
于是排列(1-2)的逆序数是排列(1-1)的逆序数增加1；
当 $a>b$ 时， $a b$ 原来是逆序，对换后 $b a$ 是标准序，
于是排列(1-2)的逆序数是排列(1-1)的逆序数减少 1 .
所以无论增加还是减少1，相邻对换都改变了排列的奇偶性.
对于不相邻的对换，不妨假设原排列为 $\cdots a i_1 \cdots i_s b \cdots$ ， 经过 $a, b$ 对换后变为排列 $\cdots b i_1 \cdots i_s a \cdots$,
这个改变过程实际上就是通过先将 $a$ 依次与其后面相邻的元素作 $s+1$ 次相邻对换变为 $\cdots i_1 \cdots i_s b a \cdots$,
再通过将 $b$ 依次与前面相邻的元素作 $s$ 次相邻对换变而得到.
一共进行了 $2 s+1$ 次相邻对换，所以改变了排列的奇偶性.

**定理2** 在 $n$ 阶排列中，偶排列和奇排列各占一半，即各有 $\frac{n !}{2}$ 个.
证明 记 $P_n\left(S_n 、 T_n\right)$ 为所有 $n$ 阶 (奇、偶) 排列构成的集合，则 $P_n=S_n \cup T_n$ 并且 $S_n \cap T_n=\varnothing$ ，
于是有 $\left|S_n\right| \leq\left|T_n\right| 、\left|T_n\right| \leq\left|S_n\right|$ ， 所以 $\left|S_n\right|=\left|T_n\right|=\frac{1}{2}\left|P_n\right|=\frac{1}{2} n !$ 。

`例`设整数 $n \geqslant 2$，则 
$$
\begin{aligned}
& \tau(n(n-1) \cdots 21)=(n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2} \\
& \tau(135 \cdots(2 n-1) 246 \cdots(2 n))=0+1+2+\cdots+(n-1)=\frac{n(n-1)}{2}
\end{aligned}
$$

###  与行列式的关联
行列式的定义是基于排列和逆序数的，$n$ 阶行列式的展开式为：
$$|A|=\sum_{j_1j_2\cdots j_n}(-1)^{\tau(j_1j_2\cdots j_n)}a_{1j_1}a_{2j_2}\cdots a_{nj_n}$$
其中 $j_1j_2\cdots j_n$ 是 $n$ 级排列，$(-1)^{\tau}$ 决定了每一项的正负号。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：平行六面体的有向体积

下一篇： n阶方阵的行列式

本文对您是否有用？有用 (0) 无用 (0)