給定n個數1,2,...,n的一個排列a1a2...an,令bi是數i在此排列中的逆序數,換句話說,bi等於該排列中先於i又大於i的那些數的個數。數列b1b2...bn稱為排列a1a2...an的逆序數列(inversion sequence)。排列與逆序數列一一對應。例如排列32541的逆序數列是01014。解釋如下:b5是4的原因為a5是1,它的前面有3、2、5、4,他們都大於1,所以有4個數大於1。b3是0的原因是a是5,它的前面有3、2,他們都小於5,所以有0個數大於5。
基本介紹
- 中文名:逆序數列
- 外文名:inversion sequence
- 所屬學科:數學
- 所屬問題:排列組合
- 相關概念:逆序,排列,逆序數等
基本介紹,定理構造方法,例題解析,
基本介紹
利用逆序來描述排列的方法是M.Hall,Jr發現的。逆序的概念是一個舊概念,它在矩陣的行列式理論中起著重要作用。令
是集合
的一個排列。如果
而
,
稱為一個逆序。於是,逆序對應一對數,它們在排列中失去自然次序。例如,排列31524中有4 個逆序,即
的唯一沒有逆序的排列是
。對於排列
,我們令
表示第二個分量為
的逆序個數。換句話說,
等於排列中先於
且又大於
的那些整數的個數。它度量
的失序有多少。數列
稱為排列
的逆序數列。上例給出的數列的逆序數列是
。

















排列
的逆序數列必須滿足條件

定理構造方法
定理1 設
是整數數列且
,則存在
的唯一排列,其逆序數列是
。




證明:我們介紹一種方法,可用來唯一地構造其逆序數列為
的一個數列。


































...
1:...
作完
諸步之後,就唯一確定了
的排列,其逆序數列是
。



習慣上,根據
的排列
的逆序個數是偶數還是奇數,稱它為偶排列或奇排列。排列的符號則根據它是否為偶或奇定義為+1或-1。在矩陣的行列式理論中,排列符號的概念是重要的,這裡
階矩陣
的行列式定義為
。這裡求和是指對
的所有排列求和,
為
的符號。








若排列
具有逆序個數為
的逆序數列
則
可以相繼經過k次交換相鄰兩數得到
。我們首先把1逐次與
個在它左邊的數進行交換。然後把2逐次與
個在它左邊的大於2的數交換,等等。用這種方法經
次交換後,我們得到
。









例題解析
試確定
的排列,使其逆序數列為
,對於給定的逆序數列,按照定理證明中的步驟,得到下面的結果:










