B型非交錯(cuò)連接分拆及其計(jì)數(shù)

崔漢哲

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

?

B型非交錯(cuò)連接分拆及其計(jì)數(shù)

崔漢哲

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

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

關(guān)鍵詞:B型連接分拆； B型非交錯(cuò)連接分拆； 生成函數(shù)

1997年，Reiner[1]在研究超平面配置時(shí)，根據(jù)Coxeter群的3類(lèi)無(wú)窮族——A、B、D型，相應(yīng)提出了3種類(lèi)型的非交錯(cuò)分拆。傳統(tǒng)的非交錯(cuò)分拆為A型。受此啟發(fā)，近20年來(lái)，組合學(xué)研究者將許多傳統(tǒng)的A型組合對(duì)象推廣為B型與D型，進(jìn)而研究它們的各種組合性質(zhì),如B型分拆[2-3]、圓環(huán)上的B型與D型非交錯(cuò)分拆[4]、B型結(jié)合多面體[5]、B型置換表[6-7]等。這方面的綜述可參見(jiàn)文獻(xiàn)[8]。

連接分拆與非交錯(cuò)連接分拆是在非交換概率論的研究中起重要作用的一類(lèi)組合對(duì)象[9-11],其本身具有豐富的性質(zhì)。不同學(xué)者已經(jīng)研究了它的計(jì)數(shù)性質(zhì)[12]、代數(shù)結(jié)構(gòu)[13]以及與其他一些組合對(duì)象的聯(lián)系[14]。本文將把傳統(tǒng)的A型非交錯(cuò)連接分拆推廣為B型，并以生成函數(shù)的形式給出它的一些計(jì)數(shù)結(jié)果。

1定義與引理

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

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

連接分拆與非交錯(cuò)連接分拆的定義見(jiàn)文獻(xiàn)[13]中的定義2與3，本文不再贅述。[n]的所有連接分拆組成的集合記為L(zhǎng)P(n)，[n]的所有非交錯(cuò)連接分拆組成的集合記為NCL(n)。

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

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

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

(3)π中至多有一個(gè)元素W,滿(mǎn)足W=-W，此時(shí)稱(chēng)W為π的零分塊；

(4) absπ∈LP(n)。

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

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

注2對(duì)于B型非交錯(cuò)連接分拆，可將定義1中的條件(3)略去。因?yàn)橐字@是非交錯(cuò)條件的一個(gè)自然推論。

例{{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型非交錯(cuò)連接分拆的幾個(gè)簡(jiǎn)單性質(zhì)。

性質(zhì)1對(duì)于π∈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在π中為單覆蓋或雙重覆蓋。用反證法。假設(shè)存在不同分塊A,B,C∈π，且滿(mǎn)足p∈A，p∈B，p∈C，則有

absp∈absA，absp∈absB，absp∈absC

absA∈absπ，absB∈absπ

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

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

A=-B且A∩B=?

但這與p∈A∩B矛盾。

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

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

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

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

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

設(shè)1≤a

證畢。

以下引理總結(jié)了文獻(xiàn)[9,12]中關(guān)于NCL(n)的一些計(jì)數(shù)結(jié)果。在定理的證明中將會(huì)用到。

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

則S(x)滿(mǎn)足

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

(1)

即

(2)

sn滿(mǎn)足的遞推關(guān)系s1=1，當(dāng)n≥2時(shí)，

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

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

2定理及其證明

定理1設(shè)n∈N，記

則

(3)

式中，fn滿(mǎn)足的遞推關(guān)系為f1=2，f2=6；當(dāng)n≥3時(shí)，

(4)

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

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

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

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

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

于是可知π的個(gè)數(shù)為s2fn-2+s3fn-3+…+sn-1f1。

于是，情況6中π的個(gè)數(shù)為

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

s1(fn-1-sn-1)

(5)

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

（1）技術(shù)人員年齡結(jié)構(gòu)偏大據(jù)統(tǒng)計(jì)在我國(guó)縣鄉(xiāng)畜牧獸醫(yī)技術(shù)推廣服務(wù)體系中，年齡在35歲以下的占28%，36-45歲的占 31%，46-60歲的占41%，年齡結(jié)構(gòu)趨于老化。

式為

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)

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

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

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

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

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)，即得

證畢。

參考文獻(xiàn)：

[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]崔漢哲.非交錯(cuò)連接分拆的等價(jià)描述[J].上海電機(jī)學(xué)院學(xué)報(bào)，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

文獻(xiàn)標(biāo)志碼:A

中圖分類(lèi)號(hào):O 157.1

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

作者簡(jiǎn)介：崔漢哲(1980-)，男，講師，博士，主要研究方向?yàn)樗阕哟鷶?shù)和組合數(shù)學(xué)，E-mail： cuihz@sdju.edu.cn

收稿日期：2015 - 01 - 08