逆序数

                     

贡献者: addis

预备知识 排列

  1我们把集合 $ \left\{1,\dots,N \right\} $ 的某种排列记为 $\pi$,该排列的元素按照顺序分别记为 $\pi_1, \dots, \pi_N$。对于任意 $i < j$,如果满足 $\pi_i > \pi_j$ 我们就把 $i, j$ 或者 $\pi_i, \pi_j$ 称为排列 $\pi$ 的一个逆序对(inversion)。一个排列中所有逆序对的个数就叫逆序数(inversion number)

   逆序数主要的应用有定义行列式列维—奇维塔(Levi-Civita)符号。在这两个应用中,我们只对逆序数的奇偶性感兴趣。我们把逆序数为奇数的排列叫做奇排列,逆序数为偶数的排列叫做偶排列。把按从小到大的顺序排列叫做标准排列。标准排列逆序数为零,是一个偶排列。

例 1 

  • 标准排列 $1,2,3,4$ 中对任意 $i < j$ 都有 $\pi_i < \pi_j$,不存在逆序对,逆序数为零。
  • $4,3,2,1$ 中对任意 $i < j$ 都有 $\pi_i > \pi_j$,任何两个元素都是逆序对,逆序数等于组合 $C_4^2 = 6$。
  • 排列 $1,6,2,5,3,4$ 中,逆序对有 $(6,2)$,$(6,5)$,$(6,3)$,$(6,4)$,$(5,3)$,$(5,4)$。共 $6$ 个。

   一般情况下,要计算逆序数,我们可以依次令 $i = 1, \dots, N$,对每个 $i$,将其右边所有小于 $\pi_i$ 的元素数求和即可。

定理 1 

   交换排列中任意两个不同元素,逆序数奇偶性改变。

证明

   在排列 $p_n$ 中,考虑第 $i, j$($i < j$)两个元素的置换,不妨把他们的值分别记为 $m, n$。不妨假设 $m < n$($n < m$ 的讨论同理)。为了方便讨论,我们把任意两个不同元素都用弧线连起来,这些弧线有的代表逆序对,有的不是。我们可以把这些连线分为 4 类来讨论:

  1. 对于不连接到 $m$ 或 $n$ 的线,置换不改变它们之中的逆序数。
  2. 对于从 $m$ 或 $n$ 连接到 $m$ 左边或 $n$ 右边的线,置换同样不改变他们之中的逆序数。
  3. 若 $m,n$ 不相邻,对于从 $m$ 或 $n$ 连接到 $m, n$ 之间某个元素 $q$ 的两条线,只有当 $m < q < n$ 时逆序数会改变:从两个非逆序对变为逆序对。但无论有多少满足条件的 $q$,逆序数只会增加偶数个。
  4. $m,n$ 在置换前不是逆序对,置换后变为逆序对,使逆序数增加 1,改变逆序数的奇偶性。

   综上所述,逆序对在置换后必定改变奇数个,所以逆序数奇偶性发生变化。证毕。

推论 1 

   把奇排列变为标准排列需要置换奇数次,把偶排列变为标准排列需要置换偶数次。

   证明显然。


1. ^ 参考 Wikipedia 相关页面


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利