B型非交错连接分拆的一个计数结果

崔汉哲

(上海电机学院 数理教学部, 上海 201306)

B型非交错连接分拆的一个计数结果

崔汉哲

(上海电机学院 数理教学部, 上海 201306)

摘要连接分拆与非交错连接分拆是组合数学中的重要研究对象。以递推式的形式计算集合[±n]上分块个数为给定偶数2k的所有B型非交错连接分拆的数目，并得到其双重生成函数。

关键词B型非交错连接分拆; 递推式; 双重生成函数

连接分拆(linked partitions)与非交错连接分拆(non-crossing linked partitions)是组合数学中的一类重要研究对象，最早在算子代数的研究中被发现。它们在计算经典非交换概率论中T—变换的形式幂级数系数时起到了重要作用[1]，在非交换概率论的其他方面也有广泛应用[2-6]。与此同时，不同学者从组合数学的多个角度也探究了它们作为组合对象的丰富性质，如计数性质[7]、代数结构[8]、与其他组合对象的联系[9-13]等。

另一方面，文献[14]中从一类和组合数学有密切关系的重要代数结构——Coxeter群的分类角度出发，定义了一大类组合对象的A、B和D型。根据此观点，文献[15]中将传统的A型非交错连接分拆推广到B型，研究了它们的基本性质并得到一些基本的计数结果，即计算了集合[±n]={1，2，…，n，-1，-2，…，-n}上所有B型非交错连接分拆的个数。在此基础上，本文进一步考虑如下问题： 对于集合[±n]上的B型非交错连接分拆，在分块个数为给定正整数的情况下，它们的个数是多少？记[±n]上所有分块个数为偶数2k的B型非交错连接分拆的个数为a(n，k)，本文将给出a(n，k)满足的递推式及其双重生成函数的具体表达式。

1定义与引理

集合{1，2，…，n，-1，-2，…，-n}在偏序关系1<2<…

对于a∈Z，定义绝对值映射abs∶Z→N为absa∶=|a|。对于Z的子集V，记-V为将V中所有元素取相反数得到的集合，记absV为将V中所有元素取绝对值得到的集合。若集合π以Z的若干子集为元素，则定义-π为{-V|V∈π}，absπ为{absV|V∈π}。

连接分拆与非交错连接分拆的定义见文献[8]中的定义2、3，本文不再赘述。[n]的所有连接分拆组成的集合记为LP(n)。[n]的所有非交错连接分拆组成的集合记为NCL(n)。为叙述完整，本文先给出B型连接分拆和B型非交错连接分拆的定义。

定义1[15][±n]的一个B型连接分拆(linked partition of type B)是指以[±n]的若干子集为元素的集合π，且满足以下条件：

(1) 这些子集的并为[±n]；

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

(3)π中至多有一个元素W满足W=-W，此时称W为π的零分块；

(4) absπ∈LP(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

以下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)。

对于π∈NCL(B)(n)，其分块个数有两种情况： ①π包含零分块，其分块个数为奇数；②π不包含零分块，其分块个数为偶数。本文考虑π不包含零分块的情形。

以下引理总结了文献[7]中关于NCL(n)相应的计数结果，在定理的证明中将会用到。

引理1记b(n，k)为NCL(n)中分块个数为k(1≤k≤n)的元素个数，其双重生成函数为

则

(1+x-t x)B2(x，t)+

(x-1)B(x，t)+x t=0

(1)

由此可解得

B(x，t)=

(2)

注： 此处的生成函数B(x，t)与文献[7]中的定义略有不同，本文省略了常数项，故B(x，t)满足的方程与最后的解是改写后的结果。

2定理及其证明

定理1记a(n，k)为NCL(B)(n)中分块个数为2k的元素个数，其双重生成函数为

则

(3)

其中，B(x，t)见引理1。

证明先推导a(n，k)的递推式，再由此解出双重生成函数。

根据定义容易得到如下边界条件： 当k>n时，

a(n，k)=b(n，k)=0

a(n，n)=1

此时的π∈NCL(B)(n)只有一种可能，即由2n个单点块组成。

为方便本文推导，再令

a(n，0)=b(n，0)=0

另外，当π∈NCL(B)(n)的分块个数为2时，有π={{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。

以下设n≥3，k≥2，π∈NCL(B)(n)且分块个数为2k(1≤k≤n)。将π中-n所在分块记为V，考虑在[±n]的全序之下的V中最小元，记为v，以下分6种情况讨论。

(1)v=-n，即{n}与{-n}同时为单点块。由性质2可见，n与-n在π中均为单覆盖。于是，将π限制到[±(n-1)]可以是NCL(B)(n-1)中的任意元素，且分块个数为2(k-1)。故此时π的个数为

K=a(n-1，k-1)

(4)

(2)v=n即{n，-n}为π中的零分块。此时π中分块个数应为奇数，与题设矛盾。因此，该情况不出现，无需讨论。

K=b(n-1，k)

(5)

(4)v=1。此时，π∈{σ∈NCL(B)(n)|1～-n(-1～n)}≅NCL(B)(n-1)且分块个数为2k，因此，π的个数为

K=a(n-1，k)

(6)

(5)v∈{2，3，…，n-1}。将v记成i，分以下两种情形讨论。

①i在π中为单覆盖。此时由非交错条件可知

(7)

b(i-1，k-u-1)]

(8)

综合上述两种情形，情况5中π的总个数为

b(i，k-u)-b(i-1，k-u-1)]

(9)

(6)v∈{-2，-3，…，1-n}。将v记成i，类似情况5，也分以下2种情形讨论。

①i在π中为单覆盖。此时由非交错条件可知

(10)

a(i-1，k-u-1)]

(11)

综合上述两种情形，情况6中π的总个数为

a(i，k-u)-a(i-1，k-u-1)]

(12)

综合上述6种情况，得到n≥3，k≥2时，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)

通过变换下标，结合定理证明的边界条件和初值条件，可将式(13)等号右侧第4、5项的双重和式简单变形为

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)可解出

证毕。

参考文献

[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]崔汉哲.非交错连接分拆的等价描述[J].上海电机学院学报，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型非交错连接分拆及其计数[J].上海电机学院学报，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

作者简介：崔汉哲(1980-)，男，讲师，博士，主要研究方向为泛函分析和组合数学，E-mail： cuihz@sdju.edu.cn

文章编号2095-0020(2016)02-0121-04

中图分类号O 157.1

文献标识码A