逆序數列

逆序數列

給定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 個逆序,即
的唯一沒有逆序的排列是
。對於排列
,我們令
表示第二個分量為
逆序個數。換句話說,
等於排列中先於
且又大於
的那些整數的個數。它度量
的失序有多少。數列
稱為排列
的逆序數列。上例給出的數列的逆序數列是
排列
的逆序數列必須滿足條件
這是顯然的,因為對每一個
,在集合中都有
個整數大於k。利用乘法原理,可知滿足
的整數
的個數等於
。這些數列中每一個都唯一地對應
的一個排列。

定理構造方法

定理1
是整數數列且
,則存在
的唯一排列,其逆序數列是
證明:我們介紹一種方法,可用來唯一地構造其逆序數列為
的一個數列。
:寫 出
:考察:
。已知
,如果,
,則
必在n的前面。如果
,則
必在n的後面。
考察
。已知
。如果
,則
必在由
步得到的兩個數之前,如果,
,則
必在由
步得到的兩個數之間。如果,
,則
必在由
步得到的兩個數之後。
(一般步)考察
。已知
,在由n到
的各步中,k個數
已按要求的次序放好。如果
,則
必在由
步得到的所有數之前。如果
,則
必在頭兩個數之間。...如果
,則
必在所有數之後。
...
1:...
作完
諸步之後,就唯一確定了
的排列,其逆序數列是
習慣上,根據
的排列
的逆序個數是偶數還是奇數,稱它為偶排列奇排列。排列的符號則根據它是否為偶或奇定義為+1或-1。在矩陣的行列式理論中,排列符號的概念是重要的,這裡
階矩陣
的行列式定義為
。這裡求和是指對
的所有排列求和,
的符號。
若排列
具有逆序個數為
的逆序數列
可以相繼經過k次交換相鄰兩數得到
。我們首先把1逐次與
個在它左邊的數進行交換。然後把2逐次與
個在它左邊的大於2的數交換,等等。用這種方法經
次交換後,我們得到

例題解析

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

相關詞條

熱門詞條

聯絡我們