B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果

崔漢哲

(上海電機(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