B型非交錯連接分拆的兩個計數結果

崔漢哲

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

B型非交錯連接分拆的兩個計數結果

崔漢哲

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

連接分拆與非交錯連接分拆是組合數學中的一類重要研究對象。對于[±n]的所有B型非交錯連接分拆組成的集合NCL(B)(n)，分別計算其中包含或不包含零分塊的元素個數。找到其滿足的遞推關系，并得出生成函數的表達式。

B型非交錯連接分拆； 零分塊； 遞推式； 生成函數

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

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

1 定義與引理

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

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

對于Z的子集V，定義

若集合π以Z的若干子集為元素，則類似定義

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

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

(1) absπ∈LP(n)；

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

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

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

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

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

以下B型連接分拆與非交錯連接分拆的幾個簡單性質見文獻[15]，在本文的證明中將要用到。

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

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

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

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

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

下文的2個引理總結了文獻[9]、[15]中關于NCL(n)與NCL(B)(n)的一些計數結果。

則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

(3)

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

引理2 設n∈N，記

則

(4)

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

(5)

2 定理、推論及其證明

定理1 設n∈N，記

則

(6)

式中，hn滿足的遞推關系：h1=1，h2=3；當n≥3時，

(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。

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

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

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

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

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

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

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

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

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

π∈NCLZ(B)(n)

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

(8)

由此可知，π的個數為s2hn-2+s3hn-3+…+sn-1h1。

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

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

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

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

反之，給定

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

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

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

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

由此可得情況(6)中π的個數為

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

綜合上述6種情況，可知n≥3時，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)

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

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

(10)

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

(11)

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

(12)

證畢。

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

推論1 設n∈N，記

則

(13)

式中，gn滿足的遞推關系為g1=1，g2=3；當n≥3時，

(14)

注記 用定理1證明中推導H(x)的方法也可以直接得到推論1的結果。g1=1、g2=3易得，然后類似定理1的證明，分6種情況討論。下文只寫出每種情況對應的元素個數K，具體過程略去。

(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滿足的遞推關系以及G(x)的表達式。

[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] 崔漢哲. 非交錯連接分拆的等價描述 [J].上海電機學院學報，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型非交錯連接分拆及其計數 [J]. 上海電機學院學報，2015，18(1)：42-45.

[16] 崔漢哲. B型非交錯連接分拆的一個計數結果 [J]. 上海電機學院學報，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-)， 男，講師，博士，主要研究方向為泛函分析和組合數學，E-mail:cuihz@sdju.edu.cn

2095 - 0020(2017)01 -0052 - 04

O 157.1

A