雙序置換的最長遞增子列

崔漢哲

（上海電機學(xué)院 數(shù)理教學(xué)部，上海201306）

長久以來，置換因其豐富的組合結(jié)構(gòu)與代數(shù)結(jié)構(gòu)一直是組合數(shù)學(xué)與代數(shù)學(xué)的重要研究對象。置換研究中的某些問題還與其他一些似乎聯(lián)系不大的數(shù)學(xué)分支有關(guān)，最長遞增子列便是一例。

最長遞增子列的研究最早由Ulam于20世紀(jì)60年代初提出，研究的核心問題是其長度在隨機置換中的漸進(jìn)分布[1]。經(jīng)過近40年的發(fā)展，Baik等[2]于1999年證明了在一般隨機置換中，最長遞增子列長度的漸進(jìn)分布為Tracy-Widom分布；期間，除組合學(xué)和代數(shù)學(xué)外，他們還運用了分析學(xué)、概率論、算子理論、微分方程、特殊函數(shù)、表示論等數(shù)學(xué)分支的知識和方法。而Baik等[3-4]研究的重要成果證明了在組合學(xué)與隨機矩陣?yán)碚撝g存在著緊密的聯(lián)系，并引發(fā)了學(xué)者們進(jìn)一步的研究興趣。

除在一般置換中研究最長遞增子列外，某些特殊置換中的情形也受到了關(guān)注[5-11]，其中，漸進(jìn)分布仍然是研究的重點。而本文對一類特殊置換的研究表明，其最長遞增子列長度的分布概率可以被精確計算。方法是先將該類置換與另一基本的組合對象——楊氏表（Young Tableau）建立聯(lián)系，然后利用楊氏表的計數(shù)方法來完成。

1 定義與引理

本文中，長度為n的置換π表示為其中＝ ｛1，2，…，n｝ ，i＝1，2，…，n，且兩兩不同。

定義1 若置換中有，且i1＜i2＜…＜ik，則稱為π的一個長度為k的遞增子列。所有遞增子列中長度最大者稱為的最長遞增子列。遞減子列的定義完全類似。

定義2 若長度為2n的置換滿足則稱其為雙序置換（2-Ordered Permutation）。

顯然，所有長度為2n的雙序置換的個數(shù)為二項式系數(shù)其最長遞增子列長度的可能取值為n，n＋1，…，2n。本文研究的主要問題實質(zhì)是，在所有長度為2n的雙序置換中，最長遞增子列的長度為n＋k（k＝0，1，…，n）的置換個數(shù)。不同于一般置換中的情形，該數(shù)在雙序置換中可以被精確計算。為此要在置換與楊氏表間建立聯(lián)系。楊氏表的定義、基本術(shù)語和性質(zhì)可參見文獻(xiàn)[12-13] 。本文利用在置換與楊氏表的二元組（P，Q）之間建立一一對應(yīng)的Robinson-Schensted-Knuth算法（簡稱為 RSK 算法）[12-13]。

引理1 所有長度為2n的雙序置換與所有行數(shù)為1或2的楊氏表（元素個數(shù)2n）之間存在一一對應(yīng)關(guān)系。在該對應(yīng)關(guān)系之下，最長遞增子列長度為n＋k的置換恰好對應(yīng)第1行長度為n＋k的楊氏表。

證明 記雙序置換楊氏表二元組（P，Q）中P的第1行為x1x2…xn＋k，第2行為y1y2…yn-k，（k∈[n] ∪｛0｝）。

首先建立一一對應(yīng)關(guān)系。從長度為2n的雙序置換到行數(shù)為1或2的楊氏表的映射f即為RSK算法中，由置換生成楊氏表二元組（P，Q）中的P。RSK算法的性質(zhì)說明的最長遞減子列長度恰為楊氏表二元組（P，Q）中P的行數(shù)，即第1列的長度[8] 53。當(dāng)為雙序置換時的最長遞減子列長度最多為2，故此時生成的楊氏表行數(shù)為1或2。且容易驗證，此時，RSK算法有十分簡單的形式，其算法步驟如下：

步驟1 令

步驟2 當(dāng)m＝2n＋1時，算法停止，此時得到的楊氏表即為f（π）；否則

（1）若πm＞xi，則令xi＋1＝，再令i＝i＋1，m＝m＋1，返回至步驟2；

（2）若，則令，再令j＝j(luò)＋1，m＝m＋1，返回至步驟2。

例：設(shè)＝1 3 2 5 4 6，則f）的第1行為1 2 4 6，第2行為3 5。

為構(gòu)造的逆映射g，本文分析中兩行元素的構(gòu)成。由上述算法的步驟2與雙序置換的定義，可驗證f（π）的第2行元素為中所有滿足的從左到右依次排列而成的其余元素依次排列為的第1行。由此，可得f（π）的逆映射g，即從行數(shù)為1或2的楊氏表生成雙重序列置換的算法如下：

步驟1 令i＝n＋k，j＝n-k，m＝2n。

步驟2 當(dāng)m＝0時，算法停止，此時得到的即為g（P）；否則

（1）若yj＜xi，則令＝xi，再令i＝i-1，m＝m-1，返回至步驟2；

（2）若yj＞xi，則令＝＝y(tǒng)j，再令i＝i-1，j＝j(luò)-1，m＝m-2，返回至步驟2。

由f與g的互逆性保證g（P）為一個雙序置換，于是一一對應(yīng)關(guān)系建立。

RSK算法的性質(zhì)說明，在上述對應(yīng)關(guān)系下，P的第1行長度，即列的個數(shù)恰為π的最長遞增子列長度[13] 99。 證畢。

2 定理及其證明

本文采用隨機置換的語言敘述定理。一個隨機雙序置換是指在所有雙序置換中等可能隨機選取的置換。令Ln為長度為2n的隨機雙序置換中最長遞增子列的長度。

定理1Ln的分布為

期望為

方差為

證明 為求P（Ln＝n＋k），只需計算所有長度為2n的雙序置換中，最長遞增子列長度為n＋k的置換個數(shù)。而根據(jù)引理1，這恰是所有1行與2行的楊氏表中，首行長度為n＋k的楊氏表個數(shù)。為此，本文用計算楊氏表個數(shù)的鉤形公式[12-13]，該數(shù)為

由此可得P（Ln＝n＋k）。

為求Ln的期望與方差，先計算

于是，

由于再將B1、B2代入，化簡便得

故

類似地，有

令l＝n-k，則

故Ln的方差

證畢。

作為上述定理的一個簡單應(yīng)用，可以求出雙序置換的另外一個重要統(tǒng)計量——下降數(shù)的分布。在置換中，若，則稱i為π的一個下降。中所有下降的個數(shù)稱為的下降數(shù)，記為在所有長度為n的置換中，下降數(shù)為k的置換個數(shù)為歐拉數(shù)（Eulerian Number）A（n，k＋1）[14-15]。而對于雙序置換，下降數(shù)與最長遞增子列的長度有如下關(guān)系。

性質(zhì)1 當(dāng)為長度2n的雙序置換時，2n-為其最長遞增子列的長度。

證明 若中有則顯然與不能同時出現(xiàn)在遞增子列中。另一方面，引理1中對映射f的分析說明，將所有的下降i處的刪除后，余下元素即組成的一個最長遞增子列。

證畢。

令Dn為長度為2n的隨機雙序置換的下降數(shù)，則由Dn＝2n-Ln和定理1可得：

推論1Dn的分布為

期望為

方差為

3 結(jié) 語

本文在雙序置換與一類楊氏表之間建立一一對應(yīng)關(guān)系，從而給出隨機雙序置換中最長遞增子列長度的分布。一直以來，最長遞增子列的核心問題是漸進(jìn)分布，于是自然存在如下問題：當(dāng)n→∞時，Ln的漸進(jìn)分布為何，它是否為某個已知隨機變量的分布函數(shù)，該分布函數(shù)在概率論或隨機矩陣?yán)碚撝惺欠褚呀?jīng)有比較重要的應(yīng)用等都有待進(jìn)一步研究。

[1] Ulam S M.Monte Carlo calculations in problems of mathematical physics[J] .Modern Mathematics for the Engineer，1961：261-281.

[2] Baik J，Deift P，Johansson K.On the distribution of the length of the longest increasing subsequence of random permutations[J] .Journal of the American Mathematical Society，1999，12（4）：1119-1178.

[3] Baik J，Deift P，Johansson K.On the distribution of the length of the second raw of a Young diagram under plancherel measure[J] .Geometric and Functional Analysis，2000，10（4）：702-731.

[4] Stanley R P.Increasing and decreasing subsequences and their variants[C] ∥Proceeding of the International Congress of Mathematicians.Madrid：[s.n.] ，2007：545-579.

[5] Pittel B.Romik D.Limit shapes for random square Young Tableaux[J] .Advances in Applied Mathematics，2007，38（2）：164-209.

[6] Romik D.Arctic circles，domino tilings and square Young Tableaux[J] .The Annals of Probability，2012，40（2）：437-891.

[7] Odlyzko A M，Rains E M.On longest increasing subsequences in random permutations[J] .Contemporary Mathematics，2000，251：439-452.

[8] Bespamyatnikh S，Segal M.Enumerating longest increasing subsequences and patience sorting[J] .Information Processing Letters，2000，76（1）：7-11.

[9] Albert M H，Golynski A，Hamel A M.Longest increasing subsequences in sliding windows[J] .Theoretical Computer Science，2004，321（2-3）：405-414.

[10] Albert M H，Atkinson M D，Nussbaum D.On the longest increasing subsequence of a circular list[J] .Information Processing Letters，2007，101（2）：55-59.

[11] Chen Erdong，Yang Linji，Yuan Hao.Longest increasing subsequences in windows based on canonical antichain partition[J] .Theoretical computer science，2007，378（3）：223-236.

[12] Stanley R P.Enumerative Combinatorics：Vol.1[M] .2nd ed.Cambridge：Cambridge University Press，2011：38.

[13] Sagan B E.The symmetric group：Representations，Combinatorial Algorithms，and Symmetric Functions[M] .2nd.ed.[s.L.] ：Springer-Verlag，New York Inc，2001：53，99.

[14] Stanley R P.Enumerative Combinatorics：Vol.2[M] .Cambridge：Cambridge University Press，1999：316.

[15] Bona M.Combinatorics of Permutations[M] .[s.L.] ：Chapman ＆ Hall／CRC，2012：5.