我们知道, n个不同元素的任一排列中, 当某两个元素的先后次序与标准次序不同时, 就说有一个逆序, 一个排列中所有逆序的总数, 叫做这个排列的逆序数。下面讨论两种计算排列的逆序数的方法。
方法1:为了不失一般性, 不妨设n个元素为1至n这n个自然数, 并规定由小到大为标准排列 (即排列12Λn为标准排列) 。设p1p2Λpn为这n个自然数的一个排列, 逐个考虑元素pi (i=1, 2, Λ, n) , 如果比ip大且排在ip前面的元素有ti个, 就说ip这个元素的逆序数为ti, 全体元素 (n个) 的逆序数之总和
即是这个排列的逆序数。
方法2:为了不失一般性, 不妨设n个元素为1至n这n个自然数, 并规定由小到大为标准排列 (即排列12Λn为标准排列) 。设p1p2Λpn为这n个自然数的一个排列, 逐个考虑元素pi (i=1, 2, Λ, n) , 如果比ip小且排在ip后面的元素有il个, 就说ip这个元素的逆序数为il, 全体元素 (n个) 的逆序数之总和
即是这个排列的逆序数。
定理:n个不同自然数所构成的排列p1p2Λpn, 按上述两种方法计算出的排列的逆序数是相等的。
证明: (利用数学归纳法证明) 。
(1) 当K=2时, 对于排列p1p2。
如果p1>p2, 两种方法计算排列的逆序数T1=T2=1;
如果p1
(2) 假设命题对于K=n时成立, 即对于排列p1p2Λpn, 按上述两种方法计算出的排列的逆序数相等, T1=T2=T0 (0T为常数) 。
(3) 下面证明当K=n+1时, 命题也成立。
对于自然数pn+1, pn+1≠pj (j=1, 2, Λ, Λ, n) , 将其任意置入排列p1p2Λpi ipi+1Λpn中, 构成排列为
为了证明方便, 设i个数p1, p2, Λ, pi中比pn+1大的元素的个数为m个, 比pn+1小的元素的个数为 (i-m) 个; (n-i) 个数pi+1, pi+2, Λ, Λ, pn中比pn+1大的元素个数为l个, 比pn+1小的元素个数为 (n-i-l) 个。
按第一种方法计算排列的逆序数:插入数pn+1, 并不改变原有的n个数的顺序, 它们之间的逆序数也不会改变, 仍为0T, 因此只需考虑比pn+1大且排在其前面的元素有m个, 比pn+1小且排在其后面的元素有 (n-i-l) 个, 如此计算排列p1p2Λpipn+11p i+1Λpn的逆序数为
按第二种方法计算排列的逆序数:同样, 插入数pn+1, 并不改变原有的n个数的顺序, 它们之间的逆序数也不会改变, 仍为0T, 因此只需考虑比pn+1小且排在其后面的元素有 (n-i-l) 个, 比pn+1大且排在其前面的元素有m个, 如此计算排列p1p2Λpipn+11p i+1Λpn的逆序数为
从而得T1=T2对于K=n+1时也成立。
综上所述, 定理成立。
摘要：本文根据排列的逆序数的定义, 通过两种方法来进行计算, 并证得两种方法是等效的, 从而更加深刻的理解排列的逆序数的定义及其计算。
关键词：排列,逆序数
参考文献
[1] 河北科技大学数学系.线性代数[M].中国标准出版社, 2003.