逆序数

定义 2.2. 逆序数

在一个 排列 中,

• 如果一个较大的数字排在一个较小的数字之前, 则称这两个数字构成一个 逆序.
• 否则, 称这两个数字构成一个 顺序.

在一个排列 $i_1{i}_2\cdots i_n$ 中,逆序的总数称为这个排列的 逆序数,记为 $\tau \left(i_1{i}_2\cdots i_n\right)$

• 逆序数为奇数的排列称为 奇排列,
• 逆序数为偶数的排列称为 偶排列.

Example

比如 8 阶排列 57864312,为方便起见将数 $i$ 与排在其前面的数构成的逆序数记为 ${\tau }_i$ ,则 ${\tau }_1=6,{\tau }_2=6,{\tau }_3=5,{\tau }_4=4,{\tau }_5=0,{\tau }_6=2,{\tau }_7=0,{\tau }_8=0$ 于是 $\tau \left(57864312\right)=6+6+5+4+0+2+0+0=23$ 故 8 阶排列 57864312 是一个奇排列.

Question

请思考: 还有别的计算逆序数的方法吗?

其中一个答案 — 对换.