逆序数

逆序数的定义

定义：逆序数

令 $\pi= \pi_1 \pi_2\cdots \pi_n\in S_n$ ，则 $\pi$的一个逆序对定义为
$$ (\pi_i,\pi_j) ,1\leqslant i< j \leqslant n$$
定义 $\pi$ 的所有逆序的个数称为 $\pi$ 的逆序数. 记为：
$$ \mathrm{inv}(\pi) = |\left\lbrace (\pi_i,\pi_j) | 1\leqslant i< j \leqslant n \text{ and } \pi_i> \pi_j \right\rbrace| $$

例如，对于 $\pi = 2413$ ，逆序对有：

\[ (2,1) , (4,1) , (4,3) \]

因此逆序数 $\mathrm{inv}(\pi)=3$ .

逆序数的生成函数

观察逆序数的生成函数：

\[ \sum\limits_{\pi\in S_n} q^{\mathrm{inv}(\pi)} = ? \]

对 $n=3$ ，所有的逆序数情形为：

\[ \begin{aligned} \mathrm{inv}(123) = 0,\mathrm{inv}(132)=1 , \mathrm{inv}(213)=1 \\ \mathrm{inv}(231)=2, \mathrm{inv}(312)=2, \mathrm{inv}(321)=3 \end{aligned} \]

那么我们就有：

\[ \begin{aligned} \sum\limits_{\pi\in S_3} q^{\mathrm{inv}(\pi)} &= 1+2q+2q^2 +q^3 \\ &= 1\cdot (1+q)(1+q+q^2) \end{aligned} \]

当 $q=1$ 时，我们能发现这个和式的取值恰好为 $|S_3|=1\cdot 2\cdot 3 = 6$ . 因此有如下的定理猜想：

定理

对 $k \geqslant 1$ ，记 $[k]=1+q+q^2+\cdots+ q^{k-1}$ . 则
$$ \sum\limits_{\pi\in S_n} q^{\mathrm{inv}(\pi)}=[1]\cdot[2]\cdots[n] = [n]!$$

证明：
记

\[ I_n = \left\lbrace (a_1,a_2,\cdots,a_n)|0 \leqslant a_i \leqslant n-i \right\rbrace \]

那么 $I_n$ 的生成函数为：

\[ \begin{aligned} &\sum\limits_{(a_1,a_2,\cdots,a_n)\in I_n} q^{a_1+a_2+\cdots+a_n}\\ &= \left(\sum\limits_{i=0}^{n-1} q^i\right) \left(\sum\limits_{i=0}^{n-2} q^i\right)\cdots \left(\sum\limits_{i=0}^{0} q^i\right) \\ &=[n]\cdot [n-1]\cdots [1] = [n]! \end{aligned} \]

建立双射：

\[ \varphi: S_n \to I_n, \varphi(\pi) = (a_1,\cdots,a_n) \]

其中，对于 $1\leqslant i \leqslant n$ ，有

\[ a_i = |\left\lbrace j | i<j \leqslant n, \pi_i > \pi_j \right\rbrace| \]

比如：$\pi = 2413$ 中，对于第一位的 $2$ ，仅有后面的 $1$ 比它小，对第二位的 $4$ 则有 $1,3$ 比它小，因此：

\[ \varphi(\pi) = (1,2,0,0) \]

那么 $\mathrm{inv}(\pi) = \sum\limits_{i=1}^n a_i$ .

下面验证其为双射：
构造逆映射如下：$\varphi^{-1} : (a_1,a_2,\cdots,a_n) \to \pi$ ，映射方法为如下的流程：

已知 $a_1$ 时，可知 $\pi_1$ 后有 $a_1$ 个元素比它小，此时 $\pi_1 = a_1+1$ ；
已知 $a_2$ ，此时在剩余的数中继续选 $a_2+1$ ；
出现 $a_i$ 时，从剩余元素中选择第 $a_i+1$ 小的元素.

因此可以构造出相应的映射. $\square$

拓展：排序的主指标

$\pi = \pi_1 \pi_2 \cdots \pi_n \in S_n$ 的主指标 (major index) 定义为：

\[ \mathrm{maj}(\pi) = \sum\limits_{1 \leqslant i < n, \pi_i > \pi_{i+1}} i \]

比如，$\mathrm{maj}(2431)=2+3=5$ .

其生成函数和逆序数的生成函数是基本一致的，不再赘述.

逆序数

逆序数的定义

逆序数的生成函数

拓展：排序的主指标

评论