崔漢哲
(上海電機(jī)學(xué)院 數(shù)理教學(xué)部, 上海 201306)
B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果
崔漢哲
(上海電機(jī)學(xué)院 數(shù)理教學(xué)部, 上海 201306)
摘要連接分拆與非交錯(cuò)連接分拆是組合數(shù)學(xué)中的重要研究對(duì)象。以遞推式的形式計(jì)算集合[±n]上分塊個(gè)數(shù)為給定偶數(shù)2k的所有B型非交錯(cuò)連接分拆的數(shù)目,并得到其雙重生成函數(shù)。
關(guān)鍵詞B型非交錯(cuò)連接分拆; 遞推式; 雙重生成函數(shù)
連接分拆(linked partitions)與非交錯(cuò)連接分拆(non-crossing linked partitions)是組合數(shù)學(xué)中的一類重要研究對(duì)象,最早在算子代數(shù)的研究中被發(fā)現(xiàn)。它們?cè)谟?jì)算經(jīng)典非交換概率論中T—變換的形式冪級(jí)數(shù)系數(shù)時(shí)起到了重要作用[1],在非交換概率論的其他方面也有廣泛應(yīng)用[2-6]。與此同時(shí),不同學(xué)者從組合數(shù)學(xué)的多個(gè)角度也探究了它們作為組合對(duì)象的豐富性質(zhì),如計(jì)數(shù)性質(zhì)[7]、代數(shù)結(jié)構(gòu)[8]、與其他組合對(duì)象的聯(lián)系[9-13]等。
另一方面,文獻(xiàn)[14]中從一類和組合數(shù)學(xué)有密切關(guān)系的重要代數(shù)結(jié)構(gòu)——Coxeter群的分類角度出發(fā),定義了一大類組合對(duì)象的A、B和D型。根據(jù)此觀點(diǎn),文獻(xiàn)[15]中將傳統(tǒng)的A型非交錯(cuò)連接分拆推廣到B型,研究了它們的基本性質(zhì)并得到一些基本的計(jì)數(shù)結(jié)果,即計(jì)算了集合[±n]={1,2,…,n,-1,-2,…,-n}上所有B型非交錯(cuò)連接分拆的個(gè)數(shù)。在此基礎(chǔ)上,本文進(jìn)一步考慮如下問題: 對(duì)于集合[±n]上的B型非交錯(cuò)連接分拆,在分塊個(gè)數(shù)為給定正整數(shù)的情況下,它們的個(gè)數(shù)是多少?記[±n]上所有分塊個(gè)數(shù)為偶數(shù)2k的B型非交錯(cuò)連接分拆的個(gè)數(shù)為a(n,k),本文將給出a(n,k)滿足的遞推式及其雙重生成函數(shù)的具體表達(dá)式。
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的若干子集為元素,則定義-π為{-V|V∈π},absπ為{absV|V∈π}。 連接分拆與非交錯(cuò)連接分拆的定義見文獻(xiàn)[8]中的定義2、3,本文不再贅述。[n]的所有連接分拆組成的集合記為L(zhǎng)P(n)。[n]的所有非交錯(cuò)連接分拆組成的集合記為NCL(n)。為敘述完整,本文先給出B型連接分拆和B型非交錯(cuò)連接分拆的定義。 定義1[15][±n]的一個(gè)B型連接分拆(linked partition of type B)是指以[±n]的若干子集為元素的集合π,且滿足以下條件: (1) 這些子集的并為[±n]; (2) 若V∈π,則-V∈π; (3)π中至多有一個(gè)元素W滿足W=-W,此時(shí)稱W為π的零分塊; (4) absπ∈LP(n)。 [±n]的所有B型連接分拆組成的集合記為L(zhǎng)P(B)(n)。對(duì)于π∈LP(B)(n),稱π的元素為塊或分塊。若i,j∈[±n]屬于π中的同一分塊,則記i~πj(當(dāng)上、下文意義明確時(shí),可將下標(biāo)省略)。若π中分塊彼此非交錯(cuò),即不存在以下情況:a,b,c,d∈[±n],a、c屬于π的某一分塊,b、d屬于π的另一分塊,且在[±n]的全序關(guān)系之下有a 以下B型非交錯(cuò)連接分拆的幾個(gè)簡(jiǎn)單性質(zhì)在定理的證明中會(huì)用到。具體證明見文獻(xiàn)[15]。 性質(zhì)1若π∈LP(B)(n),p∈[±n],則p在π中為單覆蓋或雙重覆蓋,且 (1)p在π中為單覆蓋?-p在π中為單覆蓋?absp在absπ中為單覆蓋; (2)p在π中為雙重覆蓋?-p在π中為雙重覆蓋?absp在absπ中為雙重覆蓋。 性質(zhì)2±1,±n在π∈LP(B)(n)中均為單覆蓋。 性質(zhì)3若π∈NCL(B)(n),則absπ∈NCL(n)。 對(duì)于π∈NCL(B)(n),其分塊個(gè)數(shù)有兩種情況: ①π包含零分塊,其分塊個(gè)數(shù)為奇數(shù);②π不包含零分塊,其分塊個(gè)數(shù)為偶數(shù)。本文考慮π不包含零分塊的情形。 以下引理總結(jié)了文獻(xiàn)[7]中關(guān)于NCL(n)相應(yīng)的計(jì)數(shù)結(jié)果,在定理的證明中將會(huì)用到。 引理1記b(n,k)為NCL(n)中分塊個(gè)數(shù)為k(1≤k≤n)的元素個(gè)數(shù),其雙重生成函數(shù)為 則 (1+x-t x)B2(x,t)+ (x-1)B(x,t)+x t=0 (1) 由此可解得 B(x,t)= (2) 注: 此處的生成函數(shù)B(x,t)與文獻(xiàn)[7]中的定義略有不同,本文省略了常數(shù)項(xiàng),故B(x,t)滿足的方程與最后的解是改寫后的結(jié)果。 2定理及其證明 定理1記a(n,k)為NCL(B)(n)中分塊個(gè)數(shù)為2k的元素個(gè)數(shù),其雙重生成函數(shù)為 則 (3) 其中,B(x,t)見引理1。 證明先推導(dǎo)a(n,k)的遞推式,再由此解出雙重生成函數(shù)。 根據(jù)定義容易得到如下邊界條件: 當(dāng)k>n時(shí), a(n,k)=b(n,k)=0 a(n,n)=1 此時(shí)的π∈NCL(B)(n)只有一種可能,即由2n個(gè)單點(diǎn)塊組成。 為方便本文推導(dǎo),再令 a(n,0)=b(n,0)=0 另外,當(dāng)π∈NCL(B)(n)的分塊個(gè)數(shù)為2時(shí),有π={{1,…,j,-j-1,…,-n},{j+1,…,n,-1,…,-j}}(1≤j≤n)。因此,有初值條件a(n,1)=n,類似可得b(n,1)=1,其中,b(n,k)見引理1。 以下設(shè)n≥3,k≥2,π∈NCL(B)(n)且分塊個(gè)數(shù)為2k(1≤k≤n)。將π中-n所在分塊記為V,考慮在[±n]的全序之下的V中最小元,記為v,以下分6種情況討論。 (1)v=-n,即{n}與{-n}同時(shí)為單點(diǎn)塊。由性質(zhì)2可見,n與-n在π中均為單覆蓋。于是,將π限制到[±(n-1)]可以是NCL(B)(n-1)中的任意元素,且分塊個(gè)數(shù)為2(k-1)。故此時(shí)π的個(gè)數(shù)為 K=a(n-1,k-1) (4) (2)v=n即{n,-n}為π中的零分塊。此時(shí)π中分塊個(gè)數(shù)應(yīng)為奇數(shù),與題設(shè)矛盾。因此,該情況不出現(xiàn),無(wú)需討論。 K=b(n-1,k) (5) (4)v=1。此時(shí),π∈{σ∈NCL(B)(n)|1~-n(-1~n)}?NCL(B)(n-1)且分塊個(gè)數(shù)為2k,因此,π的個(gè)數(shù)為 K=a(n-1,k) (6) (5)v∈{2,3,…,n-1}。將v記成i,分以下兩種情形討論。 ①i在π中為單覆蓋。此時(shí)由非交錯(cuò)條件可知 (7) b(i-1,k-u-1)] (8) 綜合上述兩種情形,情況5中π的總個(gè)數(shù)為 b(i,k-u)-b(i-1,k-u-1)] (9) (6)v∈{-2,-3,…,1-n}。將v記成i,類似情況5,也分以下2種情形討論。 ①i在π中為單覆蓋。此時(shí)由非交錯(cuò)條件可知 (10) a(i-1,k-u-1)] (11) 綜合上述兩種情形,情況6中π的總個(gè)數(shù)為 a(i,k-u)-a(i-1,k-u-1)] (12) 綜合上述6種情況,得到n≥3,k≥2時(shí),a(n,k)的遞推式如下: a(n,k)=a(n-1,k-1)+b(n-1,k)+ [b(i-1,k-u)+b(i,k-u)- b(i-1,k-u-1)]+ a(i,k-u)-a(i-1,k-u-1)] (13) 通過(guò)變換下標(biāo),結(jié)合定理證明的邊界條件和初值條件,可將式(13)等號(hào)右側(cè)第4、5項(xiàng)的雙重和式簡(jiǎn)單變形為 b(i,k-1-u) 再用邊界條件,可知 b(1,k-u)]=b(n-1,k-1)+a(n-1,k-1) A(x,t)=(x t+2x2t+…+nxnt+…)+x2t2+ x t[A(x,t)-xt]+x[B(x,t)-(xt+ x2t+…+xnt+…)]+x[A(x,t)- (x t+2x2t+…+nxnt+…)]+ 2xA(x,t)B(x,t)+2[A(x,t)B(x,t)- x2t2]-x t[B(x,t)-x t]-x t[A(x,t)- x t]-2xtA(x,t)B(x,t)= x t+xA(x,t)+(2+2x-2x t)· A(x,t)B(x,t)+xB(x,t)-x tB(x,t) 最后利用式(2)可解出 證畢。 參考文獻(xiàn) [1]DYKEMA K J.Multilinear function series and transforms in free probability theory[J].Advances in Mathematics,2007,208(1): 351-407. [2]POPA M.Non-crossing linked partitions and multiplication of free random variables[J].arXiv,2008: 0812.2064. [3]NICA A.Non-crossing linked partitions,the partial order onNC(n),and the S-transform[J].Proceedings of the American Mathematical Society,2010,138(4): 1273-1285. [4]POPA M,Wang J C.On multiplicative conditionally free convolution[J].Transactions of the American Mathematical Society,2011,363(12): 6309-6335. [5]ARIZMENDI O,VARGAS C.Product of free random variables and k-divisible non-crossing partitions[J].Electronic Communicatious in Probability,2012,17(5): 489-500. [6]POPA M,VINNIKOV V,WANG J C.On the multiplication of operator-valued c-free random variables[J].arXiv,2015: 1509.08853. [7]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. [8]崔漢哲.非交錯(cuò)連接分拆的等價(jià)描述[J].上海電機(jī)學(xué)院學(xué)報(bào),2012,15(6): 409-413. [9]KASRAOUI A.Ascents and descents in 01-fillings of moon polyominoes[J].European Journal of Combinatorics,2010,31(1): 87-105. [10]KIM J S.Front representation of set partitions[J].SIAM Journal on Discrete Mathematics,2009,25(1): 447-461. [11]CHEN W Y C,WANG C J.Noncrossing linked partitions and large(3, 2)-Motzkin paths[J].Discrete Mathematics,2012,312(11): 1918-1922. [12]CHEN W Y C,LIU L H,WANG C J.Linked partitions and permutation tableaux[J].arXiv,2013: 1305.5357. [13]CHEN W Y C,GUO P L,PANG S X M.Vacillating hecke tableaux and linked partitions[J].Mathematische Zeitschrift,2015,281(3): 661-672. [14]REINER V.Non-crossing partitions for classical reflection groups[J].Discrete Mathematics,1997,177(1/3): 195-222. [15]崔漢哲.B型非交錯(cuò)連接分拆及其計(jì)數(shù)[J].上海電機(jī)學(xué)院學(xué)報(bào),2015,18(1): 42-45. Enumerative Result for Non-crossing Linked Partitions of Type B CUI Hanzhe (Department of Mathematics and Physics, Shanghai Dianji University, Shanghai 201306, China) AbstractBoth linked partitions and non-crossing linked partitions are important combinatoric objects. We find a recurrence formula satisfied by the number of all non-crossing linked partitions of type B with block number 2k on [±n]. Its doubly-generating function is also obtained. Keywordsnon-crossing linked partition of type B; recurrence formula; doubly-generating function 收稿日期:2016-02-29 作者簡(jiǎn)介:崔漢哲(1980-),男,講師,博士,主要研究方向?yàn)榉汉治龊徒M合數(shù)學(xué),E-mail: cuihz@sdju.edu.cn 文章編號(hào)2095-0020(2016)02-0121-04 中圖分類號(hào)O 157.1 文獻(xiàn)標(biāo)識(shí)碼A