B型非交错连接分拆及其计数

崔汉哲

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



B型非交错连接分拆及其计数

崔汉哲

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

摘要:连接分拆与非交错连接分拆是一类重要的组合研究对象。将A型非交错连接分拆推广到B型，针对[±n]的所有B型非交错连接分拆组成的集合NCL(B)(n)，找到了其基数fspan满足的递推公式，并得到其生成函数。

关键词:B型连接分拆； B型非交错连接分拆； 生成函数

1997年，Reiner[1]在研究超平面配置时，根据Coxeter群的3类无穷族——A、B、D型，相应提出了3种类型的非交错分拆。传统的非交错分拆为A型。受此启发，近20年来，组合学研究者将许多传统的A型组合对象推广为B型与D型，进而研究它们的各种组合性质,如B型分拆[2-3]、圆环上的B型与D型非交错分拆[4]、B型结合多面体[5]、B型置换表[6-7]等。这方面的综述可参见文献[8]。

连接分拆与非交错连接分拆是在非交换概率论的研究中起重要作用的一类组合对象[9-11],其本身具有丰富的性质。不同学者已经研究了它的计数性质[12]、代数结构[13]以及与其他一些组合对象的联系[14]。本文将把传统的A型非交错连接分拆推广为B型，并以生成函数的形式给出它的一些计数结果。

1定义与引理

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

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

连接分拆与非交错连接分拆的定义见文献[13]中的定义2与3，本文不再赘述。[n]的所有连接分拆组成的集合记为LP(n)，[n]的所有非交错连接分拆组成的集合记为NCL(n)。

定义1[±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

注1定义1中的条件(2)表明B型组合对象的对称性，条件(3)则与文献[1]中的B型分拆的定义保持一致，条件(1)与条件(4)是容易理解的。

注2对于B型非交错连接分拆，可将定义1中的条件(3)略去。因为易知这是非交错条件的一个自然推论。

例{{1,2,-1,-2},{2,3},{-2,-3}}∈NCL(B)(3)，而

{{1,2,-1,-2},{2,-3},{-2,3}}∈

LP(3)(3)NCL(B)(3)

本文给出B型非交错连接分拆的几个简单性质。

性质1对于π∈LP(B)(n)，p∈[±n]，则p在π中为单覆盖或双重覆盖。且

(1)p在π中为单覆盖⟺-p在π中为单覆盖⟺absp在absπ中为单覆盖；

(2)p在π中为双重覆盖⟺-p在π中为双重覆盖⟺absp在absπ中为双重覆盖。

证明由定义1易知，p在π中为单(双重)覆盖⟺-p在π中为单(双重)覆盖。因此，只需证明p在π中为单覆盖或双重覆盖以及p在π中为单覆盖⟺absp在absπ中为单覆盖即可。

(1) 证明p在π中为单覆盖或双重覆盖。用反证法。假设存在不同分块A,B,C∈π，且满足p∈A，p∈B，p∈C，则有

absp∈absA，absp∈absB，absp∈absC

absA∈absπ，absB∈absπ

absC∈absπ，absπ∈LP(n)

由LP(n)的定义(见文献[13]中的定义2)，可知absp在absπ中为单覆盖或双重覆盖。因此，不妨设absA=absB。由于A、B为π中不同分块，故由定义1可知

A=-B且A∩B=∅

但这与p∈A∩B矛盾。

(2) 若p在π中被分块A单覆盖，则在absπ中absp显然被分块absA单覆盖。反之，设absp在absπ中被分块E单覆盖。若π中存在分块F满足F∩-F=∅且absF=abs-F=E，则在π中p被F或-F单覆盖同时p被-F或F单覆盖)。若π中存在零分块F满足absF=E，则在π中p与-p均被F单覆盖。这样便证明了p在π中为单覆盖⟺absp在absπ中为单覆盖。证毕。

由性质1以及LP(n)的定义(见文献[13]中的定义2)还可得以下推论。

性质2±1,±n在π∈LP(B)(n)中均为单覆盖。

性质3若π∈NCL(B)(n)，则absπ∈NCL(n)。

证明由NCL(B)(n)⊆LP(B)(n)，有absπ∈LP(n)，故只需证明absπ满足非交错条件即可。用反证法。

设1≤a

证毕。

以下引理总结了文献[9,12]中关于NCL(n)的一些计数结果。在定理的证明中将会用到。

引理1设n∈N，记sn∶=|NCL(n)|，则sn恰为第n-1个大Schroder数(the(n-1)th large schroder number)[15-16]。若记sn的生成函数为

则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

注意此处的生成函数S(x)与文献[12]中略有不同，因此，S(x)满足的方程以及方程的解已是改写后的结果。

2定理及其证明

定理1设n∈N，记

则

(3)

式中，fn满足的递推关系为f1=2，f2=6；当n≥3时，

(4)

这里的S(x)、sn见引理1。

证明f1=2，f2=6易得。设π∈NCL(B)(n)且n≥3。将元素-n所在分块记为V，考虑在[±n]的全序之下V中的最小元，记为v。分以下6种情况讨论。

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

情况3v=-1。此时n∈-V且V(-V)不为零分块。由非交错条件与性质2可知，π|{1,2,…,n-1}可以是集合{σ∈NCL(n)|1～n}≌NCL(n-1)中任意元素，再由对称性即得π的个数为sn-1。

反之，对于{1,2,…,v}的一个非交错连接分拆π1，以及满足v～π2-n(-v～π2n)的{v,v+1,…,n,-v,-v-1,…,-n}上的一个B型非交错连接分拆π2，可以相应得到[±n]的B型非交错连接分拆π，且满足-n所在分块在[±n]的全序之下的最小元为v。具体构造如下：

于是可知π的个数为s2fn-2+s3fn-3+…+sn-1f1。

于是，情况6中π的个数为

sn-2(f2-s2)+sn-3(f3-s3)+…+

s1(fn-1-sn-1)

(5)

综合上述6种情况，可得n≥3时，fn的递推式为

（1）技术人员年龄结构偏大据统计在我国县乡畜牧兽医技术推广服务体系中，年龄在35岁以下的占28%，36-45岁的占 31%，46-60岁的占41%，年龄结构趋于老化。

式为

fn=2fn-1+2sn-1+(s2fn-2+s3fn-3+…+sn-1f1)+

sn-2(f2-s2)+sn-3(f3-s3)+…+

s1(fn-1-sn-1)

(6)

结合s1=1与s2=3，式(6)改写为

fn=fn-1+sn-1+2(s1fn-1+s2fn-2+…+

sn-1f1)-(s1sn-1+s2sn-2+…+sn-1s1)

再利用sn的递推式，得fn的生成函数为

2x+6x2+x[F(x)-2x]+x[S(x)-x]+

2[S(x)F(x)-2x2]-[S2(x)-x2]

(7)

将引理1中式(1)代入式(7)，整理可得

F(x)=[3x+(2x-1)S(x)]/[1-x-2S(x)]

(8)

最后，将引理1中的式(2)代入式(8)，即得

证毕。

参考文献：

[1]Reiner V.Non-crossing partitions for classical reflection groups[J].Discrete Mathematics,1997,177(1/3)： 195-222.

[2]Chen W Y C,Wang D G L.Minimally intersecting set partitions of type B[J].The Electronic Journal of Combinatorics,2010,17(1)： R22.

[3]Chen W Y C,Wang D G L.Singletons and adjacencies of set partitions of type B[J].Discrete Mathematics,2011,311(6)： 418-422.

[4]Nica A,Oancea I.Posets of annular non-crossing partitions of types B and D[J].Discrete Mathematics,2009,309(6)： 1443-1466.

[5]Simion R.A type-B associahedron[J].Advances in Applied Mathematics,2003,30(1/2)： 2-25.

[6]Corteel S,Kim J S.Combinatorics on permutation tableaux of type A and type B[J].European Journal of Combinatorics,2011,32(4)： 563-579.

[7]Corteel S,Josuat-Verges M,Kim J S.Combinatorics of the permutation tableaux of type B[J].arXiv,2012： 1203.0154.

[8]Armstrong D.Generalized noncrossing partitions and combinatorics of Coxeter groups[M].[S.L.]： American Mathematical Society,2009： 81-115.

[9]Dykema K J.Multilinear function series and transforms in free probability theory[J].Advances in Mathematics,2007,208(1)： 351-407.

[10]Popa M.Non-crossing linked partitions and multiplication of free random variables[J].arXiv,2008： 0812.2064.

[11]Nica A.Non-crossing linked partitions,the partial order on NC(n), and the S-transform[J].Proceedings of the American Mathematical Society,2010,138(4)： 1273-1285.

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

[13]崔汉哲.非交错连接分拆的等价描述[J].上海电机学院学报，2012，15(6)： 409-413.

[14]Chen W Y C,Wang C J.Noncrossing linked partitions and large(3,2)-Motzkin paths[J].Discrete Mathematics,2012,312(11)： 1918-1922.

[15]Stanley R P.Enumerative combinatorics.Vol.2[M].[S.L]:Cambridge University Press,1999: 178,219.

[16]Sloane N J.The On-Line Encyclopedia of Integer Sequences (OEIS)[EB/OL].(2014-12-15).http:∥oeis.org.

Type B Non-Crossing Linked Partition and Enumeration

CUIHanzhe

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

Abstract:Both linked partitions and non-crossing linked partitions are important combinational objects. We extend non-crossing linked partitions of type A to those of type B, and find the recurrence formula satisfied by cardinal number of the set which consists of all non-crossing linked partitions of type B on [±n]. Its generating function is also obtained.

Key words:type B linked partition; non-crossing linked partition of type B; generating function

文献标志码:A

中图分类号:O 157.1

文章编号2095 - 0020(2015)01 -0042 - 04

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

收稿日期：2015 - 01 - 08