B型非交錯連接分拆及其計數

崔漢哲

(上海電機學院 數理教學部， 上海 201306)

?

B型非交錯連接分拆及其計數

崔漢哲

(上海電機學院 數理教學部， 上海 201306)

摘要:連接分拆與非交錯連接分拆是一類重要的組合研究對象。將A型非交錯連接分拆推廣到B型，針對[±n]的所有B型非交錯連接分拆組成的集合NCL(B)(n)，找到了其基數fspan滿足的遞推公式，并得到其生成函數。

關鍵詞:B型連接分拆； B型非交錯連接分拆； 生成函數

1997年，Reiner[1]在研究超平面配置時，根據Coxeter群的3類無窮族——A、B、D型，相應提出了3種類型的非交錯分拆。傳統的非交錯分拆為A型。受此啟發，近20年來，組合學研究者將許多傳統的A型組合對象推廣為B型與D型，進而研究它們的各種組合性質,如B型分拆[2-3]、圓環上的B型與D型非交錯分拆[4]、B型結合多面體[5]、B型置換表[6-7]等。這方面的綜述可參見文獻[8]。

連接分拆與非交錯連接分拆是在非交換概率論的研究中起重要作用的一類組合對象[9-11],其本身具有豐富的性質。不同學者已經研究了它的計數性質[12]、代數結構[13]以及與其他一些組合對象的聯系[14]。本文將把傳統的A型非交錯連接分拆推廣為B型，并以生成函數的形式給出它的一些計數結果。

1定義與引理

集合{1,2,…,n,-1,-2,…,-n}在偏序關系1<2<…

對于a∈Z，定義絕對值映射abs： Z→N為 absa∶=|a|。對于Z的子集V，記-V為將V中所有元素取相反數而得的集合，記absV為將V中所有元素取絕對值后而得到的集合。若集合π以Z的若干子集為元素，類似定義-π與absπ。

連接分拆與非交錯連接分拆的定義見文獻[13]中的定義2與3，本文不再贅述。[n]的所有連接分拆組成的集合記為LP(n)，[n]的所有非交錯連接分拆組成的集合記為NCL(n)。

定義1[±n]的一個B型連接分拆(linked partition of type B)是指以[±n]的若干子集為元素的集合π，且滿足以下條件：

(1) 這些子集的并為[±n]；

(2) 若V∈π，則-V∈π；

(3)π中至多有一個元素W,滿足W=-W，此時稱W為π的零分塊；

(4) absπ∈LP(n)。

[±n]的所有B型連接分拆組成的集合記為LP(B)(n)。對于π∈LP(B)(n)，稱π的元素為塊或分塊。若i,j∈[±n]屬于π中的同一分塊，則記i～πj(當上、下文中意義明確時，可將下標省略)。若π中分塊彼此非交錯，即不存在如下情況：a,b,c,d∈[±n]，其中,a,c屬于π的某一分塊；b,d屬于π的另一分塊，且在[±n]的全序關系下有a

注1定義1中的條件(2)表明B型組合對象的對稱性，條件(3)則與文獻[1]中的B型分拆的定義保持一致，條件(1)與條件(4)是容易理解的。

注2對于B型非交錯連接分拆，可將定義1中的條件(3)略去。因為易知這是非交錯條件的一個自然推論。

例{{1,2,-1,-2},{2,3},{-2,-3}}∈NCL(B)(3)，而

{{1,2,-1,-2},{2,-3},{-2,3}}∈

LP(3)(3)NCL(B)(3)

本文給出B型非交錯連接分拆的幾個簡單性質。

性質1對于π∈LP(B)(n)，p∈[±n]，則p在π中為單覆蓋或雙重覆蓋。且

(1)p在π中為單覆蓋?-p在π中為單覆蓋?absp在absπ中為單覆蓋；

(2)p在π中為雙重覆蓋?-p在π中為雙重覆蓋?absp在absπ中為雙重覆蓋。

證明由定義1易知，p在π中為單(雙重)覆蓋?-p在π中為單(雙重)覆蓋。因此，只需證明p在π中為單覆蓋或雙重覆蓋以及p在π中為單覆蓋?absp在absπ中為單覆蓋即可。

(1) 證明p在π中為單覆蓋或雙重覆蓋。用反證法。假設存在不同分塊A,B,C∈π，且滿足p∈A，p∈B，p∈C，則有

absp∈absA，absp∈absB，absp∈absC

absA∈absπ，absB∈absπ

absC∈absπ，absπ∈LP(n)

由LP(n)的定義(見文獻[13]中的定義2)，可知absp在absπ中為單覆蓋或雙重覆蓋。因此，不妨設absA=absB。由于A、B為π中不同分塊，故由定義1可知

A=-B且A∩B=?

但這與p∈A∩B矛盾。

(2) 若p在π中被分塊A單覆蓋，則在absπ中absp顯然被分塊absA單覆蓋。反之，設absp在absπ中被分塊E單覆蓋。若π中存在分塊F滿足F∩-F=?且absF=abs-F=E，則在π中p被F或-F單覆蓋同時p被-F或F單覆蓋)。若π中存在零分塊F滿足absF=E，則在π中p與-p均被F單覆蓋。這樣便證明了p在π中為單覆蓋?absp在absπ中為單覆蓋。證畢。

由性質1以及LP(n)的定義(見文獻[13]中的定義2)還可得以下推論。

性質2±1,±n在π∈LP(B)(n)中均為單覆蓋。

性質3若π∈NCL(B)(n)，則absπ∈NCL(n)。

證明由NCL(B)(n)?LP(B)(n)，有absπ∈LP(n)，故只需證明absπ滿足非交錯條件即可。用反證法。

設1≤a

證畢。

以下引理總結了文獻[9,12]中關于NCL(n)的一些計數結果。在定理的證明中將會用到。

引理1設n∈N，記sn∶=|NCL(n)|，則sn恰為第n-1個大Schroder數(the(n-1)th large schroder number)[15-16]。若記sn的生成函數為

則S(x)滿足

S2(x)+(x-1)S(x)+x=0

(1)

即

(2)

sn滿足的遞推關系s1=1，當n≥2時，

sn=sn-1+s1sn-1+s2sn-2+…+sn-1s1

注意此處的生成函數S(x)與文獻[12]中略有不同，因此，S(x)滿足的方程以及方程的解已是改寫后的結果。

2定理及其證明

定理1設n∈N，記

則

(3)

式中，fn滿足的遞推關系為f1=2，f2=6；當n≥3時，

(4)

這里的S(x)、sn見引理1。

證明f1=2，f2=6易得。設π∈NCL(B)(n)且n≥3。將元素-n所在分塊記為V，考慮在[±n]的全序之下V中的最小元，記為v。分以下6種情況討論。

情況1v=-n。此時{n}與{-n}同時為單點塊。由性質2，n與-n在π中均為單覆蓋，于是將π限制到[±(n-1)]可以是NCL(B)(n-1)中的任意元素，故π的個數為fn-1。

情況3v=-1。此時n∈-V且V(-V)不為零分塊。由非交錯條件與性質2可知，π|{1,2,…,n-1}可以是集合{σ∈NCL(n)|1～n}≌NCL(n-1)中任意元素，再由對稱性即得π的個數為sn-1。

反之，對于{1,2,…,v}的一個非交錯連接分拆π1，以及滿足v～π2-n(-v～π2n)的{v,v+1,…,n,-v,-v-1,…,-n}上的一個B型非交錯連接分拆π2，可以相應得到[±n]的B型非交錯連接分拆π，且滿足-n所在分塊在[±n]的全序之下的最小元為v。具體構造如下：

于是可知π的個數為s2fn-2+s3fn-3+…+sn-1f1。

于是，情況6中π的個數為

sn-2(f2-s2)+sn-3(f3-s3)+…+

s1(fn-1-sn-1)

(5)

綜合上述6種情況，可得n≥3時，fn的遞推式為

（1）技術人員年齡結構偏大據統計在我國縣鄉畜牧獸醫技術推廣服務體系中，年齡在35歲以下的占28%，36-45歲的占 31%，46-60歲的占41%，年齡結構趨于老化。

式為

fn=2fn-1+2sn-1+(s2fn-2+s3fn-3+…+sn-1f1)+

sn-2(f2-s2)+sn-3(f3-s3)+…+

s1(fn-1-sn-1)

(6)

結合s1=1與s2=3，式(6)改寫為

fn=fn-1+sn-1+2(s1fn-1+s2fn-2+…+

sn-1f1)-(s1sn-1+s2sn-2+…+sn-1s1)

再利用sn的遞推式，得fn的生成函數為

2x+6x2+x[F(x)-2x]+x[S(x)-x]+

2[S(x)F(x)-2x2]-[S2(x)-x2]

(7)

將引理1中式(1)代入式(7)，整理可得

F(x)=[3x+(2x-1)S(x)]/[1-x-2S(x)]

(8)

最后，將引理1中的式(2)代入式(8)，即得

證畢。

參考文獻：

[1]Reiner V.Non-crossing partitions for classical reflection groups[J].Discrete Mathematics,1997,177(1/3)： 195-222.

[2]Chen W Y C,Wang D G L.Minimally intersecting set partitions of type B[J].The Electronic Journal of Combinatorics,2010,17(1)： R22.

[3]Chen W Y C,Wang D G L.Singletons and adjacencies of set partitions of type B[J].Discrete Mathematics,2011,311(6)： 418-422.

[4]Nica A,Oancea I.Posets of annular non-crossing partitions of types B and D[J].Discrete Mathematics,2009,309(6)： 1443-1466.

[5]Simion R.A type-B associahedron[J].Advances in Applied Mathematics,2003,30(1/2)： 2-25.

[6]Corteel S,Kim J S.Combinatorics on permutation tableaux of type A and type B[J].European Journal of Combinatorics,2011,32(4)： 563-579.

[7]Corteel S,Josuat-Verges M,Kim J S.Combinatorics of the permutation tableaux of type B[J].arXiv,2012： 1203.0154.

[8]Armstrong D.Generalized noncrossing partitions and combinatorics of Coxeter groups[M].[S.L.]： American Mathematical Society,2009： 81-115.

[9]Dykema K J.Multilinear function series and transforms in free probability theory[J].Advances in Mathematics,2007,208(1)： 351-407.

[10]Popa M.Non-crossing linked partitions and multiplication of free random variables[J].arXiv,2008： 0812.2064.

[11]Nica A.Non-crossing linked partitions,the partial order on NC(n), and the S-transform[J].Proceedings of the American Mathematical Society,2010,138(4)： 1273-1285.

[12]Chen W Y C,Wu S Y J,Yan C H.Linked partitions and linked cycles[J].European Journal of Combinatorics,2008,29(6)： 1408-1426.

[13]崔漢哲.非交錯連接分拆的等價描述[J].上海電機學院學報，2012，15(6)： 409-413.

[14]Chen W Y C,Wang C J.Noncrossing linked partitions and large(3,2)-Motzkin paths[J].Discrete Mathematics,2012,312(11)： 1918-1922.

[15]Stanley R P.Enumerative combinatorics.Vol.2[M].[S.L]:Cambridge University Press,1999: 178,219.

[16]Sloane N J.The On-Line Encyclopedia of Integer Sequences (OEIS)[EB/OL].(2014-12-15).http:∥oeis.org.

Type B Non-Crossing Linked Partition and Enumeration

CUIHanzhe

(Department of Mathematics and Physics, Shanghai Dianji University, Shanghai 201306, China)

Abstract:Both linked partitions and non-crossing linked partitions are important combinational objects. We extend non-crossing linked partitions of type A to those of type B, and find the recurrence formula satisfied by cardinal number of the set which consists of all non-crossing linked partitions of type B on [±n]. Its generating function is also obtained.

Key words:type B linked partition; non-crossing linked partition of type B; generating function

文獻標志碼:A

中圖分類號:O 157.1

文章編號2095 - 0020(2015)01 -0042 - 04

作者簡介：崔漢哲(1980-)，男，講師，博士，主要研究方向為算子代數和組合數學，E-mail： cuihz@sdju.edu.cn

收稿日期：2015 - 01 - 08