#### 期刊菜单

Enumeration of Permutations Avoiding Double Vincular Patterns of Length 3
DOI: 10.12677/PM.2023.1310322, PDF, HTML, XML, 下载: 167  浏览: 286  科研立项经费支持

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. 引言

2. 有禁排列的基本理论

Sn表示 $\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}$ 右邻接。

$\sigma \ominus \pi \left(i\right)=\left\{\begin{array}{l}\sigma \left(i\right)+m\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}1\le i\le n\\ \pi \left(i-n\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}n+1\le i\le m+n\end{array}$

$\sigma \oplus \pi \left(i\right)=\left\{\begin{array}{l}\sigma \left(i\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}1\le i\le n\\ \pi \left(i-n\right)+n\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}n+1\le i\le m+n\end{array}$

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

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

${M}_{n}=\frac{1}{n+1}\underset{k=0}{\overset{⌊\frac{n}{2}⌋}{\sum }}\left(\begin{array}{c}n+1\\ k,k+1,n-2k\end{array}\right)$

1) 当n在末位时。此时 ${\sigma }_{R}$ 为空排列， ${\sigma }_{L}$ 中每一个元素都小于n，得 ${\sigma }_{L}\in {S}_{n-1}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ 。反之，对任一排列 $\tau \in {S}_{n-1}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ ，可得 ${\tau }_{n}\in {S}_{n}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ 。所以该情况下 $\sigma$ 的数量为 ${a}_{n-1}$

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

，同1)可得 ${\sigma }_{L}\in {S}_{n-2}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ ，该情况下此类 $\sigma$ 的数量为 ${a}_{n-2}$

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

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

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

${a}_{n}={a}_{n-1}+{\sum }_{0}^{n-2}{a}_{i}{a}_{n-i-2}\left(n\ge 3\right)$

n不在首位时。上文已证 $|{S}_{n}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)|={M}_{n}$ ，用 ${S}_{n}^{2}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ 表示 ${S}_{n}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ 中首位下降的排列组成的集合。对任取的 $\sigma \in {S}_{n}^{2}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 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{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ 。反之，任取一排列 $\tau ={\tau }_{1}{\tau }_{2}\cdots {\tau }_{n-1}\in {S}_{n-1}^{1}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$ ，在 $\tau$ 中第一个位置前面插入 ${\tau }_{1}+1$ ，其后比 ${\tau }_{1}$ 大的数都加1，得到的排列 ${\tau }^{\prime }\in {S}_{n}^{2}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)$

${M}_{n}=|{S}_{n}^{1}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)|+|{S}_{n-1}^{1}\left(\text{3 _ 2 _ 1 _},\text{3 _ 1 _ 2}\right)|={b}_{n}+{b}_{n-1}$

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}$ 。依此类推下去。

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

$|{S}_{n}\left(\text{1 _ 2 _ 3},\text{3 _ 1 _ 2}\right)|=1+\frac{n\left(n-1\right)}{2}$

$|{S}_{n}^{1}\left(\text{1 _ 2 _ 3},\text{3 _ 1 _ 2}\right)|=n-1$

$|{S}_{n}^{1}\left(\text{1 _ 2 _ 3},\text{3 1 _ 2 _}\right)|=n-1$

1) 当n在首位时。此时排列 ${\sigma }_{L}$ 为空且排列 ${\sigma }_{R}$ 中任一元素均小于n，显然 ${\sigma }_{R}$ 满足避免123模式。又 ${\sigma }_{R}$ 避免 $3\text{ }\text{ }\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}$ 也因单调递减唯一确定。

${C}_{n-1}^{1}+{C}_{n-1}^{2}+\cdots +{C}_{n-1}^{n-1}$

$|{S}_{n}\left(\text{1 _ 2 _ 3},\text{3 1 _ 2 _}\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}$

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}$ 也因单调递减唯一确定。

$|{S}_{n}\left(\text{1 _ 2 _ 3},\text{3 1 _ 2 _}\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}$

$|{S}_{n}^{1}\left(\text{2 _ 1 _ 3},\text{3 _ 1 _ 2}\right)|={C}_{n-1}^{1}+{C}_{n-1}^{2}+\cdots +{C}_{n-1}^{n-1}={2}^{n-1}-1$

4. 总结

 [1] Kitaev, S. (2011) Patterns in Permutations and Words. Springer, Heidelberg. [2] Knuth, D.E. (1973) The Art of Computer Programming, Volume 3: Sorting and Searching. Pearson Education, India. [3] Simion, R. and Schmidt, F.W. (1985) Restricted Permutations. European Journal of Combinatorics, 6, 383-406. https://doi.org/10.1016/S0195-6698(85)80052-4 [4] Lewis, J.B. (2011) Pattern Avoidance for Alternating Per-mutations and Young Tableaux. Journal of Combinatorial Theory, Series A, 118, 1436-1450. https://doi.org/10.1016/j.jcta.2010.12.010 [5] Bloom, J.A. (2014) Refinement of Wilf-Equivalence for Patterns of Length 4. Journal of Combinatorial Theory, Series A, 124, 166-177. https://doi.org/10.1016/j.jcta.2014.01.001 [6] Kremer, D. and Shiu, W.C. (2003) Finite Transition Matrices for Permutations Avoiding Pairs of Length Four Patterns. Discrete Mathematics, 268, 171-183. https://doi.org/10.1016/S0012-365X(03)00042-6 [7] Rotem, D. (1981) Stack Sortable Permutations. Discrete Mathematics, 33, 185-196. https://doi.org/10.1016/0012-365X(81)90165-5 [8] West, J. (1996) Generating Trees and Forbidden Subse-quences. Discrete Mathematics, 157, 363-372. https://doi.org/10.1016/S0012-365X(96)83023-8 [9] Bóna, M. (1997) Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps. Journal of Combinatorial Theory, Series A, 80, 257-272. https://doi.org/10.1006/jcta.1997.2800 [10] Babson, E. and Steingrímsson, E. (2000) Generalized Per-mutation Patterns and a Classification of the Mahonian Statistics. Séminaire Lotharingien de Combinatoire (Electronic Only), 44, 1-18. [11] Claesson, A. (2001) Generalized Pattern Avoidance. European Journal of Combinatorics, 22, 961-971. https://doi.org/10.1006/eujc.2001.0515 [12] Kitaev, S. (2003) Multi-Avoidance of Generalised Patterns. Discrete Mathematics, 260, 89-100. https://doi.org/10.1016/S0012-365X(02)00452-1 [13] Elizalde, S. and Mansour, T. (2005) Restricted Motzkin Permutations, Motzkin Paths, Continued Fractions, and Chebyshev Polynomials. Discrete Mathematics, 305, 170-189. https://doi.org/10.1016/j.disc.2005.10.010 [14] Barnabei, M., Bonetti, F. and Silimbani. M. (2010) The Joint Dis-tribution of Consecutive Patterns and Descents in Permutations Avoiding 3-1-2. European Journal of Combinatorics, 31, 1360-1371. https://doi.org/10.1016/j.ejc.2009.11.011 [15] 武蕊红. 排列组合中常见的问题及解题方法[J]. 山西师范大学学报: 自然科学版, 2013(S1): 5-6. [16] Donaghey, R. and Shapiro, L.W. (1977) Motzkin Numbers. Journal of Com-binatorial Theory, Series A, 23, 291-301. https://doi.org/10.1016/0097-3165(77)90020-6