分层排列上长度2网格模式（mesh patterns）的等分布分类、分布公式与经典排列统计量细化

《Discrete Mathematics》：Equidistribution of mesh patterns of short length on layered permutations

　　

研究人员研究长度为2的网格模式（mesh patterns）在分层排列（layered permutations）上的分布，扩展了近期关于网格模式在任意排列上分布的工作。研究人员将所有长度为2的网格模式划分为恰好35个等分布类（equidistribution classes），并推导出每一类的分布公式。除一个例外外，相应的避免序列（avoidance sequences）均出现在整数序列在线百科全书（OEIS）中，揭示了其与Fibonacci数、Tribonacci数、某些整数组合（integer compositions）以及受限字（restricted words）的联系。研究人员还通过联合追踪五个经典排列统计量——下降（descents）、左至右极大值与极小值（left-to-right maxima and minima）以及右至左极大值与极小值（right-to-left maxima and minima）——细化了若干枚举结果。

研究背景方面，网格模式（mesh patterns）由Br?ndén与Claesson引入，用于将若干排列统计量展开为经典排列模式的线性组合；Kitaev与Zhang随后系统研究网格模式在排列上的分布，另有多项工作讨论其分布与等分布。已有研究对任意排列上长度为2的网格模式等分布类作出近乎完整的分类，类数介于105与108之间并猜测为105。分层排列（layered permutations）由若干递减层直接和构成，是排列模式研究中被广泛讨论的对象，但长度为2的网格模式在分层排列上的等分布分类与分布公式此前尚未得到完整处理。因此，研究人员开展本项研究，目标是在分层排列上分类所有长度为2的网格模式，给出每个等分布类的分布公式，识别相应避免序列，并通过经典排列统计量细化枚举结果。

研究人员开展的核心研究是将分层排列的层分解、生成函数（generating function, g.f.）、函数方程、递推、显式双射以及补（complement）、逆（inverse）、反（reverse）等对称操作结合，对长度为2的网格模式进行分类与计数；结论是分层排列上长度为2的网格模式恰有35个等分布类，并为每一类给出分布结果，除一个例外外相应避免序列可在OEIS中识别，且若干结果可由五个经典排列统计量联合细化。其重要意义在于给出了该设定下完整而不可冗余的等分布分类，建立了与Fibonacci数、Tribonacci数、整数组合及受限字等组合对象的联系，并推进了网格模式分布与分层排列计数的研究。

关键技术方法概括（不超过250字）：研究人员主要采用分层排列的唯一层分解与层权重生成函数方法，将网格模式出现条件转化为对层大小、单例层及相邻层的局部约束；利用补、逆、反等基本对称操作以及关于12、21型模式中若干方格不影响计数的事实，合并平凡等价类；对每类选取代表模式，通过表4、表5所列局部观察建立递推或函数方程，求解普通生成函数；用附录中有限n的多项式比较验证不同类之间的区分性；细化部分引入多变量生成函数，联合追踪下降、左至右极大/极小值、右至左极大/极小值，并用有限状态转移矩阵a(I?M)^?1b处理依赖前一层状态的情形。本文未涉及样本队列来源。

研究结果按原文小标题概括如下。Theorem 3.1 Class 1：该类的任一模式在分层排列中至多出现一次，n≥1时s_n,1=n?1、s_n,0=2^n?1?n+1，并得相应生成函数。Theorem 3.2 Class 2：n≥2时恰含一次的模式计数为2^n?2，避免计数为2^n?1?2^n?2，由删除特定单例层与L_n?1建立双射。Theorem 3.3 Class 3：按首层长度分解得生成函数，避免序列满足a_n=2a_n?1?a_n?2+a_n?3并解释为避开部分2的整数组合。Theorem 3.4 Class 4：通过末层是否为单例建立函数方程，得到有理生成函数；避免类对应Fibonacci数，解释为除末层外无单例层的分层排列。Theorem 3.5 Class 5：若首层大小为1则出现次数为|π|?1，否则为0，由此得生成函数。Theorem 3.6 Class 6：固定首层大小k后，右侧每个单例层贡献k次出现，非单例层不贡献，得求和型生成函数。Theorem 3.7 Class 7：仅两层分层排列可含该类模式，层大小(i,j)时出现ij次，得相应生成函数。Theorem 3.8 Class 8：由首层及右侧元素计数得生成函数，并证明该类另一代表模式等分布。Theorem 3.9 Class 9：两层情形出现次数为?₁?₂，另一代表为?₁?_m，通过交换第二层与末层构造等分布，得求和公式。Theorem 3.10 Class 10：首层每个元素与右侧各层最小元形成出现，得含1/(1?t?tq^k)型项的生成函数。Theorem 3.11 Class 11：任意至少两层的分层排列恰含一次，单层排列避免，故s_n,1=2^n?1?1。Theorem 3.12 Class 12：每个非单例层贡献一次，首层大小1与至少2的情形分别加权，得有理生成函数。Theorem 3.13 Class 13：出现次数等于相邻层大小乘积之和∑?_i?_i+1，对整数组合求和得生成函数。Theorem 3.14 Class 14：首层每个元素与右侧所有元素形成出现，若首层大小k、右侧总长s则出现ks次，得求和型生成函数。Theorem 3.15 Class 15：该类模式仅在n=2的特定排列中发生一次，其余情形均避免。Theorem 3.16 Class 16：n≥3时恰含一次计数为2^n?3，避免计数为3·2^n?3，相关序列对应受限字解释。Theorem 3.17 Class 17：n≥2时仅一个分层排列含一次出现，故s_n,1=1、s_n,0=2^n?1?1。Theorem 3.18 Class 18：三个代表模式的出现数分别为?₂、?₁、?_m，在至少两层排列上同分布，得生成函数。Theorem 3.19 Class 19：通过逐项构造分层排列，区分加入最右层与开启新层，得生成函数(1?tq)/(1?t(1+q))。Theorem 3.20 Class 20：出现由连续单例层形成，分解为三类块得生成函数；避免类对应Tribonacci数，解释为无连续两个单例层的分层排列。Theorem 3.21 Class 21：首层为单例时，其元素与后续单例层形成出现，后续非单例层不贡献，得生成函数。Theorem 3.22 Class 22：n≥2时仅层大小(1,n?1)的排列含n?1次出现，其余避免，并证明其他代表等分布。Theorem 3.23 Class 23：首层为单例，其元素与每个后续层末元形成出现，得生成函数。Theorem 3.24 Class 24：四个代表模式的出现数分别化为?₂、?₁、?₁?1、?_m?1，证明同分布并得生成函数。Theorem 3.25 Class 25：出现数等于非末单例层数，另一代表对应非首单例层数，由层序反转建立等分布；避免类与Fibonacci数相关。Theorem 3.26 Class 26：仅两层排列可发生，且每个首层元素与第二层最大元形成一次，按两层情形与至少三层情形分解得生成函数。Theorem 3.27 Class 27：该类分布对应分层排列上的逆序数分布，得F(t,q)=1/(1?∑_k≥1q^C(k,2)t^k)。Theorem 3.28 Class 28：出现数等于层对数C(k,2)，其中k为非空层数，按切点选择得生成函数∑q^C(k,2)(t/(1?t))^k。Theorem 3.29 Class 29：该类给出非逆序型统计，出现数为∑<sub>i?i?j，对整数组合求和得生成函数及递推式。Theorem 3.30 Class 30：出现数等于单例层数k的二项式C(k,2)，用非单例层块生成函数B(t)得求和公式；避免序列对应至多一个1的整数组合。Theorem 3.31 Class 31：仅单层递减排列含该类出现，出现数为C(n,2)，其余至少两层排列避免，得生成函数。Theorem 3.32 Class 32：出现数等于首层大小?1的二项式C(?1,2)，右侧为任意分层排列，得生成函数。Theorem 3.33 Class 34：按无单例层与含k个单例层的块分解得乘积型生成函数；无单例层避免类与Fibonacci数相关。Theorem 3.34 Class 33：将Class 34块分解中非单例层权重由每元素tqⁱ改为除最大元外仅计t，得乘积型生成函数。Theorem 3.35 Class 35：出现数为∑j=2^m(j?1)?j，通过递推F(t,q)=1+t/(1?t)F(tq,q)迭代得含q-阶乘型分母的生成函数；避免序列为平凡序列。

讨论部分主要在第4节。4.1 Refined layer weights：研究人员先给出所有分层排列关于五个经典统计量的多变量生成函数L(t,d,x,y,u,v)，作为后续细化结果的基准。4.2 A finite-state method and representative examples：通过给每层附加q权重记录新增出现，当前层贡献若仅依赖有限状态，则用行向量、转移矩阵和列向量表示，至少两层排列的贡献写成a(I?M)^?1b；文中以Class 1、Class 9、Class 4、Class 14为例给出细化生成函数。4.3 Consistency checks and the remaining classes：将多变量生成函数特殊化可恢复未细化公式，令q=1可恢复全部分层排列的基准生成函数；其余类可按同样程序处理。研究结论可译为：研究人员将分层排列上所有长度为2的网格模式完整分类为35个等分布类，并给出每一类的分布公式；除一个例外外，相应避免序列均出现在OEIS中，揭示了其与Fibonacci数、Tribonacci数、某些整数组合及受限字的联系；同时通过联合追踪下降、左至右极大值与极小值、右至左极大值与极小值这五个经典排列统计量，细化了若干枚举结果。</sub>