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é)中的一類(lèi)重要研究對(duì)象。對(duì)于[±n]的所有B型非交錯(cuò)連接分拆組成的集合NCL(B)(n)，分別計(jì)算其中包含或不包含零分塊的元素個(gè)數(shù)。找到其滿(mǎn)足的遞推關(guān)系，并得出生成函數(shù)的表達(dá)式。

B型非交錯(cuò)連接分拆； 零分塊； 遞推式； 生成函數(shù)

組合數(shù)學(xué)中，連接分拆(linked partitions)與非交錯(cuò)連接分拆(noncrossing linked partitions)作為一類(lèi)重要的內(nèi)容被研究。它們最早由Dykema[1]在經(jīng)典非交換概率論的T—變換研究時(shí)引入，之后被廣泛應(yīng)用于非交換概率論的其他方面以及算子代數(shù)的研究中[2-7]。同時(shí)，不同學(xué)者從多角度研究了連接分拆與非交錯(cuò)連接分拆作為組合對(duì)象的豐富性質(zhì)，如代數(shù)結(jié)構(gòu)[8]、計(jì)數(shù)性質(zhì)、與其他組合對(duì)象的聯(lián)系[10-13]等。

另一方面，文獻(xiàn)[14]中從與組合數(shù)學(xué)有密切聯(lián)系的Coxeter群的分類(lèi)角度出發(fā)，定義了A、B和D型組合對(duì)象。在此基礎(chǔ)上，文獻(xiàn)[15]中定義了B型非交錯(cuò)連接分拆，研究了它們的基本性質(zhì)，并與文獻(xiàn)[16]共同得到了一些基本的計(jì)數(shù)結(jié)果。具體而言，文獻(xiàn)[15]中計(jì)算了集合[±n]={1,2,…,n,-1,-2,…，-n}的所有B型非交錯(cuò)連接分拆的個(gè)數(shù)。本文進(jìn)一步計(jì)算集合[±n]的B型非交錯(cuò)連接分拆中包含或不包含零分塊的元素個(gè)數(shù)。

1 定義與引理

在集合{1,2,…,n,-1,-2,…,-n}上定義全序關(guān)系1<2<…

對(duì)于a∈Z，定義絕對(duì)值映射abs∶Z→N為

對(duì)于Z的子集V，定義

若集合π以Z的若干子集為元素，則類(lèi)似定義

文獻(xiàn)[8]中的定義2、3給出了連接分拆與非交錯(cuò)連接分拆的定義，此處不贅。記[n]的所有連接分拆組成的集合為L(zhǎng)P(n)，[n]的所有非交錯(cuò)連接分拆組成的集合為NCL(n)。為敘述完整，本文先給出B型連接分拆和B型非交錯(cuò)連接分拆的定義。

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

(1) absπ∈LP(n)；

(2) 由V∈π可得-V∈π；

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

注意：由條件(1)和(2)可知，π中所有元素之并為[±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

π|S={V∩S|V∈π,V∩S≠?}

稱(chēng)其為將π限制到S后所得的連接分拆。最后，將NCL(B)(n)中所有包含零分塊的元素組成的集合記為NCLZ(B)(n)。本文目的為計(jì)算|NCLZ(B)(n)|和|NCL(B)(n)NCLZ(B)(n)|。

以下B型連接分拆與非交錯(cuò)連接分拆的幾個(gè)簡(jiǎn)單性質(zhì)見(jiàn)文獻(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)。

下文的2個(gè)引理總結(jié)了文獻(xiàn)[9]、[15]中關(guān)于NCL(n)與NCL(B)(n)的一些計(jì)數(shù)結(jié)果。

則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

(3)

注：本文中的生成函數(shù)與文獻(xiàn)[9]中稍有不同，略去了常數(shù)項(xiàng)1。因此，式(1)以及方程的解是改寫(xiě)后的結(jié)果。下同。

引理2 設(shè)n∈N，記

則

(4)

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

(5)

2 定理、推論及其證明

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

則

(6)

式中，hn滿(mǎn)足的遞推關(guān)系：h1=1，h2=3；當(dāng)n≥3時(shí)，

(7)

證明 由NCLZ(B)(1)={{{1,-1}}}可知h1=1。

由NCLZ(B)(2)={{{1,-1},{2},{-2}},{{1},{-1}{2,-2}},{{1,2,-1,-2}}}可知h2=3。

設(shè)π∈NCLZ(B)(n)且n≥3。將元素-n所在分塊記為V，將在[±n]的全序之下的V中最小元記為v。分以下6種情況討論。

(1)v=-n。此時(shí)，V={n}且{n}與{-n}同時(shí)為單點(diǎn)塊。由性質(zhì)2可知，n與-n在π中均為單覆蓋。于是，π|[±(n-1)]∈NCLZ(B)(n-1)，且π|[±(n-1)]可以是NCLZ(B)(n-1)中的任意元素，故π的個(gè)數(shù)為hn-1。

(2)v=n。此時(shí)V={n,-n}恰為π中的零分塊。由非交錯(cuò)條件可知，π|[n-1]∈NCL(n-1)，且π|[n-1]可以是NCL(n-1)中的任意元素，π的個(gè)數(shù)為sn-1。

(3)v=-1。此時(shí),n∈-V且V(-V)不為零分塊。由非交錯(cuò)條件可知，此時(shí)π中沒(méi)有零分塊，即π?NCLZ(B)(n)。由題設(shè)，此情況可略去不計(jì)。

(4)v=1。此時(shí)，π|[±(n-1)]∈NCLZ(B)(n-1)，且π|[±(n-1)]可以是NCLZ(B)(n-1)中的任意元素，故π的個(gè)數(shù)為hn-1。

(5)v∈{2,3,…,n-1}。此時(shí)，由非交錯(cuò)條件可知，π|{1,2,…,v}為NCL(v)中任意元素，而π|{v,v+1,…,n,-v,-v-1,…,-n}為{v,v+1,…,n,-v,-v-1,…,-n}上的一個(gè)包含零分塊的B型非交錯(cuò)連接分拆，且滿(mǎn)足v～-n(-v～n)，于是進(jìn)一步有

π|{v,v+1,…,n -1,- v,- v -1,…,-(n-1)}∈NCLZ(B)(n-v)

且可以是NCLZ(B)(n-v)中的任意元素。

反之，對(duì)于{1,2,…,v}的一個(gè)非交錯(cuò)連接分拆π1，以及{v,v+1,…,n,-v,-v-1,…,-n}上的一個(gè)包含零分塊的B型非交錯(cuò)連接分拆π2滿(mǎn)足v～π2(-n)(-v～π2n)，可以相應(yīng)得到

π∈NCLZ(B)(n)

且-n所在分塊在[±n]的全序之下的最小元為v。具體構(gòu)造如下：

(8)

由此可知，π的個(gè)數(shù)為s2hn-2+s3hn-3+…+sn-1h1。

(6)v∈{-2,-3,…,1-n}。此時(shí)，-v,n∈-V且V(-V)不為零分塊。由非交錯(cuò)條件可知，

π|{1,2,…,-v,-1,-2,…,v}∈NCLZ(B)(-v)

{σ∈NCLZ(B)(-v)|v～σ(-v)}

且可以是該集合中的任意元素。而π|{v,v-1,…,-n}為{v,v-1,…,-n}的非交錯(cuò)連接分拆且滿(mǎn)足v～-n，因此，π|{v,v-1,…,-n∈NCL(n+v)。

反之，給定

NCLZ(B)(-v){σ∈NCLZ(B)(-v)|v～σ(-v)}

中元素與集合{v,…,-n}上滿(mǎn)足v～-n的非交錯(cuò)連接分拆，類(lèi)似情況(5)中的構(gòu)造，可以得到滿(mǎn)足情況(6)條件的[±n]上包含零分塊的B型非交錯(cuò)分拆。而由對(duì)稱(chēng)性、非交錯(cuò)條件以及映射abs，類(lèi)似情況(2)中的討論，可知集合

{σ∈NCLZ(B)(-v)|v～σ(-v)}=

{σ∈NCL(B)(-v)|v～σ(-v)}?NCL(-v)

由此可得情況(6)中π的個(gè)數(shù)為

sn-2(h2-s2)+sn-3(h3-s3)+…+s1(hn-1-sn-1)

綜合上述6種情況，可知n≥3時(shí)，fn的遞推式如下：

hn=2hn-1+sn-1+(s2hn-2+s3hn-3+…+sn-1h1)+sn-2(h2-s2)+sn-3(h3-s3)+ …+s1(hn-1-sn-1)

(9)

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

hn=hn-1+sn-1+2(s1hn-1+s2hn-2+…+sn-1h1)-(s1sn-1+s2sn-2+…+sn-1s1)

(10)

再由生成函數(shù)的定義可將式(10)改寫(xiě)為

(11)

最后，將引理1中S(x)的已知結(jié)果代入式(11)，整理后即得

(12)

證畢。

由定理1以及引理2可直接計(jì)算NCL(B)(n)中不包含零分塊的元素個(gè)數(shù)。

推論1 設(shè)n∈N，記

則

(13)

式中，gn滿(mǎn)足的遞推關(guān)系為g1=1，g2=3；當(dāng)n≥3時(shí)，

(14)

注記 用定理1證明中推導(dǎo)H(x)的方法也可以直接得到推論1的結(jié)果。g1=1、g2=3易得，然后類(lèi)似定理1的證明，分6種情況討論。下文只寫(xiě)出每種情況對(duì)應(yīng)的元素個(gè)數(shù)K，具體過(guò)程略去。

(1)K=gn-1；

(2)K=0；

(3)K=sn-1；

(4)K=gn-1；

(5)K=s2gn-2+s3gn-3+…+sn-1g1；

(6)K=g2sn-2+g3sn-3+…+gn-1s1。

由此，同樣可得gn滿(mǎn)足的遞推關(guān)系以及G(x)的表達(dá)式。

[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 Communication in Probability, 2012, 17(5):489-500.

[6] POPA M. A Fock space model for addition and multiplication of c-free random variables [J].Proceed-ings of the American Mathematical Society, 2014, 142(6): 2001-2012.

[7] POPA M, VINNIKOV V, WANG J C. On the multiplication of operator-valued c-free random variables [J].arXiv,2015:1509.08853.

[8] 崔漢哲. 非交錯(cuò)連接分拆的等價(jià)描述 [J].上海電機(jī)學(xué)院學(xué)報(bào)，2012，15(6)：409-413.

[9] 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.

[10] CHEN W Y C, WANG C J. Noncrossing linked partitions and large (3, 2)-Motzkin paths [J].Dis-crete Mathematics, 2012, 312(11): 1918-1922.

[11] CHEN W Y C, LIU L H, WANG C J. Linked partitions and permutation tableaux[J].arXiv, 2013,1305.5357

[12] CHEN W Y C, GUO P L, PANG S X M. Vacillat-ing Hecke tableaux and linked partitions [J]. Mathematische Zeitschrift, 2015, 281(3): 661-672.

[13] YAN S H F, ZHOU R. Refined enumeration of corners in tree-like tableaux[J]. arXiv,2017:1701.07216.

[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.

[16] 崔漢哲. B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果 [J]. 上海電機(jī)學(xué)院學(xué)報(bào)，2016，19(2)：121-124.

[17] STANLEY R P. Enumerative combinatorics[J]. Cambridge Studies in Advanced Mathematics. 1999,62(2)：178，291.

[18] SLOANE N J. The on-line encyclopedia of integer sequences (OEIS) [EB/OL]. [2016-08-26].http://oeis.org/search?q=A006138&language=english &go=Search.

Two Enumerative Results for Noncrossing Linked Partitions of Type B

CUIHanzhe

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

Linked partitions and non-crossing linked partitions are both important combinatoric objects. We calculate the cardinal numbers of the sets that consist of non-crossing linked partitions of type B on [±n] with or without zero blocks. Their recurrence formulas and generating functions are obtained.

noncrossing linked partitions of type B; zero block; recurrence formula; generating functions

2016 -12 -25

崔漢哲(1980-)， 男，講師，博士，主要研究方向?yàn)榉汉治龊徒M合數(shù)學(xué)，E-mail:cuihz@sdju.edu.cn

2095 - 0020(2017)01 -0052 - 04

O 157.1

A