避免双3长Vincular模式排列的计数研究

Enumeration of Permutations Avoiding Double Vincular Patterns of Length 3

摘要: 本文首先介绍有禁排列相关的基本定义，对避免双3长vincular模式排列的计数结果进行整理，将计数结果相同的模式用表格的形式进行分类。随后我们使用特殊元素分析与位置分析这两种方法，给出等8个避免双3长vincular模式排列计数结果的代数证明。

Abstract: This article first introduces the basic definitions related to forbidden permutations, and summarizes the counting results of bivincular patterns of length 3. We classify patterns with the same counting results and present them intabular form. Additionally, we also provides algebraic proofs for the counting results of eight bivincular patterns of length 3, including , using two mainmethods: analysis of special elements and analysis of positions.

1. 引言

排列是一种重要的离散结构，在组合数学中具有其重要的研究意义 [1] ，其中有禁排列的计数理论是近些年来较为热门的研究方向。在上世纪60年代末，Knuth [2] 研究计算机的排序算法时发现了有禁排列在其领域的首个明确应用，他发现有禁模式与堆栈的分类有关，这次发现使得越来越多的学者开始关注并深入研究有禁排列这个领域。在1985年，Simion和Schmidt [3] 首次对有禁排列进行了系统研究，他们的相关成果不仅丰富了排列与其他组合结构之间的对应关系 [4] ，还促进了有禁排列之间Wilf-等价关系的研究 [5] 。至此以后，对有禁排列的研究开始逐步形成体系，学者们也对有禁模式的研究逐渐拓宽限制 [6] 。

在1981年，Rotem [7] 对避免双3长普通模式的排列进行了研究，得到 $S_n\left(231,312\right)$ 的计数结果是 $2^{n-1}$ 。1995年，Julian West [8] 提出了生成树应用于 $S_n\left(132,231\right)$ 的计数问题。1997年，Miklós Bóna [9] 首次解决了S_n避免单个4长模式的排列计数问题，得到 $S_n\left(1342\right)$ 的生成函数，并证明了 $S_n\left(1342\right)$ 的计数结果等于n个顶点上某种类型的标记平面数。

到了2000年，Babson和Steingrímsson [10] 提出了vincular模式，其要求模式中需存在相连的部分，拓宽了对有禁排列的研究道路，因此有更加丰富多样的有禁模式问题等待着人们的探究。此外，Claesson [11] 研究了避免单一3长vincular模式和避免双3长vincular模式排列的计数结果，并建立了 $S_n\left(1\underset{\_}{23},\underset{\_}{13}2\right)$ 与Motzkin路之间的双射 [11] 。这个研究打开了Motzkin数与Catalan数之间的研究方向，此后更多计数结果为Motzkin数与Catalan数的 有禁排列在此基础上被深入研究。在2003年，Kitaev利用归纳法得到了 $S_n\left(\underset{\_}{213},\underset{\_}{312}\right)$ 的计数结果是 $2^{n-1}$ [12] 。自此学者们开始对避免双vincular模式排列的计数问题与其他组合结构之间建立双射进行研究。此后不久，Elizalde和Mansour 在2005年通过与Motzkin路之间建立双射得到 $S_n\left(\underset{\_}{123},132\right)$ 的计数结果是第n个Motzkin数 [13] 。在2010年，Barnabei、Bonetti和Silimbani [14] 也通过与Motzkin路之间建立双射得到 $S_n\left(\underset{\_}{213},312\right)$ 的计数结果是第n个Motzkin数。

在上述学者研究的基础上，本文中我们给出了部分避免双3长vincular模式排列的部分计数结果，并使用特殊元素法和位置分析法提供了代数证明。

2. 有禁排列的基本理论

记S_n表示 $\left[n\right]=\left\{1,2,\cdots ,n\right\}$ 的排列集合。我们可以将每个排列 $\sigma \in S_n$ 表示为 ${\sigma }_1{\sigma }_2\cdots {\sigma }_n$ ，其中 ${\sigma }_i$ 表示排列 $\sigma$ 从左往右第i个位置上的数。对 $i=\text{1},\text{2},\cdots ,n-\text{1}$ ，我们称 ${\sigma }_i$ 与 ${\sigma }_{i+1}$ 左邻接，元素 ${\sigma }_{i+1}$ 与 ${\sigma }_i$ 右邻接。

如果对每一个指标i，满足 ${\sigma }_{i+1}={\sigma }_i+1$ (或 ${\sigma }_{i+1}={\sigma }_i-1$ )，则称排列 $\sigma$ 是连续递增(或递减)的。

定义1 一个排列 $\sigma$ 的前缀是一个对于某个正整数p，取连续的初始子序列 ${\sigma }_1{\sigma }_2\cdots {\sigma }_p$ 。

定义2 给定一个排列 $\sigma \in S_n$ ，如果 $\sigma \left(i\right)>\sigma \left(i+\text{1}\right)$ ，则称位置 $i\in \left[n-\text{1}\right]$ 是 $\sigma$ 的下降。类似地，如果 ${\sigma }_i<{\sigma }_{i+1}$ ，则称位置 $i\in \left[n-\text{1}\right]$ 是 $\sigma$ 的上升。

定义3 给定一个排列 $\sigma \in S_n$ ，如果存在指标 $c_1<\cdots <c_k$ 使得 ${\sigma }_{c_1}{\sigma }_{c_2}\cdots {\sigma }_{c_k}$ 与长度为k的排列 $\pi$ 同构(即它们各个位置的大小顺序相同)则称排列 $\sigma$ 包含模式 $\pi$ 。一个排列如果不包含一个模式 $\pi$ ，那么这个排列称为避免模式 $\pi$ 。S_n中避免模式 $\pi$ 的排列组成的集合记为 $S_n\left(\pi \right)$ 。

例如：排列4132中第1，2，3位与排列312同构，因此排列4132包含模式312。而排列3241则避免模式312。

特别地，vincular模式是要求模式存在部分相连。如312模式要求必须是前两个位置邻接。

例如：排列4132包含模式312，排列4213则避免模式312 (它里面413与312同构，但4和1不邻接)。

定义4 若 $\left|S_n\left({\pi }_1,\cdots ,{\pi }_k\right)\right|=\left|S_n\left({\tau }_1,\cdots ,{\tau }_{\mathcal{l}}\right)\right|$ ，则称两组模式 ${\pi }_1,\cdots ,{\pi }_k$ 和 ${\tau }_1,\cdots ,{\tau }_{\mathcal{l}}$ 在 $S_n$ 上是Wilf-等价的。

给定一个排列 $\sigma ={\sigma }_{\text{1}}{\sigma }_{\text{2}}\cdots {\sigma }_n$ ，定义 $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n\to \left(n+1-{\sigma }_1\right)\left(n+1-{\sigma }_2\right)\cdots \left(n+1-{\sigma }_n\right)$ ，这个双射过程为互补。定义 $\sigma ={\sigma }_{\text{1}}{\sigma }_{\text{2}}\cdots {\sigma }_n\to {\sigma }_n{\sigma }_n{}_{-\text{1}}\cdots {\sigma }_{\text{1}}$ ，这个双射过程为翻转。若两个有禁模式互为翻转或互补至少满足一个，那么避免这两个模式的排列是一一对应的，自然满足Wilf-等价性。

定义5 以(0, 0)为起点，以(n, 0)为终点，由上步 $U=\left(\text{1},\text{1}\right)$ ，下步 $D=\left(-\text{1},-\text{1}\right)$ 和水平步 $H=\left(\text{1},0\right)$ 构成的格路经，称为一条长度为n的Motzkin路，且全程不会穿越到x轴的下方。长度为n的Motzkin路的数量记为第n个Motzkin数M_n。

为了刻画排列之间的构造关系，我们定义排列的直和与斜和。

定义6 设 $\sigma$ 是长度为n的排列， $\pi$ 是长度为m的排列，则 $\sigma$ 和 $\pi$ 的直和 $\sigma \ominus \pi$ 定义为

$\sigma \ominus \pi \left(i\right)=\{\begin{array}{l}\sigma \left(i\right)+m1\le i\le n\\ \pi \left(i-n\right)n+1\le i\le m+n\end{array}$ 。

例如： $132\ominus 123=465123$ 。

定义7 设 $\sigma$ 是长度为n的排列， $\pi$ 是长度为m的排列，则 $\sigma$ 和 $\pi$ 的直和 $\sigma \oplus \pi$ 定义为

$\sigma \oplus \pi \left(i\right)=\{\begin{array}{l}\sigma \left(i\right)1\le i\le n\\ \pi \left(i-n\right)+nn+1\le i\le m+n\end{array}$ 。

例如： $132\oplus 123=132456$ 。

3. 避免双3长Vincular模式排列的计数结果证明

本文将给出 $S_n$ 及 $S_n^1$ 上避免双3长vincular模式排列部分有代表性的非平凡计数结果，如下表1：

Table 1. Enumeration results of avoiding double vincular patterns of length 3 on S n and S n 1

表1. $S_n$ 及 $S_n^1$ 上避免双3长vincular模式的计数结果

我们在这一部分使用位置分析法和元素分析法 [15] 给出部分避免双3长vincular模式排列计数结果的代数证明。元素分析法指的是先安排特殊元素再处理其他元素。例如在排列中先确认最大值n，通过对n位置的讨论来归纳出所有排列的计数结果。位置分析法则需要先满足特殊位置的要求，再处理其他位置。例如在避免vincular模式排列的问题中可以先确认相邻部分的位置关系，然后再处理不要求相邻的位置，以此来归纳出所有的位置结果。

引理1 Motzkin数的计数结果 [16]

$M_n=\frac{1}{n+1}\underset{k=0}{\overset{\lfloor \frac{n}{2}\rfloor }{{\displaystyle \sum }}}\left(\begin{array}{c}n+1\\ k,k+1,n-2k\end{array}\right)$ ，

有递推式 $M_{n+1}=M_n+{\displaystyle {\sum }_{k=0}^{n-1}{M}_k{M}_{n-1-k}}\left(M_0=M_1=1\right)$ 。

定理2 对于 $n\ge 1$ ，有 $\left|S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=M_n$ 。

证明 记 $\left|S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=a_n$ ，易得 $a_1=1=M_0$ ， $a_2=2=M_1$ 。当 $n\ge 3$ 时，对于 $\left|S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，为避免 $\underset{\_}{321}$ 和312模式， ${\sigma }_R$ 最多只能有1个元素，故n在排列中的位置只有两种情况：

1) 当n在末位时。此时 ${\sigma }_R$ 为空排列， ${\sigma }_L$ 中每一个元素都小于n，得 ${\sigma }_L\in S_{n-1}\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 。反之，对任一排列 $\tau \in S_{n-1}\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ ，可得 ${\tau }_n\in S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 。所以该情况下 $\sigma$ 的数量为 $a_{n-1}$ 。

2) 当n在第 $n-1$ 位时。此时 ${\sigma }_R$ 中只有一个元素，此时仍可分为两种情况，即这个元素是否为 $n-1$ 。

若，同1)可得 ${\sigma }_L\in S_{n-2}\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ ，该情况下此类 $\sigma$ 的数量为 $a_{n-2}$ 。

若不然，为了排列避免 $\underset{\_}{321}$ 和312模式，所以在排列的后四位中只存在 $u,n-\text{1},n,v$ 与 $n-\text{1},u,n,v$ 两种排列方式，且为了避免312模式在第二种排列方式中u > v。由此令 $n-1$ 在第 $i\left(i=n-\text{2},n-\text{3}\right)$ 位，记排列为 ${\sigma }_l\left(n-1\right){\sigma }_r$ ，显然 ${\sigma }_l\in S_{i-1}\left(\underset{\_}{3}\underset{\_}{2}\underset{\_}{1},\underset{\_}{3}\underset{\_}{1}2\right)$ ， ${\sigma }_r\in S_{n-i}\left(\underset{\_}{3}\underset{\_}{2}\underset{\_}{1},\underset{\_}{3}\underset{\_}{1}2\right)$ ，这时仅对于 $n-1$ 的位置的排列结果为

${\displaystyle \underset{n-3}{\overset{n-2}{\sum }}{a}_i{a}_{n-i-2}}$ 。

同理，当我们固定 $n-1$ 的位置讨论 $n-2$ 时发现，对于 $n-2$ 同样只有 $u,n-\text{2},n-\text{1}$ 与 $n-\text{2},u,n-\text{1}$ 两种排列方式。这时对于 $n-2$ 的位置的排列结果为

${\displaystyle \underset{n-5}{\overset{n-4}{\sum }}{a}_i{a}_{n-i-2}}$ 。

由此，因为 $n\ge 3$ ，我们可以归纳出当n在倒数第二位时 $\sigma$ 的数量为

${\displaystyle \underset{0}{\overset{n-2}{\sum }}{a}_i{a}_{n-i-2}}$ 。

综合上述两种情况，可得：

$a_n=a_{n-1}+{\displaystyle {\sum }_0^{n-2}{a}_i{a}_{n-i-2}}\left(n\ge 3\right)$ 。

将递推关系式与 $M_n$ 的递推关系式对比，并结合初值可证 $a_n=M_n\left(n\ge 3\right)$ 。

证毕。

定理3 对于 $n\ge \text{2}$ ，用 $S_n^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 表示 $S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中首位上升的排列组成的集合，记 $b_n=\left|S_n^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|$ ，则有 $b_n+b_{n-1}=M_n$ 。

证明 对于 $S_n^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，由于 $\sigma$ 避免 $\underset{\_}{321}$ 模式且避免312模式，显然n不可能出现在首位。

当n不在首位时。上文已证 $\left|S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=M_n$ ，用 $S_n^2\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 表示 $S_n\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中首位下降的排列组成的集合。对任取的 $\sigma \in S_n^2\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ ，由于 $\sigma$ 避免 $\underset{\_}{321}$ 模式，则 ${\sigma }_{\text{1}}>{\sigma }_{\text{2}}$ ， ${\sigma }_3>{\sigma }_2$ 。为了保证该排列避免312模式，必须满足 ${\sigma }_1={\sigma }_2+1$ 。去掉 ${\sigma }_{\text{1}}$ ，对于 ${\sigma }_3{\sigma }_4\cdots {\sigma }_n$ 中大于 ${\sigma }_2$ 的数都减1，操作后得到的排列 ${\sigma }^{\prime }\in S_{n-1}^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 。反之，任取一排列 $\tau ={\tau }_1{\tau }_2\cdots {\tau }_{n-1}\in S_{n-1}^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ ，在 $\tau$ 中第一个位置前面插入 ${\tau }_1+1$ ，其后比 ${\tau }_1$ 大的数都加1，得到的排列 ${\tau }^{\prime }\in S_n^2\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 。

因此，综合上述两种情况，可得

$M_n=\left|S_n^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|+\left|S_{n-1}^1\left(\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder>},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=b_n+b_{n-1}$ 。

证毕。

定理4 对于 $n\ge 1$ ，有 $\left|S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=1+\frac{n\left(n-1\right)}{2}$ 。

证明 对于 $S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，则n在排列中的位置可分为两种情况：

1) 当n在首位时。此时排列 ${\sigma }_L$ 为空且排列 ${\sigma }_R$ 中任一元素均小于n，显然 ${\sigma }_R$ 满足避免123模式。又 ${\sigma }_R$ 避免312模式，则 ${\sigma }_R$ 首位 ${\sigma }_2=n-1$ ，否则一定存在 ${\sigma }_i=n-1$ ， $3\le i\le n$ ，使得 $n{\sigma }_2{\sigma }_i$ 构成312模式。同理我们得到 ${\sigma }_R$ 的第二位 ${\sigma }_3=n-2$ ，第三位 ${\sigma }_4=n-3$ ，故 ${\sigma }_R$ 是一个单调递减的排列。所以该情况下，此类 $\sigma$ 的数量为1。

2) 当n不在首位时。由1)可得在排列 $\sigma ={\sigma }_{L}n{\sigma }_R$ 中， ${\sigma }_R$ 一定是一个单调递减的排列。因为 ${\sigma }_{L}n$ 避免123模式，因此除了最后一位， ${\sigma }_L$ 中不存在上升。又 ${\sigma }_L$ 避免312模式，可以得出 ${\sigma }_L$ 只有连续下降且元素相连这一种排列方式，对应的排列情况为从 $n-1$ 开始的 $n-1$ ， $n-\text{1},n-\text{2}$ 直至 $n-\text{1},n-\text{2},\cdots ,\text{1}$ 。从 $n-2$ 开始的 $n-2$ ， $n-\text{2},n-\text{3}$ 直至 $n-\text{2},n-\text{3},\cdots ,\text{1}$ 。依此类推下去。

所以在该情况下，此类 $\sigma$ 的数量为

$\frac{\left(n-1\right)\left[1+\left(n-1\right)\right]}{2}$ 。

综合上述两种情况，可得：

$\left|S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=1+\frac{n\left(n-1\right)}{2}$ 。

证毕。

定理5 对于 $n\ge 1$ ，有 $\left|S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=n-1$ 。

证明对于 $S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，由于 $\sigma$ 是首位上升排列，则n不在排列首位。由于 $n{\sigma }_R$ 避免312模式， ${\sigma }_R$ 只能是一个单调递减的排列。又 ${\sigma }_L$ 避免123模式，所以在 ${\sigma }_L$ 中同样不存在上升。但 $\sigma$ 又满足首位上升，因此当 ${\sigma }_L$ 中有且仅有一个元素才可以满足条件。

综上所述n只能在排列的第二位，此时 ${\sigma }_L$ 是除n以外的任意一个元素， ${\sigma }_R$ 因单调递减被选取的 ${\sigma }_L$ 唯一确定，所以在该情况下，此类 $\sigma$ 的数量为

$\left|S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=n-1$ 。

证毕。

定理6 对于 $n\ge \text{2}$ ，有 $\left|S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)\right|=n-1$ 。

证明 对于 $S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，由于 $\sigma$ 是首位上升排列，则n不在排列首位。

由于 $n{\sigma }_R$ 避免 $3\underset{\_}{12}$ 模式，则在 ${\sigma }_R$ 中不存在上升，即 ${\sigma }_R$ 是一个单调递减的排列。又 ${\sigma }_L$ 避免123模式，所以在 ${\sigma }_L$ 中同样不存在上升。但 $\sigma$ 又满足首位上升，因此当 ${\sigma }_L$ 中有且仅有一个元素才可以满足条件。

综上所述n只能在排列的第二位，此时 ${\sigma }_L$ 是除n以外的任意一个元素， ${\sigma }_R$ 因单调递减被选取的 ${\sigma }_L$ 唯一确定，所以在该情况下，此类 $\sigma$ 的数量为

$\left|S_n^1\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)\right|=n-1$ 。

证毕。

定理7 对于 $n\ge 1$ 时|， $\left|S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)\right|=2^{n-1}$ 。

证明 对于 $S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，则n在排列中的位置可分为两种情况：

1) 当n在首位时。此时排列 ${\sigma }_L$ 为空且排列 ${\sigma }_R$ 中任一元素均小于n，显然 ${\sigma }_R$ 满足避免123模式。又 ${\sigma }_R$ 避免 $3\underset{\_}{12}$ 模式，则 ${\sigma }_R$ 中不存在上升，故此时排列 ${\sigma }_R$ 只有 $n-\text{1},n-\text{2,}\cdots ,\text{2},\text{1}$ 一种排列方法。不妨记该排列是 ${\sigma }_L$ 在 $n-1$ 个数中任取0个数得到的。即此类情况下 $\sigma$ 的数量为

$C_{n-1}^0$ 。

2) 当n不在首位时。由1)可得在排列 $\sigma ={\sigma }_{L}n{\sigma }_R$ 中， ${\sigma }_R$ 一定是一个单调递减的排列。因为 ${\sigma }_{L}n$ 中不存在123模式，所以除了最后一位， ${\sigma }_L$ 中不存在上升。因此 ${\sigma }_L$ 是在 $n-1$ 个数中任取 $i\left(1\le i\le n\right)$ 个数按递减顺序构成的排列，同时 ${\sigma }_R$ 也因单调递减唯一确定。

此类情况下 $\sigma$ 的数量为

$C_{n-1}^1+C_{n-1}^2+\cdots +C_{n-1}^{n-1}$ 。

综合上述两种情况，由二项式定理可得：

$\left|S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)\right|=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+\cdots +C_{n-1}^{n-1}={\left(1+1\right)}^{n-1}=2^{n-1}$ 。

证毕。

定理8 当n ≥ 1时，有 $\left|S_n\left(\text{<munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=2^{n-1}$ 。

证明 对于 $S_n\left(\text{<munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，则n在排列中的位置可分为两种情况：

1) 当n在首位时。此时排列 ${\sigma }_L$ 为空且排列 ${\sigma }_R$ 中任一元素均小于n，显然 ${\sigma }_R$ 满足避免213模式。又 ${\sigma }_R$ 避免312模式，则 ${\sigma }_R$ 首位 ${\sigma }_2=n-1$ ，否则一定存在 ${\sigma }_i=n-1$ ， $3\le i\le n$ ，使得 $n{\sigma }_2{\sigma }_i$ 构成312模式。进一步可得 ${\sigma }_3=n-2$ ，依此类推得排列 ${\sigma }_R$ 只有 $n-1,n-2,\cdots ,2,1$ 一种排列方法。不妨记该排列是 ${\sigma }_L$ 在 $n-1$ 个数中任取0个数得到的。即此类情况下 $\sigma$ 的数量为

$C_{n-1}^0$ 。

2) 当n不在首位时。由1)可得在排列 $\sigma ={\sigma }_{L}n{\sigma }_R$ 中， ${\sigma }_R$ 一定是一个单调递减的排列。又因为 $\sigma$ 避免213模式，因此在 ${\sigma }_L$ 中只存在上升不存在下降，因此 ${\sigma }_L$ 是在 $n-1$ 个数中任取 $i\left(1\le i\le n\right)$ 个数按递增顺序构成的排列，同时 ${\sigma }_R$ 也因单调递减唯一确定。

综合上述两种情况，由二项式定理可得：

$\left|S_n\left(\text{<munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder> 3},\text{3 <munder accentunder="true"> 1 <mo> \_ </mo> </munder> <munder accentunder="true"> 2 <mo> \_ </mo> </munder>}\right)\right|=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+\cdots +C_{n-1}^{n-1}={\left(1+1\right)}^{n-1}=2^{n-1}$ 。

证毕。

定理9 当 $n\ge \text{1}$ 时，有 $\left|S_n^1\left(\text{<munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=2^{n-1}-1$ 。

证明 对于 $S_n^1\left(\text{<munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)$ 中任一排列 $\sigma$ ，记 $\sigma ={\sigma }_{L}n{\sigma }_R$ ，由于 $\sigma$ 是首位上升排列，则n不在排列首位。又 ${\sigma }_L$ 满足避免213模式，同定理8，在 ${\sigma }_L$ 中不存在下降，即 ${\sigma }_L$ 是一个单调递增的排列。又 ${\sigma }_R$ 避免312模式，则 ${\sigma }_R$ 首位 ${\sigma }_2$ 为 ${\sigma }_R$ 中的最大数，否则一定存在 ${\sigma }_i\left(3\le i\le n\right)$ 使得 $n{\sigma }_2{\sigma }_i$ 构成312模式。进一步可得 ${\sigma }_3$ 为 ${\sigma }_R$ 中的次大数，依此类推可证排列 ${\sigma }_R$ 单调递减。此类情况下 ${\sigma }_L$ 是在 $n-1$ 个数中任取 $i\left(1\le i\le n\right)$ 个数按递增顺序构成的排列，同时 ${\sigma }_R$ 也因单调递减唯一确定。

综合上述情况，可得：

$\left|S_n^1\left(\text{<munder accentunder="true"> 2 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 3},\text{<munder accentunder="true"> 3 <mo> \_ </mo> </munder> <munder accentunder="true"> 1 <mo> \_ </mo> </munder> 2}\right)\right|=C_{n-1}^1+C_{n-1}^2+\cdots +C_{n-1}^{n-1}=2^{n-1}-1$ 。

证毕。

4. 总结

本文只对避免双3长vincular模式排列的部分计数结果进行了研究，并利用位置分析法和元素分析法对计数结果做了单一的代数证明，对于计数结果是第n个Motzkin数的情况，我们猜测其与组合结构Motzkin路可能存在双射，之后将会进一步深入研究。

由于避免双3长vincular模式排列的情况众多，本文研究了部分有代表性的非平凡计数结果，对于其他情况的计数结果，有兴趣的读者可以进行类似的分析与计算。

基金项目

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