关于n元对称群上的有禁排列计数研究

Research on Enumeration of Pattern-Avoiding Permutations on N-Element Symmetric Group

摘要: 有禁排列计数问题是计数组合学中的热点问题，在物理、化学、计算机等学科中有着广泛应用。本文在Kitaev的综述书籍基础上，对n元对称群Sn上有禁排列计数的经典结果进行了总结，并介绍相关研究成果。

Abstract: The enumeration of pattern-avoiding permutations is a hot topic in enumeration combinatorics and has wide applications in physics, chemistry and computer science. Based on Kitaev’s review book, this paper summarizes the classical results of the enumeration of pattern-avoiding permutations n-element symmetric group Sn, and introduces the related research results.

1. 引言

排列集上模式问题的研究有悠久的历史。19世纪八十年代，MacMahon [1] 在组合对象研究中使用生成函数方法给出了排列和词中逆序数的分布，即现代观点下的21模式问题。在20世纪七十年代和八十年代早期，Knuth [2] ，Rotem [3] 和Rogers [4] 对排列与词中的模式问题进行了研究，Simion和Schimdt [5] 首次对模式问题进行了系统的研究。

现今关于排列中模式的研究是一个活跃的领域，已经产生了丰富的工具来研究关于模式的各类问题，相关结果综述参见Kitaev的著作 [6] 。排列中模式的概念已成为众多领域中的重要工具语言，如Kazhdan-Lusztig的多项式理论、Schubert簇的奇异点、Chebyshev多项式、Ferrer的rook多项式以及多种分类算法。此外，排列中模式的研究也经常被运用于计算生物学与理论物理学中。

记n元对称群 $S_n$ 为从1到n的连续正整数排列全体所组成的集合，如 $S_1=\left\{1\right\}$ ， $S_2=\left\{12,21\right\}$ ， $S_3=\left\{123,132,213,231,312,321\right\}$ 。我们称排列w中去掉若干字母得到的排列为w的子列，由连续字母组成的子列称为w的因子。如排列123245321的子列有324532、232321等，前者也是排列123245321的因子。

对排列w的子列 $\sigma =w_{i_1}{w}_{i_2}\cdots w_{i_r}$ 中的字母进行排序，最小的用1代替，然后去掉这个字母继续排序，最小的用2代替，这样一直进行下去可得到子列的简化形式 $red\left(\sigma \right)$ ，如 $red\left(453\right)=231$ 。对给定的 $k\left(k\le n\right)$ 元排列 $\tau$ ，排列 $w\in S_n$ 且w所有子列的简化形式都不等于 $\tau$ ，这样的w全体组成的集合记作 $S_n$ 上的有禁排列集 $S_n\left(\tau \right)$ ， $S_n\left(\tau \right)$ 中的元素称为是避免模式 $\tau$ 的。如 $S_4\left(123\right)=\{1432,2143,2413,2431,3142,3214,3241,3412,3421,4132,4213,4231,4312,4321\}$ 。

在对排列的研究过程中产生了大量有趣的组合双射问题。对于给定的正整数n，如果集合 $S_n\left(\sigma \right)$ 中的元素个数等于集合 $S_n\left(\tau \right)$ 中元素个数，我们称两个模式 $\sigma$ 和 $\tau$ 在 $S_n$ 上是Wilf-等价的。近年来，有众多文献研究模式的Wilf-等价性 [7] [8] [9] ，以及如何用组合双射来证明这些等价类，也有大量文献给出其他组合对象，如偏序集、格路径、平面图、有序树与避免某种模式的排列有相同的计数结果 [10] [11] 。

2. 避免3长模式的计数结果

根据递推关系的一致性，可以证明 $S_n\left(231\right)$ 的计数结果是经典的Catalan数 $C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$ 。通过对

模式231进行翻转和互补(将i替换为 $n-i$ ， $i=1,2,\cdots ,n$ )可以证明 $\left\{132,231,213,312\right\}$ 在 $S_n$ 上是Wilf-等价的，这一方法也能证明 $\left\{123,231\right\}$ 在 $S_n$ 上是Wilf-等价的。MacMahon [2] 得出 $S_n$ 上避免这六种模式的计数结果都是Catalan数 $C_n$ ，但 $\left\{132,231,213,312\right\}$ 和 $\left\{123,231\right\}$ 这两类模式之间的Wilf-等价性不容易进行双射证明。

在构造这两类排列之间双射的过程中，Dyck路成为重要的辅助工具。 $S_n\left(132\right)$ 和n长Dyck路之间有一个标准的双射，由此Knuth [3] 和Rotem [4] 及Krattenthaler [12] 分别利用Dyck路作为中间桥梁，建立了 $S_n\left(321\right)$ 到 $S_n\left(132\right)$ 和 $S_n\left(123\right)$ 到 $S_n\left(321\right)$ 之间的双射。除了利用Dyck路，Mansour，Deng和Du [13] 使用正则约化分解，构造了 $S_n\left(321\right)$ 到 $S_n\left(231\right)$ 之间的双射。受计算机思想启发的算法也是学者们构造双射的重要工具。Simion和Schmidt [5] 使用算法构造了 $S_n\left(123\right)$ 到 $S_n\left(132\right)$ 的双射，称为Simion-Schmidt双射。Richards [14] 使用算法构造了Dyck路到 $S_n\left(123\right)$ 的双射，与标准双射复合即得到 $S_n\left(321\right)$ 到 $S_n\left(132\right)$ 的双射，称为Knuth-Richards双射。还有学者通过与其他组合结构构造双射，如West [15] 利用生成树建立了 $S_n\left(123\right)$ 到 $S_n\left(132\right)$ 之间的双射，Reifegerste [16] 利用矩阵变换建立了 $S_n\left(321\right)$ 到 $S_n\left(132\right)$ 之间的双射，Claesson和Kitaev [17] 详细列出了这些双射之间的联系以及相关组合统计量的分布规律。

对于 $S_n$ 中避免两个及以上的3长模式，Simion和Schmidt [5] 给出了 $S_n\left(123,132\right)$ 、 $S_n\left(123,132,213\right)$ 等有禁排列集的计数结论。

3. 避免4长模式的计数结果

在 $S_n$ 上4长模式的Wilf-等价性研究也有丰富的成果。避免单个4长模式的排列上有3个Wilf-等价类，Bóna [18] 得到了 $S_n\left(1342\right)$ 的生成函数，Regev [19] 得到了 $S_n\left(1234\right)$ 的生成函数，对于剩下的Wilf类中 $S_n\left(1324\right)$ 的计数问题仍然是该领域的一个重要的开放问题。Backelin，West和Xin [20] 证明了 $\left\{1243,2143\right\}$ 两个模式的等价性，经过翻转和互补可得 $\left\{1234,1243\right\}$ 等价。Stankova在两个文献中 [21] [22] 分别证明了 $\left\{1342,2413\right\}$ 和 $\left\{1234,3214\right\}$ 等价，完成了单个4长模式的等价类分类工作。Gessel [23] 和Bóna [18] 给出了这些等价类的计数结果。

同时避免一个3长和一个4长模式的排列中，Erdös和Szekeres [24] 给出了 $S_n\left(123,4321\right)$ 的计数结果。Billey，Jockusch和Stanley [25] 得到 $S_n\left(123,3412\right)$ 的计数结果。West [26] 使用生成树方法解决了所有“3 + 4”计数问题，其中大部分计数结果和斐波那契数列相关。Tenner [27] 证明了带布尔主序理想的排列集恰好是 $S_n\left(321,3412\right)$ ，故这类排列也称为布尔排列。

同时避免2个4长模式的排列上有56个对称类，Le [28] 建立了38个Wilf-等价类。Kremer [29] 证明了10种避免两个4长模式的排列的计数结果与Schröder数相关，其中 $S_n\left(1243,2143\right)$ 被Egge和Mansour [30] 称为Schröder排列。

下面介绍避免两个4长模式的计数结果。对于模式集A，用 $s_n\left(A\right)$ 表示 $S_n$ 中避免A中模式的排列数量，Kremer和Shiu [31] 使用有限转移矩阵得到如下结果：

定理1.

$s_n\left(1234,3214\right)=s_n\left(4123,3214\right)=s_n\left(2341,2143\right)=s_n\left(1234,2143\right)=\frac{1}{3}\left(4^{n-1}+2\right)$ .

Stankova [21] 证明了 $S_n\left(2143,3412\right)$ 是Skew-merged排列，即由一个递增子列和一个递减子列合并而成的排列。Atkinson [32] 由下面定理给出了计数结果。

定理2.

$s_n\left(2143,3412\right)=\left(\begin{array}{c}2n\\ n\end{array}\right)-{\displaystyle {\sum }_{m=0}^{n-1}{2}^{n-m-1}\left(\begin{array}{c}2m\\ m\end{array}\right)}$ ，

相应的生成函数为

${\displaystyle {\sum }_{n\ge 0}{s}_n\left(2143,3412\right)x^n}=\frac{1-3x}{\left(1-2x\right)\sqrt{1-4x}}$ .

对于 $n\to \infty$ ，有

$\frac{s_n\left(2143,3412\right)}{\left(\begin{array}{c}2n\\ n\end{array}\right)}\to \frac{1}{2}$ .

此外，Miner [33] 计算了等价类 $\left\{4123,1324\right\}$ 、 $\left\{4123,1243\right\}$ 、 $\{4123,1342\}$ 的生成函数。Miner和Pantone [34] 研究了最后两个Wilf-等价类 $\left\{2413,3412\right\}$ 和 $\left\{3412,4123\right\}$ 。Callan，Mansour和Shattuck [35] [36] 得到避免3个4长模式的排列上有242个Wilf-等价类。Mansour [37] 给出了 $S_n\left(1324,2134,1243\right)$ (称为极大偏序排列)的计数结果如下：

定理3.

${\displaystyle {\sum }_{n\ge 0}{s}_n\left(1324,2134,1243\right)x^n}=\frac{2-C\left(x\right)}{2-x-C\left(x\right)}$ ，

其中 $C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x}$ 。

$s_n\left(1324,2134,1243\right)=P_{5n}-4P_{5\left(n-1\right)}+2P_{5\left(n-2\right)}-{\displaystyle {\sum }_{j=0}^{n-2}{C}_j{P}_{5\left(n-2-j\right)}}$ ，

其中 $P_n$ 是第n个Padovan数。

进一步，Mansour [38] 通过生成树、递归关系和左右极大值分解证明了避免3个4长模式(其中有一个是模式1324)对应的生成函数并利用Kuszmau的软件和INSENC软件得到并证明避免4个4长模式的排列上有1100个Wilf-等价类。

Green和Losonczy [39] 引入了自由编织排列，即对于 $S_n\left(3421,4231,4312,4321\right)$ ，Mansour [40] 给出了其计数结果如下：

定理4.

${\displaystyle {\sum }_{n\ge 0}{s}_n\left(3421,4231,4312,4321\right)x^n}=\frac{1-3x-2x^2+\left(1+x\right)\sqrt{1-4x}}{1-4x-x^2+\left(1-x^2\right)\sqrt{1-4x}}$ .

Albert等人 [41] 使用编码插入的方法得到 $s_n\left(3124,4123,3142,4132\right)=\left(\begin{array}{c}2n-2\\ n-1\end{array}\right)$ 。

4. 多长模式的计数结果

Babson和West [42] 证明了 $s_n\left(12\cdots kP\right)=s_n\left(k\left(k-1\right)\cdots 1P\right)$ 中 $k=2,3$ 的情形，这里P是由 $\left\{k+1,\cdots ,l\right\}$ 组成的排列。这样就完成了5长模式的Wilf-等价类的分类工作。

Stankova和West [43] 证明了 $s_n\left(231P\right)=s_n\left(312P\right)$ ，这里P是由 $\left\{4,\cdots ,l\right\}$ 组成的排列，并证明了 $\left\{546213,465213\right\}$ 是Wilf-等价的，完成了6长模式的Wilf-等价类分类。7长模式的Wilf-等价类分类也可用类似的方法完成。

经典 $S_n\left(12\cdots \left(k+1\right)\right)$ 的计数研究和杨表密切相关。设n个元素组成的每行长度不超过k的杨表个数为 $y_k\left(n\right)$ ，其指数型生成函数记为 $Y_k\left(n\right)$ 。Wilf [44] 证明了

${\displaystyle {\sum }_{n\ge 0}{s}_n\left(12\cdots \left(k+1\right)\right)\frac{x^{2n}}{{\left(n!\right)}^2}}=Y_k\left(x\right)Y_k\left(-x\right)\left(k=2,4,6,\cdots \right)$ .

使用初等工具，Bóna [45] 证明了 $s_n\left(12\cdots k\right)\le {\left(k-1\right)}^{2n}$ 。

5. 渐近计数

对任意的 $p\in S_3$ ， $s_n\left(p\right)$ 是Catalan数 $C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$ ，从而有近似估计 $s_n\left(p\right)~\frac{4^n}{n^{\frac{3}{2}}\sqrt{\pi }}$ 。

Bóna [46] 证明了 $s_n\left(1k2\cdots \left(k-1\right)\right)<s_n\left(12\cdots k\right)$ 。

Marcus和Tardos [47] 解决了著名的Stanley-Wilf猜想，即下面定理：

定理5. 对任意的正整数k，任意 $p\in S_k$ ，极限 $\underset{n\to \infty }{\lim }{\left(s_n\left(p\right)\right)}^{\frac{1}{n}}$ 存在。

这一极限称为Stanley-Wilf极限，记为 $L\left(p\right)$ 。数列 $\left\{{\left(s_n\left(p\right)\right)}^{\frac{1}{n}}\right\}$ 称为Stanley-Wilf数列。上面的结果即

$L\left(p\right)=4,p\in S_3$ .

$L\left(12\cdots k\right)={\left(k-1\right)}^2$ .

Bóna [48] 得到 $L\left(12453\right)=9+4\sqrt{2}$ ，证明了 $L\left(p\right)$ 也可以是无理数。其一般形式为如下定理：

定理6. 对 $k\ge 4$ ， $L\left(12\cdots \left(k-3\right)\left(k-1\right)k\left(k-2\right)\right)={\left(k-4+2\sqrt{2}\right)}^2$ .

Albert，Elder和Rechnitzer [49] 证明了 $L\left(4231\right)\ge 9.47$ ，这是避免单个4长模式中Stanley-Wilf极限的最大值。

Kaiser和Klazar [50] 提到Valtr一个未发表的工作是证明了 $L\left(p\right)\ge \frac{{\left(k-1\right)}^2}{e^3}$ ，对任意的 $p\in S_k$ 成立。

使用Bóna [51] 的方法可得

$L\left(1324567\cdots k\right)={\left(k-4+\sqrt{L\left(1324\right)}\right)}^2\ge {\left(k-4+\sqrt{9.47}\right)}^2$ 。

限于篇幅，以上仅对有禁排列的一些经典成果做了综述，还有一些新的研究未及论述，如 [52] 。希望以后可以另起篇幅，对相关进展进行介绍。

基金项目

国家自然科学基金青年基金(项目编号：12201641)；河北省自然科学基金青年科学基金(项目编号：A2021205003)。

参考文献