最后更新: 2024-12-31 15:13 查看: 1057 次反馈同步训练

排列及其逆序数

## 1. 排列及其逆序数
为了解决$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的逆序数 0 （因为3的前面比他大的数为零个）
4的逆序数 0 （因为4的前面比他大的数为零个）
2的逆序数 2  （因为2的前面比他大的数为4和2共两个）
1 的逆序数 3 （因为1的前面比他大的数为2，4和3共三个）
所以，总的逆序数为：$0+0+2+3=5$

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

`例` 求$\tau (42153)$
解：如下图
![图片](/uploads/2023-01/image_202301027b0d7d7.png)

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

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

#### 奇排列与偶排列
**定义3** 逆序数为偶数的排列，称为偶排列；逆序数为奇数的排列，称为奇排列.
例如， $\tau(213)=1$ ，所以 213 是一个奇排列；而 $\tau(312)=2$ ，所以 312 是一个偶排列。
**定义4** 只交换排列中某两个数的位置，其它的数保持不动而得到一个新排列的变换，称为一个对换. 若交换的是相邻位

免费注册看余下 50%

非VIP会员每天15篇文章，开通VIP 无限制查看

上一篇：四阶行列式的计算

下一篇： n 阶行列式

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