4. 逆序数与符号

本节是选学内容. 不学本节不影响理解任何必学内容 (也就是, 未被声明为选学内容的节).

我们知道, 排列是特别的文字列: 排列的每一个文字是互不相同的. 本节, 我想介绍一些跟排列有关的量.

在研究排列时, 我们通常选文字为整数. 熟知, 整数有大小关系. 设 $a_1$, $a_2$, $\dots$, $a_n$ 是互不相同的 $n$ 个整数. 我们从小到大地排 $a_1$, $a_2$, $\dots$, $a_n$ 为 $b_1$, $b_2$, $\dots$, $b_n$ ($b_1<b_2<\cdots <b_n$). 我们说, 这是整数 $a_1$, $a_2$, $\dots$, $a_n$ 的自然排列. $a_1$, $a_2$, $\dots$, $a_n$ 的自然排列有且只有一个.

设 $c_1$, $c_2$, $\dots$, $c_n$ 是 $a_1$, $a_2$, $\dots$, $a_n$ 的一个排列. 若存在整数 $i$, $j$, 使 $1⩽i<j⩽n$, 且 $c_i>c_j$, 我们说, 有序对 $(c_i,c_j)$ 为排列 $c_1$, $c_2$, $\dots$, $c_n$ 的一个逆序. 比如, 排列 $1$, $2$, $3$, $4$, $5$ 无逆序, 而 $3$, $2$, $5$, $1$, $4$ 有 $5$ 个逆序: $(3,2)$, $(3,1)$, $(2,1)$, $(5,1)$, $(5,4)$.

不难看出, 说 $(c_i,c_j)$ (其中 $i<j$) 是排列 $c_1$, $c_2$, $\dots$, $c_n$ 的一个逆序, 相当于说 $\rho (c_i,c_j)=1$. (注意, 因为 $c_1$, $c_2$, $\dots$, $c_n$ 是互不相同的整数, 故不可能出现 $i<j$, 但 $c_i=c_j$ 的情形.)

我们说, 一个排列的所有的逆序的数目为其逆序数. 比如, 排列 $1$, $2$, $3$, $4$, $5$ 的逆序数为 $0$, 而 $3$, $2$, $5$, $1$, $4$ 的逆序数为 $5$.

不难利用 $\rho$-记号写出排列 $c_1$, $c_2$, $\dots$, $c_n$ 的逆序数$$\begin{array}{rl}\tau (c_1,c_2,\dots ,c_n)=& \rho (c_1,c_2)\\ & +\rho (c_1,c_3)+\rho (c_2,c_3)\\ & +\rho (c_1,c_4)+\rho (c_2,c_4)+\rho (c_3,c_4)\\ & +\dots \\ & +\rho (c_1,c_n)+\rho (c_2,c_n)+\cdots +\rho (c_{n-1},c_n)\\ =& \sum _{j=2}^n\sum _{i=1}^{j-1}\rho (c_i,c_j)\\ =& \sum _{1⩽i<j⩽n}\rho (c_i,c_j).\end{array}$$比如, 当 $c_1$, $c_2$, $c_3$, $c_4$, $c_5$ 为 $1$, $2$, $3$, $4$, $5$ 时, 每一个 $\rho (c_i,c_j)$ ($1⩽i<j⩽5$) 都是 $0$, 故 $\tau (1,2,3,4,5)=0$; 当 $c_1$, $c_2$, $c_3$, $c_4$, $c_5$ 为 $3$, $2$, $5$, $1$, $4$ 时, $\rho (c_1,c_2)$, $\rho (c_1,c_4)$, $\rho (c_2,c_4)$, $\rho (c_3,c_4)$, $\rho (c_3,c_5)$ 都是 $1$, 而 $\rho (c_1,c_3)$, $\rho (c_1,c_5)$, $\rho (c_2,c_3)$, $\rho (c_2,c_5)$, $\rho (c_4,c_5)$ 都是 $0$, 故 $\tau (3,2,5,1,4)=5$.

有一件小事值得提. 若一个排列恰含一个文字, 我们说, 它没有逆序, 从而它的逆序数为 $0$. 这跟前面的公式是一样的: 既然没有整数对 $(i,j)$ 适合 $1⩽i<j⩽1$, 那这个和就是 $0$.

利用 $-1$ 的整数次方, 我们可再引入一些跟排列有关的量.

定义 4.1 (符号记号). 设 $x$ 为整数. 定义$$\begin{array}{r}\mathrm{sgn}(x)=\{\begin{array}{ll}1,& x>0;\\ 0,& x=0;\\ -1,& x<0.\end{array}\end{array}$$

$\mathrm{sgn}$ 来自英语 sign (或 signum).

不难看出, 若 $u$, $v$ 是不相等的整数, 则 $\mathrm{sgn}(v-u)=(-1{)}^{\rho (u,v)}$. 并且, 说 $(c_i,c_j)$ (其中 $i<j$) 是排列 $c_1$, $c_2$, $\dots$, $c_n$ 的一个逆序, 相当于说 $\mathrm{sgn}(c_j-c_i)=-1$.

定义 4.2 (整数文字列的符号). 设 $c_1$, $c_2$, $\dots$, $c_n$ 是一个文字列, 且其文字全为整数 (也就是, $c_1$, $c_2$, $\dots$, $c_n$ 是整数文字列). 定义其符号为$$\begin{array}{rl}s(c_1,c_2,\dots ,c_n)=& \mathrm{sgn}(c_2-c_1)\\ & \cdot \mathrm{sgn}(c_3-c_1)\cdot \mathrm{sgn}(c_3-c_2)\\ & \cdot \mathrm{sgn}(c_4-c_1)\cdot \mathrm{sgn}(c_4-c_2)\cdot \mathrm{sgn}(c_4-c_3)\\ & \cdot \dots \\ & \cdot \mathrm{sgn}(c_n-c_1)\cdot \mathrm{sgn}(c_n-c_2)\cdot \cdots \cdot \mathrm{sgn}(c_n-c_{n-1})\\ =& \prod _{j=2}^n\prod _{i=1}^{j-1}\mathrm{sgn}(c_j-c_i)\\ =& \prod _{1⩽i<j⩽n}\mathrm{sgn}(c_j-c_i).\end{array}$$

$s$ 也来自英语 sign (或 signum).

显然, 若 $c_1$, $c_2$, $\dots$, $c_n$ 里有二个相同的文字 (也就是, 存在整数 $i$, $j$, 使 $1⩽i<j⩽n$, 且 $c_i=c_j$), 则此文字列的符号为 $0$. 反过来, 因为非零的整数的积不是 $0$, 故符号为 $0$ 的文字列有二个相同的文字.

有一件小事值得提. 若一个文字列恰含一个文字, 我们说, 它 (作为文字列) 的符号是 $1$. 这跟前面的公式是一样的: 既然没有整数对 $(i,j)$ 适合 $1⩽i<j⩽1$, 那这个积就是 $1$.

不要混淆 $\mathrm{sgn}$ 跟 $s$: 比如, $s(0)=1$, 但 $\mathrm{sgn}(0)=0$; 又比如, $s(-3)=1$, 但 $\mathrm{sgn}(-3)=-1$.

排列是特别的文字列 (排列的文字互不相同), 故排列也有符号, 其要么是 $1$, 要么是 $-1$. 根据 $\mathrm{sgn}$ 与 $\rho$ 的关系, 再利用 $-1$ 的整数次方的性质, 不难得到排列的逆序数与符号的关系:

定理 4.3. 设 $a_1$, $a_2$, $\dots$, $a_n$ 是互不相同的 $n$ 个整数. 设 $c_1$, $c_2$, $\dots$, $c_n$ 是 $a_1$, $a_2$, $\dots$, $a_n$ 的一个排列. 则$$\begin{array}{r}s(c_1,c_2,\dots ,c_n)=(-1{)}^{\tau (c_1,c_2,\dots ,c_n)}.\end{array}$$

一个恰含一个文字的文字列的文字也是互不相同的, 故此文字列当然是一个排列. 我们说过, 恰含一个文字的排列的逆序数为 $0$. 因为 $(-1{)}^0=1$, 故, 约定恰含一个文字的文字列 (排列) 的符号为 $1$, 不是没有道理的.