Research on enumeration problem of pattern-avoiding permutations

Abstract

The problem of relevant enumeration with pattern-avoiding permutations is a significant topic in enumerative combinatorics and has wide applications in physics, chemistry, and computer science. This paper summarizes the relevant conclusions of the enumeration of pattern-avoiding permutations on the n-element symmetric group {\mathcal{S}}_n, alternating permutations, Dumont permutations, Ballot permutations, and inversion sequences. It also introduces relevant research results on avoiding vincular patterns and barred patterns in {\mathcal{S}}_n.

Keywords

Pattern avoidance / combinatorial enumeration / combinatorial bijection

1 Research on pattern-avoiding enumeration on {\mathcal{S}}_{\mathit{n}}

Researches on pattern problems on permutation sets can be traced back to the 1880s, when MacMahon [47] used generating functions to study the distribution of permutations and inverse numbers in words. In 1985, Simion and Schmidt [62] first systematically studied the problem of pattern avoidance on permutations. Since then, the problem of patterns on permutation sets has attracted the attention of many combinatorial scholars. The problem of pattern avoidance on permutations with different constraints has become a hot topic in combinatorial mathematics, and relevant pattern-avoiding permutations can bijectively correspond with many combinatorial structures. This paper reviews relevant achievements in this field and introduces conclusions and conjectures on the n-element symmetric group S_n, alternating permutations, Dumont permutations, Ballot permutations, and pattern avoidance problems on inversion sequences. It also presents research results on avoiding vincular patterns and barred patterns in {\mathcal{S}}_n.

Denote the n-element symmetric group S_n as the set of all permutations on \left[n\right]=\{1,2,\dots ,n\}, such as S_1=\left\{1\right\}, {\mathcal{S}}_2=\{12,21\}, {\mathcal{S}}_3=\{123,132,213,231,312,321\}.

Definition 1.1　Given two permutations \sigma ={\sigma }_1{\sigma }_2\dots {\sigma }_n and \pi ={\pi }_1{\pi }_2\dots {\pi }_k, if there exists , such that the subpermutation {\sigma }_{c_1}{\sigma }_{c_2}\dots {\sigma }_{c_k} and \pi are order isomorphic, i.e., if and only if , then permutation \sigma is said to contain pattern \sigma. If there does not exist a subpermutation of \sigma that is order isomorphic to \pi, permutation \sigma is said to avoid pattern \pi. The set of permutations avoiding pattern \pi on S_n is denoted by {\mathcal{S}}_n\left(\pi \right).

Definition 1.2　If \left|{\mathcal{S}}_n\left(\pi \right)\right|=\left|{\mathcal{S}}_n\left(\tau \right)\right|, we say the two patterns \pi and \tau are Wilf equivalent in {\mathcal{S}}_n.

Knuth [40] first proposed the “pattern theory” and obtained that the enumeration result for avoiding any length-3 pattern is a Catalan number C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{n}{2n}\right) and provided the bijection between {\mathcal{S}}_n\left(132\right) and Dyck paths. Later, Simion and Schmidt [62] systematically studied the problem of avoiding patterns on permutations and constructed the bijection between S_n\left(123\right) and {\mathcal{S}}_n\left(132\right). West [68] established the bijection between {\mathcal{S}}_n\left(123\right) and {\mathcal{S}}_n\left(132\right) using a spanning tree. Reference [61] established the bijection between {\mathcal{S}}_n\left(321\right) and {\mathcal{S}}_n\left(132\right) with matrix transformation. Simion and Schmidt [62] also obtained all enumeration results for avoiding two and three length-3 patterns in S_n, as shown in the following theorems.

Theorem 1.1　(1) For n\ge 1, any p\in \{\left(123,132\right),\left(123,213\right),\left(231,321\right),(132,213),\left(132,231\right),\left(132,312\right),\left(213,231\right),\left(213,312\right),\left(231,312\right),\left(312,321\right)\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=2^{n-1}.

(2) For n\ge 1, any p\in \{\left(123,231\right),\left(123,312\right),\left(132,321\right),\left(213,321\right)\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=1+\left(\begin{array}{c}n\\ 2\end{array}\right).

(3) For n\ge 5, there exists

\left|{\mathcal{S}}_n\left(123,321\right)\right|=0.

Theorem 1.2　(1) For n\ge 1, any p\in \{\left(123,132,213\right),\left(231,312,321\right)\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=F_{n+1},

where F_n is the n-th Fibonacci number.

(2) For n\ge 1, any p\in \{\left(123,132,231\right),\left(123,213,312\right),\left(123,231,312\right),(132,213,231),(132,213,312),(132,213,321),(132,213,321),\left(132,231,312\right), (132,231,321),(213,231,321),\left(213,312,321\right)\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=n.

(3) For n\ge 5, any p\in \{\left(123,132,321\right),\left(123,213,321\right),\left(123,231,321\right),(123,312,321)\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=0.

Simion and Schmidt [62] also obtained that the enumeration result for avoiding four and five length-3 patterns on {\mathcal{S}}_n was a simple constant.

There are also abundant achievements in the research on avoiding length-4 patterns on {\mathcal{S}}_n. The permutations that avoid a single length-4 pattern can be divided into three Wilf equivalent classes. Bóna [7] and Regev [60] presented the generating functions for the enumeration of avoiding 1342 and 1234 pattern equivalence classes. Gessel [35] and Bóna [7] gave the enumeration results for avoiding these patterns. Conway and Guttmann [28] used a modified algorithm to estimate the enumeration result of {\mathcal{S}}_n\left(1324\right) in the remaining Wilf equivalent classes. West [67] obtained the enumeration result for avoiding a length-3 and length-4 pattern at the same time on {\mathcal{S}}_n with a spanning tree. Most of the results are related to Fibonacci number. Kremer and Shiu [42] detailed the enumeration problem of avoiding double length-4 patterns on {\mathcal{S}}_n. Mansour [50] gave the enumeration result of maximal partial permutation {\mathcal{S}}_n(1324,2134,1243).

Among the studies of avoiding multiple-length patterns on {\mathcal{S}}_n, through constructing bijections, Backelin et al. [3] obtained \left|{\mathcal{S}}_n\right(12\cdots k\tau \left)\right| = \left|{\mathcal{S}}_n\left(k\left(k-1\right)\cdots 1\tau \right)\right|, where \tau is a random permutation comprised of \{k+1,\dots ,l\}. Reference [61] got \left|{\mathcal{S}}_n\left(\tau k\left(k-1\right)\right)\right|=\left|{\mathcal{S}}_n\left(\tau \left(k-1\right)k\right)\right|, where \tau is a random permutation comprised of \{1,\dots ,k-2\}.

The asymptotic enumeration problem of pattern-avoiding permutations on {\mathcal{S}}_n has also attracted the attention of scholars. Marcus and Tardos [55] solved the famous Stanley-Wilf Conjecture, as shown in the following theorem.

Theorem 1.3　 For any positive integer k and any \tau \in S_k, {\mathrm{l}\mathrm{i}\mathrm{m}}_{n\to \mathrm{\infty }}{\left(\left|{\mathcal{S}}_n\left(\tau \right)\right|\right)}^{\frac{1}{n}} exists and is finite.

This is called the Stanley-Wilf limit for pattern \tau, denoted by L\left(\tau \right). When \tau \in {\mathcal{S}}_3, L\left(\tau \right)=4 is proved. When \tau \in {\mathcal{S}}_4, there are three Wilf equivalent classes. Regev [60] proved L\left(1234\right)=9, and \text{Bóna} [7] proved L\left(1342\right)=8. The Stanley-Wilf limit of pattern 1324 in the remaining equivalent class remains an open issue. Conway et al. [29] obtained . Mansour and Nassau [52] got L\left(1324567\cdots k\right)\ge {\left(k-4+\sqrt{9.47}\right)}^2.

2 Research on pattern-avoiding enumeration on alternating permutations

Definition 2.1　Given a permutation \sigma, if , then permutation \sigma is said to be an alternating permutation.

Denote {\mathcal{A}}_n as a set comprised of all alternating permutations on \left[n\right]. The enumeration result of length-n alternating permutation is an Euler number E_n, with its exponential generating function satisfying

\sum _{n=0}^{\mathrm{\infty }}{E}_n\frac{x^n}{n!}=\mathrm{s}\mathrm{e}\mathrm{c}x+\mathrm{t}\mathrm{a}\mathrm{n}x.

Mansour [48] used the block decomposition method to obtain \left|{\mathcal{A}}_{2n}\right|=C_n. Later, Lewis [43] concluded that the enumeration results of alternating permutations avoiding any length-3 pattern are related to C_n. He established the bijection between {\mathcal{S}}_n\left(132\right) and {\mathcal{A}}_{2n+1}\left(132\right), and for the first time, he studied the enumeration problem of alternating permutations avoiding length-4 patterns [44]. Lewis [45] established the bijection between {\mathcal{A}}_{2n}\left(1234\right),{\mathcal{A}}_{2n}\left(2143\right) and standard Young tableaux of shape ⟨n,n,n⟩ by constructing a spanning tree, and obtained

\left|{\mathcal{A}}_{2n}\left(1234\right)\right|=\left|{\mathcal{A}}_{2n}\left(2143\right)\right|=\frac{2\cdot \left(3n\right)!}{n!\left(n+1\right)!\left(n+2\right)!}.

Meanwhile, Lewis [45] established the bijection between {\mathcal{A}}_{2n+1}\left(2143\right) and standard Young Tableaux of shape ⟨n+2,n+1,n⟩, and obtained

\left|{\mathcal{A}}_{2n+1}\left(2143\right)\right|=\frac{2\left(3n+3\right)!}{n!\left(n+1\right)!\left(n+2\right)!\left(2n+1\right)\left(2n+2\right)\left(2n+3\right)}.

Besides, Lewis [45] also gave the following conjectures.

Conjecture 2.1　 For n\ge 1, any p\in \{1243,2134,1432,3214,2341,4123,3421,4312\}, there exists

\left|{\mathcal{A}}_{2n}\left(p\right)\right|=\left|{\mathcal{A}}_{2n}\left(1234\right)\right|=\left|{\mathcal{A}}_{2n}\left(2143\right)\right|.

Conjecture 2.2　 For n\ge 0, anyp\in \{2134,4312,3214,4132\}, there exists

\left|{\mathcal{A}}_{2n+1}\left(p\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(1234\right)\right|.

Conjecture 2.3　 For n\ge 0, any p\in \{1243,3421,1432,2341\}, there exists

\left|{\mathcal{A}}_{2n+1}\left(p\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(2143\right)\right|.

Conjecture 2.4　 If permutations p and q are Wilf equivalent on any {\mathcal{A}}_n, then they are Wilf equivalent on any {\mathcal{S}}_n.

The above Conjectures 2.1‒2.3 have been fully resolved in recent years. Xu and Yan [69] established the bijection between {\mathcal{A}}_{2n}\left(4123\right) and standard Young tableaux of shape ⟨n+2,n,n-2⟩, as well as the bijection between {\mathcal{A}}_{2n+1}\left(4123\right) and standard Young tableaux of shape⟨n+1,n,n-1⟩ by constructing a spanning tree, proving

\begin{array}{rl}& \left|{\mathcal{A}}_{2n}\left(4123\right)\right|=\left|{\mathcal{A}}_{2n}\left(1234\right)\right|=\left|{\mathcal{A}}_{2n}\left(1432\right)\right|,\\ & \left|{\mathcal{A}}_{2n+1}\left(4123\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(1234\right)\right|,\\ & \left|{\mathcal{A}}_{2n+1}\left(1432\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(2143\right)\right|.\end{array}

By constructing a spanning tree, Bóna [8, 9] proved

\begin{array}{rl}& \left|{\mathcal{A}}_{2n}\left(1234\right)\right|=\left|{\mathcal{A}}_{2n}\left(1243\right)\right|,\\ & \left|{\mathcal{A}}_{2n}\left(12345\right)\right|=\left|{\mathcal{A}}_{2n}\left(12354\right)\right|,\\ & \left|{\mathcal{A}}_{2n+1}\left(1234\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(2134\right)\right|;\end{array}

and further obtained

\begin{array}{rl}& \left|{\mathcal{A}}_{2n}\left(12\dots k\right)\right|=\left|{\mathcal{A}}_{2n}\left(12\dots k(k-1)\right)\right|,\\ & \left|{\mathcal{A}}_n\left(12\dots k\right)\right|=\left|{\mathcal{A}}_n\left(21\dots (k-1)k\right)\right|.\end{array}

Chen et al. [21] proved by constructing a spanning tree

\begin{array}{rl}& \left|{\mathcal{A}}_{2n+1}\left(1243\right)\right|=\left|{\mathcal{A}}_{2n+1}\left(2143\right)\right|,\\ & \left|{\mathcal{A}}_{2n}\left(4312\right)\right|=\left|{\mathcal{A}}_{2n}\left(1234\right)\right|.\end{array}

Lewis [45] also raised the following problems, which remain open to date.

Problem 2.1　Is there any other large pattern family that can be proved to be Wilf equivalent on alternating permutations?

Definition 2.2　Given a permutation \sigma, if for all i\in \{k,2k,\dots \}, {\sigma }_i>{\sigma }_{i+1} is satisfied, that is, the descending set is \{k,2k,\dots \}, then the set comprised of permutations \sigma is {\text{Des}}_{n,k}.

Problem 2.2　Can pattern avoidance be studied on {\mathrm{D}\mathrm{e}\mathrm{s}}_{n,k}? On such a permutation set, can it be proved that there exists an equivalent pattern pair or family?

Definition 2.3　If alternating permutation \sigma satisfies \sigma ={\sigma }^{-1}, it is said to be an alternating involutory permutation.

Denote \mathcal{A}{\mathcal{J}}_n as a set comprised of all alternating permutations on \left[n\right]. Barnabei et al. [4] studied the pattern-avoiding enumeration problem on alternating involutory permutations and yielded relevant results, as seen in Theorem 2.1.

Theorem 2.1　 For any permutation \tau on \{3,\dots ,m\}, there exists

\left|{\mathcal{A}\mathcal{J}}_n\left(12\tau \right)\right|=\left|{\mathcal{A}\mathcal{J}}_n\left(21\tau \right)\right|.

And for any permutation \tau on \{1,\dots ,k-2\}, there exists

\left|{\mathcal{A}\mathcal{J}}_{2n}\left(\tau \left(k-1\right)k\right)\right|=\left|{\mathcal{A}\mathcal{J}}_{2n}\left(\tau k\left(k-1\right)\right)\right|.

The results of avoiding single length-4 patterns on alternating involutory permutations are mostly related to the Motzkin number, while the results of avoiding double length-4 patterns are related to the Fibonacci number and power of 2. In addition, Barnabei et al. [4] proposed the following Conjectures 2.5 and 2.6.

Conjecture 2.5　 For n\ge 1, there exists

\left|{\mathcal{A}\mathcal{J}}_{2n}\left(1432\right)\right|=\left|{\mathcal{A}\mathcal{J}}_{2n+1}\left(1432\right)\right|=\left|{\mathcal{A}\mathcal{J}}_{2n}\left(3214\right)\right|,

and

\left|{\mathcal{A}\mathcal{J}}_{2n-1}\left(3214\right)\right|=M_n-M_{n-2},

where M_n is the nth Motzkin number.

Conjecture 2.6　 If \tau is any arbitrary permutation of \{4,\dots ,m\}, where m\ge 4, there exists

\left|{\mathcal{A}\mathcal{J}}_n\left(123\tau \right)\right|=\left|{\mathcal{A}\mathcal{J}}_n\left(321\tau \right)\right|.

Yan et al. [71] proved the above two conjectures and conducted Wilf equivalence classification of avoiding length-4 patterns on alternating involutory permutations.

3 Research on pattern-avoiding enumeration on dumount permutations

There are four kinds of Dumont permutations. The first and second kinds were proposed by Dumont [31]. Burstein and Stromquist [17] proved the Kitaev-Remmel [38, 39] Conjecture by establishing the bijection between {\mathcal{D}}_{2n}^1and {\mathcal{D}}_{2n}^3, defining the relevant permutation set as the third kind of Dumont permutation. They used Foata's fundamental transformation to map the third kind of Dumont permutations onto the permutation set of the same order, hence the fourth kind of Dumont permutation. For convenience, we first give the following definitions.

Definition 3.1　The fixed point (excedance, deficiency) in permutation \pi ={\pi }_1{\pi }_2\dots {\pi }_n refers to location i, which satisfies the condition

Definition 3.2　(1) Permutations where the locations of every even value are descending and the locations of every odd value are ascending or which end with an odd value are referred to as Dumont permutations of the first kind.

(2) Permutations where the locations of every even value are deficiencies, and the locations of every odd value are fixed points or exceedances are referred to as Dumont permutations of the second kind.

(3) Permutations where all descendances are from an even value to an even value are referred to as Dumont permutations of the third kind.

(4) Permutations where all deficiencies must be at locations of even values and correspond to even values are referred to Dumont permutations of the fourth kind.

For 1\le i\le 4, use {\mathcal{D}}_{2n}^i to represent the set comprised of length-2n Dumont permutations of ith kind. Use the G_{2n} to represent nth Genocchi number. Dumont, Burstein and Stromquist [17, 31] obtained

\left|{\mathcal{D}}_{2n}^1\right|=\left|{\mathcal{D}}_{2n}^2\right|=\left|{\mathcal{D}}_{2n}^3\right|=\left|{\mathcal{D}}_{2n}^4\right|=G_{2n+2},

where the exponential generating function of the nth Genocchi number satisfies

\sum _{n=1}^{\mathrm{\infty }}{G}_{2n}\frac{x^{2n}}{\left(2n\right)!}=x\mathrm{t}\mathrm{a}\mathrm{n}\left(\frac{x}{2}\right),\sum _{n=1}^{\mathrm{\infty }}{\left(-1\right)}^n{G}_{2n}\frac{x^{2n}}{\left(2n\right)!}=-x\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\left(\frac{x}{2}\right).

3.1 Research on pattern-avoiding enumeration on {\mathcal{D}}_{2\mathit{n}}^1

Mansour [49] studied the enumeration problem of avoiding single length-3 patterns on {\mathcal{D}}_{2n}^1 for the first time, and obtained by recursion

\left|{\mathcal{D}}_{2n}^1\left(132\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(231\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(312\right)\right|=C_n,\left|{\mathcal{D}}_{2n}^2\left(321\right)\right|=C_n.

Burstein et al. [13] established the bijection between the permutations enumerated by C_n and Dyck paths. Besides, Mansour, Ofodile, and Burstein [16, 50, 58] enumerated the permutations with restricted inclusion of length-3 patterns one time on {\mathcal{D}}_{2n}^1. Burstein [12] studied the enumeration problem of avoiding single length-3 and two length-3 patterns on {\mathcal{D}}_{2n}^1, and obtained

\left|{\mathcal{D}}_{2n}^1\left(213\right)\right|=C_{n-1},\left|{\mathcal{D}}_{2n}^2\left(231\right)\right|=2^{n-1},

and the following theorems.

Theorem 3.1　 For n\ge 2, there exists

\begin{array}{rl}\left|{\mathcal{D}}_{2n}^1\right(132,231\left)\right|& =\left|{\mathcal{D}}_{2n}^1\right(132,312\left)\right|=\left|{\mathcal{D}}_{2n}^1\right(213,312\left)\right|=\left|{\mathcal{D}}_{2n}^1\right(132,213\left)\right|\\ & =\left|{\mathcal{D}}_{2n}^1\right(231,312\left)\right|=\left|{\mathcal{D}}_{2n}^1\right(123,213\left)\right|=\left|{\mathcal{D}}_{2n}^1\right(231,321\left)\right|=1.\end{array}

Burstein [12] further studied the enumeration problem of avoiding two length-4 patterns on {\mathcal{D}}_{2n}^1 , and presented Theorem 3.2 and Theorem 3.3.

Theorem 3.2　 The ordinary generating function G\left(x\right) for {\mathcal{D}}_{2n}^1\left(1423,4132\right) enumeration sequence is

G\left(x\right)=\frac{1-3x-\left(1+x\right)\sqrt{1-4x}}{1-3x-2x^2-\left(1+x\right)\sqrt{1-4x}}.

Theorem 3.3　(1) For n\ge 0, there exists

\begin{array}{rl}& \left|{\mathcal{D}}_{2n}^1\left(1342,1423\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(2341,2413\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(1342,2413\right)\right|=s_{n+1},\\ & \left|{\mathcal{D}}_{2n}^1\left(2413,3142\right)\right|=\sum _{k=0}^{n-1}\frac{n-k}{n+k}\left(\genfrac{}{}{0pt}{}{n+k}{n}\right)2^k+{\delta }_{n=0},\end{array}

namely power of 2 and convolution of Ballot numbers.

\left|{\mathcal{D}}_{2n}^1\left(2413,4132\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(1423,3142\right)\right|,

where s_n is the nth small Schröder number.

(2) For n\ge 1, there exists \left|{\mathcal{D}}_{2n}^1\left(1342,4213\right)\right|=2^{n-1}.

(3) For n\ge 3, there exists \left|{\mathcal{D}}_{2n}^1\left(2341,1423\right)\right|=b_n, where b_n satisfies b_n=3b_{n-1}+2b_{n-2} and b_0=1, b_1=1, b_2=3.

Regarding avoiding single length-4 patterns on {\mathcal{D}}_{2n}^1, Burstein and Jones [14] gave the following Conjecture 3.1 and Conjecture 3.2, which remain open to date.

Conjecture 3.1　 For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^1\left(2143\right)\right|=\left|{\mathcal{D}}_{2n}^1\left(3421\right)\right|.

Definition 3.3

\begin{array}{rl}& a_k=\left|\right\{\pi \in {\mathcal{D}}_{2n}^1\left(2143\right)\left|\right(2\underset{\_}{31})\pi =k\}|,\\ & b_k=\left|\right\{\pi \in {\mathcal{D}}_{2n}^1\left(3421\right)\left|\right(\underset{\_}{13}2)\pi =k\}|,\end{array}

where (2\underset{\_}{31})\pi \left(\right(\underset{\_}{13}2\left)\pi \right) is the occurrence of vincular pattern 2\underset{\_}{31}\left(\underset{\_}{13}2\right)appearing in \pi.

Conjecture 3.2　 For n\ge 0, there exists

\{\begin{array}{ll}{a}_k=b_k=1,& whenk=\left(\begin{array}{c}n\\ 2\end{array}\right)\text{;}\\ a_k=b_k=0,& whenk>\left(\begin{array}{c}n\\ 2\end{array}\right)\text{;}\\ {\displaystyle \sum _{k=0}^m{a}_k\ge {\displaystyle \sum _{k=0}^m{b}_k,}}& when0\le m\le \left(\begin{array}{c}n\\ 2\end{array}\right)\text{.}\end{array}

The condition for the last formula to hold is m=\left(\genfrac{}{}{0pt}{}{n}{2}\right).

3.2 Research on pattern-avoiding enumeration on {\mathcal{D}}_{2\mathit{n}}^2

The foregoing has provided the enumeration results for avoiding patterns 321, 312 and 231 on {\mathcal{D}}_{2n}^2. According to the definition, {\mathcal{D}}_{2n}^2 contains patterns 123, 132, and 213, so the enumeration result for avoiding the three patterns is naturally zero. Hence, we have obtained all enumeration results for avoiding single length-3 patterns on {\mathcal{D}}_{2n}^2. Among the research on avoiding single length-4 patterns on {\mathcal{D}}_{2n}^2, Burstein [12] obtained \left|{\mathcal{D}}_{2n}^2\left(3142\right)\right|=C_n, and Elizalde and Mansour [13] found \left|{\mathcal{D}}_{2n}^2\left(4132\right)\right|=\left|{\mathcal{D}}_{2n}^2\left(321\right)\right|=C_n, along with the following Theorem 3.4.

Theorem 3.4　 For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^2\left(2143\right)\right|=a_n{a}_{n+1},

where

a_{2m}=\frac{1}{2m+1}\left(\genfrac{}{}{0pt}{}{3m}{m}\right),a_{2m+1}=\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{3m+1}{m}\right).

Use {\mathcal{D}}_{2n}^2\left(\tau ;1\right) to indicate a permutation set with restricted inclusion of length-4 pattern \tau once in {\mathcal{D}}_{2n}^2. For \tau \in {\mathcal{D}}_4^2, Ofodile [58] obtained the enumeration result. Burstein and Ofodile [16] obtained the enumeration result of {\mathcal{D}}_{2n}^2\left(2143;1\right), as shown in Theorems 3.5 and 3.6.

Theorem 3.5　 For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^2\left(3142;1\right)\right|=\left(\genfrac{}{}{0pt}{}{2n-1}{n-1}\right).

Theorem 3.6　 For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^2\left(2143;1\right)\right|=a_n{b}_{n+1}+b_n{a}_{n+1}+a_{n-1}{a}_n,

where

a_{2k}=\frac{1}{2k+1}\left(\genfrac{}{}{0pt}{}{3k}{k}\right),b_{2k}=\left(\genfrac{}{}{0pt}{}{3k-3}{k-2}\right).

3.3 Research on pattern-avoiding enumeration on {\mathcal{D}}_{2\mathit{n}}^3

Burstein et al. [15] obtained the following enumeration results of avoiding patterns 231 and 312 on {\mathcal{D}}_{2n}^3.

Theorem 3.7　 For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^3\left(231\right)\right|=\left|{\mathcal{D}}_{2n}^3\left(312\right)\right|=C_n.

Genocchi’s Seidel triangle is a Pascal triangular array of integers {\left(g_{i,j}\right)}_{i,j\ge 1}, a subdivision of the Genocchi number, which satisfies the following recursion:

\{\begin{array}{ll}{g}_{2i+1,j}=g_{2i+1,j-1}+g_{2i,j},& \mathrm{f}\mathrm{o}\mathrm{r}j=1,2,\dots ,i+1,\\ g_{2i,j}=g_{2i,j+1}+g_{2i-1,j},& \mathrm{f}\mathrm{o}\mathrm{r}j=i,i-1,\dots ,1,\end{array}

where g_{1,1}=1 and g_{i,j}=0. If j\le 0,i\le 0, or i>\lceil \frac{j}{2}\rceil. Then

\begin{array}{rl}& g_{2n-1,n-1}=g_{2n-1,n}=g_{2n,n}=G_{2n+2},\\ & g_{2n-1,1}=g_{2n-2,1}=H_{2n-1},\end{array}

where G_{2n} is the nth Genocchi number and H_{2n-1} is the nth central Genocchi number. For {\mathcal{D}}_{2n}^3 and {\mathcal{D}}_{2n}^4, Burstein et al. [15] gave the following conjectures, which remain open to date.

Conjecture 3.3　 In {\mathcal{D}}_{2n}^3, the number of permutations where 2k follows 2n is g_{2n,k}, and the number of permutations where 2k is in front of 2 is g_{2n,n-k+1}.

Conjecture 3.4　 In{\mathcal{D}}_{2n}^4, the number of permutations ending with 2k is g_{2n,k}, and the number of permutations where 2 is at the location of 2k is g_{2n,n-k+1}.

Conjecture 3.5　 In{\mathcal{D}}_{2n}^4, the number of permutations \pi ={\pi }_1{\pi }_2\dots {\pi }_n where {\pi }_{2n}=2 and m\in \left[n-1\right] satisfies the condition that the minimal integer of {\pi }_{2m+1}=2m+2 is g_{2n-1,m}, and the number of permutations \pi where {\pi }_{2n}=2 without such m\in \left[n-1\right] that {\pi }_{2m+1}=2m+2 is g_{2n-1,n-1}.

3.4 Research on pattern-avoiding enumeration on {\mathcal{D}}_{2\mathit{n}}^4

Burstein and Jones [14] studied the pattern avoidance on {\mathcal{D}}_{2n}^4. When n\ge 4, it can be seen from the definition that {\mathcal{D}}_{2n}^4 contains pattern 1234 in {\mathcal{D}}_4^4, so the enumeration result of avoiding this pattern is naturally zero. The enumeration result of avoiding other patterns in {\mathcal{D}}_4^4 is as shown in the following Theorem 3.8.

Theorem 3.8　 For n\ge 1, there exists

\left|{\mathcal{D}}_{2n}^4\left(1342\right)\right|=2^{n-1}.

For n\ge 0, there exists

\left|{\mathcal{D}}_{2n}^4\left(1432\right)\right|=\left|{\mathcal{D}}_{2n}^4\left(321\right)\right|=C_n.

The partial enumeration result for avoiding length-4 patterns except {\mathcal{D}}_4^4 and containing length-3 pattern 321 once on {\mathcal{D}}_{2n}^4 is as follows:

Theorem 3.9　 For n\ge 0, there exists

\begin{array}{rl}& \left|{\mathcal{D}}_{2n}^4\left(1324\right)\right|=\left|{\mathcal{D}}_{2n}^4\left(1243\right)\right|=\left|{\mathcal{D}}_{2n}^4\left(213\right)\right|=2\left(\genfrac{}{}{0pt}{}{n}{2}\right)+1=n^2-n+1,\\ & \left|{\mathcal{D}}_2^4\left(1423\right)\right|-\left|{\mathcal{D}}_2^4\left(312\right)\right|.\end{array}

([14] also provided the ordinary generating function of \left|{\mathcal{D}}_{2n}^4\left(1423\right)\right| in the form of a continued fraction, and obtained the corresponding OEIS sequence for the {\mathcal{D}}_{2n}^4\left(312\right) counting sequence.)

Theorem 3.10　 For n\ge 1, there exists

\left|{\mathcal{D}}_{2n}^4\left(321;1\right)\right|=\frac{3}{n}\left(\genfrac{}{}{0pt}{}{2n}{n-3}\right)+\frac{3}{n+1}\left(\genfrac{}{}{0pt}{}{2n+2}{n-2}\right).

4 Research on pattern-avoiding enumeration on Ballot permutations

Definition 4.1　The prefix of a permutation \sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n refers to a continuous initial subsequence {\sigma }_1{\sigma }_2\cdots {\sigma }_p(1\le p\le n).

Definition 4.2　Given a permutation \sigma \in S_n, if {\sigma }_i>{\sigma }_{i+1}, then i\in \left[n-1\right] is said to be a descent of permutation \sigma. If , then i\in \left[n-1\right] is said to be an ascent of permutation \sigma.

Definition 4.3　Given a permutation \sigma, if the number of descents in any prefix of \sigma is no less than the number of ascents, then the permutation \sigma is said to be a Ballot permutation.

For example, permutation 14325 is not a Ballot permutation because the number of descents (2) is greater than the number of ascents (1) in the prefix 1432.

Definition 4.4　A Gessel walk is constrained to the 1/4 {\mathbb{N}}^2 plane, with each step consisting of a \{\uparrow ,\downarrow ,\nearrow ,\swarrow \} lattice path.

Definition 4.5　For i,j\in \mathbb{N}, denote \mathcal{G}\left(n;0,j\right) as the set comprised of nth Gessel walks from \left(0,i\right) to \left(0,j\right).

Denote {\mathcal{B}}_n as the set of all Ballot permutations on \left[n\right]. Lin et al. [46] first studied the enumeration of avoiding length-3 patterns on Ballot permutations and obtained \left|{\mathcal{B}}_n\left(123\right)\right|=C\left(\lceil \frac{n}{2}\rceil \right) and \left|{\mathcal{B}}_n\left(321\right)\right|=\frac{3}{n+1}\left(\genfrac{}{}{0pt}{}{2n-2}{n-2}\right).

In addition, they concluded that patterns 213 and 312 as well as patterns 132 and 231 are Wilf-equivalent on {\mathcal{B}}_n. They established the bijection between {\mathcal{B}}_n\left(213\right) and Gessel walks with endpoints on the y-axis, and summarized the following two theorems.

Theorem 4.1　 For n\ge 1, there exists

\left|{\mathcal{B}}_n\left(213\right)\right|=\left|{\mathcal{B}}_n\left(312\right)\right|=\sum _{j=0}^n|\mathcal{G}\left(n;0,j\right)|.

Theorem 4.2　 For n\ge 0, there exists

\left|{\mathcal{B}}_n\left(132\right)\right|=\left|{\mathcal{B}}_n\left(231\right)\right|=C\left(\lfloor \frac{n}{2}\rfloor \right)C\left(\lfloor n+\frac{1}{2}\rfloor \right).

They also raised the following problems.

Definition 4.6　For \mathit{m}=\left(m_1,\dots ,m_n\right)\in {\mathbb{N}}^n, denote {\mathcal{G}}_m as the set of multiple permutations comprised of \left\{1^{m_1},2^{m_2},\dots ,n^{m_n}\right\}. For an element \pi in {\mathcal{G}}_m, if for every i,1\le i\le \sum _{i=1}^n m_n, there exists

Then we call this element a Ballot multiple permutation.

Problem 4.1　In{\mathcal{G}}_m, can Ballot multiple permutations be counted for fixed m\in {\mathbb{N}}^n?

Sun [65] further obtained all enumeration results of avoiding two length-3 patterns and three length-3 patterns, concluded the Wilf equivalence of corresponding patterns to {\mathcal{B}}_n\left(132,213\right),{\mathcal{B}}_n\left(213,231\right),{\mathcal{B}}_n\left(231,312\right),{\mathcal{B}}_n\left(132,312\right), established the bijection between {\mathcal{B}}_n\left(132,312\right) and the left factor of the Dyck path, and raised the following problems.

Problem 4.2　Can the enumeration result of Ballot permutations avoiding length-4 patterns be obtained?

Problem 4.3　Can the enumeration result of Ballot multiple permutations avoiding patterns in {\mathcal{S}}_n be obtained?

Problem 4.4　Can the enumeration result of Ballot permutations, whose number of ascents is at least \lambda times over the number of descents, be obtained for avoiding a single lengh-3 pattern or two length-3 patterns?

5 Research on pattern-avoiding enumeration on inversion sequences

The pattern-avoiding enumeration of inversion sequences is a problem related to word enumeration. However, its research methods and results are mostly related to permutation enumeration, which has attracted the attention of scholars in recent years. Therefore, this paper will introduce it.

Definition 5.1　Given a length-n integer sequence e=e_0{e}_1\cdots e_n, if any 0\le i\le n satisfies 0\le e_i\le i, then it is said to be an inversion sequence.

Definition 5.2　Given any length-k word \tau on \left[k\right], if there is a length-k subsequence q in the inversion sequence e that is order isomorphic to the pattern \tau, then the inversion sequence e is said to contain the pattern \tau; otherwise, the inversion sequence e avoids the pattern \tau. Denote {\mathcal{J}}_n as the set composed of all inversion sequences on \left[n\right].

For example, e=01021321\in {\mathcal{J}}_7 contains patterns 120 and 000, corresponding to subsequence 231 and 111 in e, but e avoids pattern 201.

The concept of pattern avoidance in inversion sequences was proposed by Corteel et al. [30] and Mansour and Shattuck [53]. Mansou and Shattuck [53] conducted a systematic study for the first time on the problem of avoiding length-3 patterns without repeating letters in inversion sequences. They presented the enumeration results of avoiding patterns 012, 021, 102, 201, and 210 in inversion sequences and obtained the enumeration results of avoiding pattern 120 in inversion sequences under certain conditions. In addition, Corteel et al. [30] proved that pattern 201 and pattern 210 are Wilf equivalent on {\mathcal{J}}_n, obtained the recursive relationship of {\mathcal{J}}_n(201) and {\mathcal{J}}_n(210) enumeration results, and linked the enumeration results with classical combinatorial numbers, as shown in Theorems 5.1 and 5.2.

Theorem 5.1

(1) For n\ge 1, there exists

\left|{\mathcal{J}}_n\left(012\right)\right|=F_{2n-1}.

(2) For n\ge 1, there exists

\left|{\mathcal{J}}_n\left(021\right)\right|=r_{n-1}.

(3) For n\ge 0, there exists

\left|{\mathcal{J}}_n\left(102\right)\right|=\sum _{m=\lceil \frac{n}{2}\rceil }^n\frac{{\left(-1\right)}^{n-m}}{2m+1}\left(\genfrac{}{}{0pt}{}{3m}{m}\right)\left(\genfrac{}{}{0pt}{}{m}{n-m}\right).

Additionally, the generating function of \left|{\mathcal{J}}_n\left(012\right)\right|is

\sum _{n\ge 1}|{\mathcal{J}}_n\left(012\right)|x^n=\frac{x}{1-x}+\frac{x^2}{\left(1-x\right)\left(1-3x+x^2\right)}=\sum _{n\ge 1}{F}_{2n-1}{x}^n,

the generating function of \left|{\mathcal{J}}_n\left(021\right)\right|is

\sum _{n\ge 1}|{\mathcal{J}}_n\left(021\right)|y^n=\frac{1-y-\sqrt{1-6y+y^2}}{2}=\sum _{n\ge 1}{r}_{n-1}{y}^n,

where F_n is the nth Fibonacci number, and r_n is the nth large Schröder number.

Definition 5.3　For e\in {\mathcal{J}}_n, Let a_1\le a_2\le \cdots \le a_t be a weak maximum sequence of e from left to right, and assume is the sequence of remaining indices in \left[n\right]. Define e^{\mathrm{t}\mathrm{o}\mathrm{p}}=\left(e_{a_1},e_{a_2},\dots ,e_{a_t}\right) and top \left(e\right)=e_{a_t}, define e^{\mathrm{b}\mathrm{o}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{m}}=\left(e_{b_1},e_{b_2},\dots ,e_{b_{n-t}}\right) and bottom \left(e\right)=e_{b_{n-t}}. If every item of e is a weak maximum from left to right, then e^{\text{bottom}} is empty, and here let bottom \left(e\right)=-1.

Theorem 5.2　 For n\ge 0, there exists

\left|{\mathcal{J}}_n\left(201\right)\right|=\left|{\mathcal{J}}_n\left(210\right)\right|={\sum }_{a=0}^{n-1}{\sum }_{b=-1}^{a-1}{\mathcal{T}}_{n,a,b}=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)+{\sum }_{a=0}^{n-1}{\sum }_{b=0}^{a-1}{\mathcal{T}}_{n,a,b},

where {\mathcal{T}}_{n,a,b} is the number of e\in {\mathcal{J}}_n\left(201\right), and e satisfies tan\left(e\right)=a, bottom\left(e\right)=b.

Corteel et al. [30] also studied the problem of avoiding length-3 patterns with repeated letters in inversion sequences, obtained the counting results of avoiding patterns 000, 001, and 011, and proved \left|{\mathcal{J}}_n\left(101\right)\right|=\left|{\mathcal{J}}_n\left(110\right)\right|, as shown in Theorems 5.3 and 5.4.

Theorem 5.3　 For n\ge 1, there exists

\begin{array}{rl}& \left|{\mathcal{J}}_n\left(000\right)\right|=\left|E_{n+1}\right|,\\ & \left|{\mathcal{J}}_n\left(001\right)\right|=2^{n-1},\\ & \left|{\mathcal{J}}_n\left(011\right)\right|=B_n,\end{array}

where E_n is the nth Euler number, and B_n is the nth Bell number, namely the number of all divisions of \left[n\right].

Theorem 5.4　 For n\ge 1, there exists

\left|{\mathcal{J}}_n\left(101\right)\right|=\left|{\mathcal{J}}_n\left(110\right)\right|.

Conjecture 5.1　 Forn\ge 1,0\le k\le n-1, denote d_{n,k} as the number of words with the last element being k-1 in {\mathcal{J}}_n\left(000\right). Then d_{n,k} satisfies the recursive relationship

d_{n,k}=d_{n,k-1}+d_{n-1,n-k}.

Later, Kotsiias et al. [41] used a spanning tree-based algorithm to obtain the function equation of {\mathcal{J}}_n\left(100\right) and {\mathcal{J}}_n\left(201\right) generating functions. Testart [66] obtained the counting results of {\mathcal{J}}_n\left(010\right) by decomposing the inversion sequence.

Martinez and Savage [56] linked the problem of avoiding patterns in inversion sequences with classical combinatorial structures and other pattern-avoiding permutations, providing simpler explanations for some combinatorial sequences than before. For the first time, they redefined length-3 patterns as triples of binary relations and obtained the counting results of inversion sequences avoiding legnth-3 patterns and conjectures about the counting results of {\mathcal{J}}_n\left(021,120\right), namely Theorem 5.5 and Conjecture 5.2.

Theorem 5.5　 For n\ge 1, there exists

\left|{\mathcal{J}}_n\left(201,100\right)\right|={\mathrm{S}\mathrm{B}}_n,

where {\mathrm{S}\mathrm{B}}_n is the nth semi-Baxter number.

Definition 5.4　 {\mathcal{J}}_n\left({\rho }_1,{\rho }_2,{\rho }_3\right) is a set comprised of e\in {\mathcal{J}}_n satisfying the following conditions: there is no such that e_i{\rho }_1{e}_j, e_j{\rho }_2{e}_k, e_i{\rho }_3{e}_k.

For example,

Conjecture 5.2　 For n\ge 1, there exists

Recently, Yan and Lin [70] obtained numerous counting results for inversion sequences avoiding double length-3 patterns, which were related to Fibonacci numbers, powers of 2, Schröder numbers and Bell numbers. They also solved the conjecture by Martinez and Savage [56] about the effect of inversion sequence pattern avoidance on the counting results. Subsequently, Kotsiias et al. [41] used a spanning tree-based algorithm to obtain the spanning tree of pattern pairs {\mathcal{J}}_n\left(000,021\right),{\mathcal{J}}_n\left(100,021\right),{\mathcal{J}}_n\left(110,021\right),{\mathcal{J}}_n\left(102,021\right),{\mathcal{J}}_n(100,012), {\mathcal{J}}_n\left(011,201\right),{\mathcal{J}}_n\left(011,210\right), and {\mathcal{J}}_n\left(120,210\right), and used the kernel function method to get the corresponding counting results’ generating functions and counting sequences.

Hong and Li [36] studied the Wilf equivalence class problem for inversion sequences avoiding length-4 patterns. Kotsireans et al. [41, 54] studied the counting problem of inversion sequences while avoiding pattern 021 and length-4 patterns using the spanning tree method. Lin and Ma [70] proposed the following conjecture on the counting results of the inversion sequence avoiding pattern 0012.

Conjecture 5.3　 For n\ge 1, there exists

\left|{\mathcal{J}}_n\left(0012\right)\right|=1+\sum _{i=1}^{n-1}\left(\genfrac{}{}{0pt}{}{2i}{i-1}\right).

Later, Chern [23] proved the conjecture. Hong and Li [36] proposed the following conjecture on the counting results of the inversion sequence avoiding pattern 0012.

Conjecture 5.4　 LetA_n=\left|{\mathcal{J}}_n\left(0021\right)\right| and A\left(x\right)=\sum _n\ge 1A_n{x}^n, then A\left(x\right) satisfies

\frac{1}{\left(1-A\left(x\right)\right){\left(1+A\left(x\right)\right)}^2}=1-x.

This conjecture has been proved by Chern et al. [24] and Mansour [51] at the same time.

6 Research on enumeration of avoiding vincular patterns on {\mathcal{S}}_{\mathit{n}}

Definition 6.1　Given the pattern \tau ={\tau }_1{\tau }_2\cdots {\tau }_k, some consecutive digits in \tau are underlined as follows:

\underset{\_}{{\tau }_i{\tau }_{i+1}\cdots {\tau }_j}.

If permutation \sigma contains a pattern \tau, the corresponding letters appearing in permutation \sigmamust be adjacent, while there is no adjacent condition for consecutive letters without an underline. This pattern \tau is called a vincular pattern.

For example, permutation \sigma =541326 contains pattern \tau =1\underset{\_}{23} one time, corresponding to the subsequence 126 in \sigma.

The vincular pattern had already appeared in other references before it was formally studied in reference [2]. Simon and Stanton [63] found that patterns 231, 213, 132, and 312 were related to a set of orthogonal polynomials of a generalized Laguerre polynomial. In addition, many permutation statistics could also be described by vincular patterns, such as valley (213 or 312), peak (231 or 132), continuous ascendance (\underset{\_}{123}), and continuous descendance (321). More generally, the continuous ascendance and descendance of length k are 12\cdots k and k\left(k-1\right)\cdots 1, respectively.

6.1 Research on enumeration of permutations avoiding length-3 vincular patterns

Claesson [25] first studied the enumeration problem of avoiding length-3 vincular patterns on {\mathcal{S}}_n, and found that the partial counting results of avoiding two length-3 vincular patterns were related to the Motzkin number, Bessel number, and involution number. At the same time, Claesson obtained the relationship between the partial counting results of avoiding length-3 vincular patterns on S_n and other combinatorial structures.

The counting result of {\mathcal{S}}_n\left(123\right) is a Bell number, indicating that the Stanley-Wilf Conjecture doesn’t hold for the case of vincular patterns, nor does the conjecture by Noonan and Zeilberger [57]. That is, the counting result of avoiding a vincular pattern may not necessarily be polynomially recursive.

Claesson and Mansour extended the results of [25] in [27], providing complete counting results for the two vincular patterns of type (1, 2) or (2, 1), and conjectured the counting results for avoiding three or more vincular patterns of type (1, 2) or (2, 1) on {\mathcal{S}}_n. Bernini et al. [5] proved the partial counting conjecture for avoiding three vincular patterns on {\mathcal{S}}_n. Bernini and Pergola [6] proved the partial counting conjecture for avoiding four, five, and six vincular patterns on {\mathcal{S}}_n. These counting results were related to the Motzkin number, Fibonacci number, binomial coefficient, and power of 2.

6.2 Research on enumeration of permutations avoiding length-4 vincular patterns

Steingrímsson [64] proposed that there were 48 symmetric classes for length-4 vincular patterns on {\mathcal{S}}_n, and through computer experiments, it was speculated that there were at least 24 Wilf equivalent classes. For the counting problem of avoiding length-4 vincular patterns on S_n, the counting results of 7 Wilf classes were known, as described below.

Elizalde and Noy [34] provided exponential generating functions for three consecutive length-4 patterns \underset{\_}{1234},\underset{\_}{1243},\underset{\_}{1342} in seven Wilf equivalence classes.

Kitaev [37] and Elizalde [32] studied patterns \underset{\_}{1234} and \underset{\_}{1324} in two Wilf equivalence classes based on the counting results of avoiding consecutive length-4 patterns on S_n by Elizalde and Noy, and proved that their generation functions were respectively

\mathrm{e}\mathrm{x}\mathrm{p}\left({\displaystyle \frac{\sqrt{3}}{2}}{\int }_0^x{\displaystyle \frac{{\mathrm{e}}^{t/2}\mathrm{d}t}{\mathrm{c}\mathrm{o}\mathrm{s}\left({\displaystyle \frac{\sqrt{3}}{2}}+{\displaystyle \frac{\pi }{6}}\right)}}\right),\mathrm{e}\mathrm{x}\mathrm{p}\left({\int }_0^x{\displaystyle \frac{\mathrm{d}t}{1-{\int }_0^x{\mathrm{e}}^{-u^2/2}\mathrm{d}u}}\right).

Callan [18] proved \left|{\mathcal{S}}_n\left(3\overline{5}241\right)\right|=\left|{\mathcal{S}}_n\left(3142\right)\right|, and gave two recursion formulas for \left|{\mathcal{S}}_n\left(3142\right)\right| [19]. One recursion formula of a_n=\left|{\mathcal{S}}_n\left(3142\right)\right| is as follows:

\begin{array}{rl}& a_n=\sum _{i=0}^{n-1} a_i{c}_{n-i},n\ge 1;\\ & c_n=\sum _{i=0}^{n-1} i{a}_{n-1,i},n\ge 2;\\ & a_{n,k}=\{\begin{array}{l}{\displaystyle \sum _{i=0}^{k-1} a_i{\displaystyle \sum _{j=k-i}^{n-1-i} a_{n-1-i,j},1\le k\le n-1;}}\\ a_{n-1},k=n.\end{array}\end{array}

Callan [20] also obtained:

\left|{\mathcal{S}}_n\left(1\underset{\_}{23}4\right)\right|=\sum _{k=1}^{n}u\left(n,k\right),

where u\left(n,k\right) has the following recursive relationship:

u\left(n,k\right)=u\left(n-1,k-1\right)+k\sum _{j=k}^{n-1}u\left(n-1,j\right) \left(n\ge 1,u\left(0,0\right)=0,u\left(n,0\right)=0\right).

This result turns out an improvement to the \left|{\mathcal{S}}_n\left(1234\right)\right| complex recursion.

Asinowski et al. [1] proved there was a relationship between Baxter permutation set {\mathcal{S}}_n\left(2413,3142\right) and set {\mathcal{S}}_n\left(2143,3412\right), and obtained the counting results and generating function for {\mathcal{S}}_n\left(2\underset{\_}{14}3,3\underset{\_}{4}\underset{\_}{12}\right), as shown in Theorem 6.1.

Theorem 6.1　 The generating function of {\mathcal{S}}_n\left(2\underset{\_}{14}3,3\underset{\_}{4}\underset{\_}{12}\right) is

\sum _{n\ge 1}{x}^{n-1}{\left(1-x\right)}^n{b}_n,

where

b_n=\left|{\mathcal{S}}_n\left(2\underset{\_}{413},3\underset{\_}{142}\right)\right|=\sum _{m=0}^n\frac{2}{n{\left(n+1\right)}^2}\left(\genfrac{}{}{0pt}{}{n+1}{m}\right)\left(\genfrac{}{}{0pt}{}{n+1}{m+1}\right)\left(\genfrac{}{}{0pt}{}{n+1}{m+2}\right)

is the counting result of length-n Baxter permutation. So,

\left|{\mathcal{S}}_n\left(2\underset{\_}{14}3,3\underset{\_}{41}2\right)\right|=\sum _{i=0}^{\lfloor \left(n+1\right)/2\rfloor }{\left(-1\right)}^i\left(\genfrac{}{}{0pt}{}{n+1-i}{i}\right)b_{n+1-i}.

Elizalde [33] obtained the following theorem.

Theorem 6.2

\begin{array}{rl}& \sum _{n\ge 0} \left|{\mathcal{S}}_n\right(1\underset{\_}{23},3\underset{\_}{12},\underset{\_}{3421}\left)\right|x^n=-1+\sum _{k\ge 0} \frac{k(1+kx)x^2}{(1-(k+1\left)x\right){{\displaystyle \prod }}_{j=1}^{k-1} (1-jx)},\\ & \sum _{n\ge 0} \left|{\mathcal{S}}_n\right(1\underset{\_}{23},\underset{\_}{3421}\left)\right|x^n=\sum _{k\ge 0} \frac{(1+kx)x^{k+1}}{(1+x{)}^k(1-kx\left)\right(1-(k+1)x)}.\end{array}

6.3 Research on enumeration of including vincular pattern times

Claesson and Mansour [26] studied the counting problem of {\mathcal{S}}_n that includes vincular patterns 123 and 132 exactly one time, and obtained the following theorem, where {\mathcal{S}}_n^1\left(\tau \right) represents a permutation set containing pattern \tau exactly one time in {\mathcal{S}}_n.

Theorem 6.3　 Assume B_n is the n-th Bell number, for n\ge -1, there exists

\left|{\mathcal{S}}_{n+2}^1\left(1\underset{\_}{23}\right)\right|=2\left|{\mathcal{S}}_{n+1}^1\left(1\underset{\_}{23}\right)\right|+\sum _{k=0}^{n-1}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left[\left|{\mathcal{S}}_{k+1}^1\left(1\underset{\_}{23}\right)\right|+B_{k+1}\right]\left(\left|{\mathcal{S}}_0^1\left(1\underset{\_}{23}\right)\right|=0\right).

Theorem 6.4　 For n\ge 0, there exists

\left|{\mathcal{S}}_{n+1}^1\left(1\underset{\_}{32}\right)\right|=\left|{\mathcal{S}}_n^1\left(1\underset{\_}{32}\right)\right|+\sum _{k=1}^{n-1}\left[\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left|{\mathcal{S}}_k^1\left(1\underset{\_}{32}\right)\right|+\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)B_k\right]\left(\left|{\mathcal{S}}_0^1\left(1\underset{\_}{32}\right)\right|=0\right).

7 Research on enumeration of permutations avoiding barred patterns on {\mathcal{S}}_{\mathit{n}}

Definition 7.1　A length-r barred pattern is a permutation where some digits are underlined. We use {\overline{\mathcal{S}}}_r to represent the set of all barred patterns with a length ofr.

For example, {\overline{\mathcal{S}}}_1=\{1,\overline{1}\},{\overline{\mathcal{S}}}_2=\{12,\overline{1}2,1\overline{2},\overline{12},21,\overline{2}1,2\overline{1},\overline{21}\}. 24153 and 31524 are barred patterns in {\overline{\mathcal{S}}}_5.

Definition 7.2　For \overline{\tau }\in \overline{\mathcal{S}}_r, where \tau is the pattern obtained by removing all the overlines in \overline{\tau }. Define {\tau }^{\prime } as the pattern obtained by removing all underlined digits and simplifying them.

For example, if \overline{\tau }=53214, then \tau=53214 and {\tau }^{\prime }=312.

Definition 7.3　Given a permutation \pi and pattern \overline{\tau }, if each occurrence of {\tau }^{\prime } in \pi is a part of the occurrence of \tau in \pi, then permutation \pi is called pattern \overline{\tau } avoiding.

For example, permutation \pi =1625374 avoids pattern \overline{\tau }=4132, because the corresponding subsequences of {\tau }^{\prime }=321 in \pi are 635 and 645, which are part of subsequences 6253 and 6254, corresponding to the pattern \tau =4132 in \pi.

The counting result of {\mathcal{S}}_n avoiding length-1 and length-2 barred patterns is trivial, and the counting result of avoiding length-3 barred patterns with 3 digits all overlined is n!-\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right). In addition, the counting result of avoiding other length-3 barred patterns with 1 digit overlined is 1 and \left(n-1\right)!.

Callan [18] and Pudwell [59] studied all length-4 patterns with 1 digit overlined, and obtained the following theorems.

Theorem 7.1　 For p\in \{1\overline{4}23,134\overline{2},23\overline{1}4,\overline{2}431,\overline{3}124,32\overline{4}1,4\overline{1}32,421\overline{3},2\overline{4}13,24\overline{1}3,24\overline{1}3,241\overline{3}, \overline{3}142,3\overline{1}42,31\overline{4}2,314\overline{2}\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=B_n,

where B_n is the nth Bell number.

Theorem 7.2　 For p\in \{\overline{1}432,234\overline{1},23\overline{1}4,\overline{4}123\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=\left(n-1\right)!+\sum _{j=2}^n\frac{\left(n-2\right)!}{\left(j-2\right)!}+\sum _{i=3}^n\sum _{j=2}^{n-i+2}\sum _{l=j+i-2}^n\frac{\left(n-i\right)!\left(l-j-1\right)!}{\left(l-i\right)!\left(i-3\right)!}.

Theorem 7.3　 For p\in \{\overline{1}432,\overline{1}342,231\overline{4},2\overline{4}31,312\overline{4},324\overline{1},\overline{4}132,\overline{4}213,\overline{1}324,132\overline{4},423\overline{1},\overline{4}231\}, there exists

\left|{\mathcal{S}}_n\left(p\right)\right|=\sum _{i=1}^n\left(n-i\right)!\left|{\mathcal{S}}_{i-1}\left(p\right)\right|.

Elizalde [33] studied the counting problem of simultaneously avoiding vincular patterns and barred patterns and obtained the following theorem.

Theorem 7.4　 For n\ge 1, there exists

\left|{\mathcal{S}}_n\right(213,\overline{2}\underset{\_}{3}\underset{\_}{1}\left)\right|=M_{n-1},

where M_{n-1} is the (n-1)-th Motzkin number.

In addition, Pudwell [59] obtained |{\mathcal{S}}_n(1\overline{4}23)|=\left|{\mathcal{S}}_n\left(123\right)\right|, Chen et al. [22] got {\mathcal{S}}_n(321, 3\overline{1}42\left)\right|=M_n, Bousquet-Mélou and Butler [10] reached |{\mathcal{S}}_n(4231,45\overline{3}12)|=\left|{\mathcal{S}}_n\left(4231,3412\right)\right|, and combined with \left|{\mathcal{S}}_n\left(2413\right)\right|=\left|{\mathcal{S}}_n\left(3412\right)\right|to obtain the following theorem.

Theorem 7.5　 For n\ge 1, there exists

\left|{\mathcal{S}}_n\left(2\underset{\_}{41}3\right)\right|=\left|{\mathcal{S}}_n\left(\underset{\_}{341}2\right)\right|=\left|{\mathcal{S}}_n\left(21\overline{3}54\right)\right|.

Bousquet-Mélou and Claesson [11] also got the counting result of {\mathcal{S}}_n avoiding 3\overline{1}52\overline{4}, and obtained the following theorem.

Theorem 7.6　 For n\ge 1, there exists

\left|{\mathcal{S}}_n\left(3\overline{1}52\overline{4}\right)\right|=\sum _{k=1}^n\left(\genfrac{}{}{0pt}{}{\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)+n-k-1}{n-k}\right).

The kth item of the above sum contains k counting results of minimum permutations from right to left, hence solving Pudwell's conjecture [59]. At the same time, the generating function corresponding to the above result is

\sum _{n\ge 0}|{\mathcal{S}}_n\left(3\overline{1}52\overline{4}\right)|x^n=\sum _{k\ge 1}\frac{x^k}{\left(1-x\right)\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)}.

References

[1] Asinowski A, Barequet G, Bousquet-Mélou M, Mansour T, Pinter R Y. Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations. Electron J Combin 2013; 20(2): 35

[2] Babson E, Steingrímsson E. Generalized permutation patterns and a classification of the Mahoniar statistics. Sém Lothar Combin 2000; 44: B44b

[3] Backelin J, West J, Xin G C. Wilf-equivalence for singleton classes. Adv in Appl Math 2007; 38(2): 133–148

[4] Barnabei M, Bonetti F, Castronuovo N, Silimbani M. Pattern avoiding alternating involutions. Enumer Comb Appl 2023; 3(1): S2R4

[5] Bernini A, Ferrari L, Pinzani R. Enumerating permutations avoiding three Babson-Steingrímssont patterns. Ann Comb 2005; 9(2): 137–162

[6] Bernini A, Pergola E. Enumerating permutations avoiding more than three Babson-Steingrímsson Patterns. J Integer Seq 2007; 10(6): 07.6.4

[7] Bóna M. Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J Combin Theory Ser A 1997; 80(2): 257–272

[8] Bóna M. New records in Stanley-Wilf limts. European J Combin 2007; 28(1): 75–85

[9] Bóna M. On a family of conjectures of Joel Lewis on alternating permutations. Graphs Combin 2014; 30(3): 521–526

[10] Bousquet-Mélou M, Butler S. Forest-like permutations. Ann Combin 2007; 11(3/4): 335–354

[11] Bousquet-Mélou M, Claesson A, Dukes M, Kitaev S. (2+2)-free posets, ascent sequences and patterm avoiding permutations. J Combin Theory Ser A 2010; 117(7): 884–909

[12] Burstein A. Restricted Dumont permutations. Ann Comb 2005; 9(3): 269–280

[13] Burstein A, Elizalde S, Mansour T. Restricted Dumont permutations, Dyck paths, and noncrossing partitions. Discrete Math 2006; 306(22): 2851–2869

[14] Burstein A, Jones O. Enumeration of Dumont permutations avoiding certain four-letter patterns. Discrete Math Theor Comput Sci 2021/2022; 22(2): 7

[15] Burstein A, Josuat-Vergès M, Stromquist W. New Dumont permutations. Pure Math Appl (PU M A) 2010; 21(2): 177–206

[16] BursteinAOfodileC. Dumont permutations containing one occurrence of certain three- and four- letter patterns. In: 9th International Conference on Permutation Patterns, June 20‒24, 2011, Sam Luis Obispo, CA

[17] BursteinAStromquistW. Dumont permutations of the third kind. In: 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 20077), July, 2007, Tianjin

[18] CallanD. A Wilf equivalence related to two stack sortable permutations. 2005, arXiv: math/0510211

[19] Callan D. A combinatorial interpretation of the eigensequence for composition. J Integer Seq 2006; 9(1): 06.1.4

[20] CallanD. A bijection to count (1-23-4)-avoiding permutations. 2010

[21] Chen J N, Chen Y C, W R D P. On pattern avoiding alternating permutations. European J Combin 2014; 40: 11–25

[22] Chen W Y C, Deng E Y P, Yang L L M. Riordan paths and derangements. Discrete Math 2008; 308(11): 2222–2227

[23] Chern S. On 0012-avoiding inversion sequences and a conjecture of Lin and Ma. Quaest Math 2023; 46(4): 681–694

[24] Chern S, Fu S, Lin Z. Burstein’s permutation conjecture, Hong and Li’s inversion sequence conjecture and restricted Eulerian distributions. Proc Edinb Math Soc (2) 2023; 66(4): 1179–1201

[25] Claesson A. Generalized pattern avoidance. European J Combin 2001; 22(7): 961–971

[26] Claesson A, Mansour T. Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations. Adv Appl Math 2002; 29(2): 293–310

[27] Claesson A, Mansour T. Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns. Ars Combin 2005; 77: 17–31

[28] Conway A R, Guttmann A J. On 1324-avoiding permutations. Adv Appl Math 2015; 64: 50–69

[29] Conway A R, Guttmann A J, Zinn-Justin P. 1324-avoiding permutations revisited. Adv Appl Math 2018; 96: 312–333

[30] Corteel S, Martinez M A, Savage C D, Weselcouch M. Patterns in inversion sequences I. Discret Math Theor Comput Sci 2016; 18(2): 2

[31] Dumont D. Interprétations combinatoires des nombres de Genocchi. Duke Math J 1974; 41: 305–318

[32] Elizalde S. Asymptotic enumeration of permutations avoiding generalized patterns. Adv Appl Math 2006; 36(2): 138–155

[33] Elizalde S. Generating trees for permutations avoiding generalized patterns. Ann Comb 2007; 11(3/4): 435–458

[34] Elizalde S, Noy M. Consecutive patterns in permutations. Adv Appl Math 2003; 30(1/2): 110–125

[35] Gessel I M. Symmetric functions and P-recursiveness. J Combin Theory Ser A 1990; 53(2): 257–285

[36] Hong L T, Li R. Length-four pattern avoidance in inversion sequences. Electron J Combin 2022; 29(4): 4.37

[37] Kitaev S. Partially ordered generalized patterns. Discrete Math 2005; 298(1/2/3): 212–229

[38] Kitaev S, Remmel J. Classifying descents according to equivalence mod k. Electron J Combin 2006; 13(1): 64

[39] Kitaev S, Remmel J. Classifying descents according to parity. Ann Combin 2007; 11(2): 173–193

[40] KnuthD E. The Art of Computer Programming, Vol 3, Sorting and Searching, Reading. MA: Addison-Wesley, 1973

[41] Kotsireas I, Mansour T, Yıldırım G. An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences. J Symbolic Comput 2024; 120: 102231

[42] Kremer D, Shiu W C. Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math 2003; 268(1/2/3): 171–183

[43] Lewis J B. Alternating, pattern-avoiding permutations. Electron J Combin 2009; 16(1): Note 7, 8

[44] Lewis J B. Pattern avoidance for alternating permutations and Young tableaux. J Combin Theory Ser A 2011; 118(4): 1436–1450

[45] Lewis J B. Generating trees and pattern avoidance in alternating permutations. Electron J Combin 2012; 19(1): 21, 21

[46] Lin Z C, Wang D G L, Zhao T Y. A decomposition of ballot permutations, pattern avoidance and Gessel walks. J Combin Theory Ser A 2022; 191: 105644

[47] MacMahonP A. Combinatory Analysis, Volumes I, II. Mineola, NY: Dover Publications, Inc, 2004

[48] Mansour T. Restricted 132-alternating permutations and Chebyshev polynomials. Ann Comb 2003; 7(2): 201–227

[49] Mansour T. Restricted 132-Dumont permutations. Australas J Combin 2004; 29: 103–117

[50] Mansour T. The enumeration of permutations whose posets have a maximum element. Adv Appl Math 2006; 37(4): 434–442

[51] Mansour T. Generating trees for 0021-avoiding inversion sequences and a conjecture of Hong and Li. Discrete Math Lett 2023; 12: 11–14

[52] MansourTNassauC. On Stanley-Wilf limit of the pattern 1324. Adv Appl Math, 2021: 130

[53] Mansour T, Shattuck M. Pattern avoidance in inversion sequences. Pure Math Appl (PU M A) 2015; 25(2): 157–176

[54] MansourTYıldırımG. Inversion sequences avoiding 021 and another pattern of length four. 2023

[55] Marcus A, Tardos G. Excluded permutation matrices and the Stanley-Wilf conjecture. J Combin Theory Ser A 2004; 107(1): 1531160

[56] Martinez M, Savage C. Patterns in inversion sequences II: inversion sequences avoiding triples of relations. J Integer Seq 2018; 21(2): 18.2.2

[57] Noonan J, Zeilberger D. The enumeration of permutations with a prescribed number of “forbidden” patterns. Adv Appl Math 1996; 17(4): 381–407

[58] OfodileC O. The enumeration of Dumont permutations with few occurrences of three and four letter patterns. Ph D Thesis. Washington, DC: Howard University, 2011

[59] PudwellL. Enumeration schemes for words avoiding permutations. In: Permutation Patterns, London Math Soc Lecture Note Ser, Vol 376. Cambridge: Cambridge University Press, 2010, 193–211

[60] Regev A. Asymptotic values for degrees associated with strips of Young diagrams. Adv Math 1981; 41(2): 115–136

[61] Reifegerste A. A generalization of Simion-Schmidt’s bijection for restricted permutations. Electron J Combin 2003; 9(2): 14

[62] Simion R, Schmidt F W. Restricted permutations. European J Combin 1985; 6(4): 383–406

[63] Simion R, Stanton D. Octabasic Laguerre polynomials and permutation statistics. J Comput Appl Math 1996; 68(1/2): 297–329

[64] SteingrímssonE. Generalized permutation patterns—a short survey. In: Permutation Patterns, London Math Soc Lecture Note Ser, Vol 376. Cambridge: Cambridge University Press, 2010, 137–152

[65] Sun N. A complete enumeration of ballot permutations avoiding sets of small patterns. Enumer Comb Appl 2023; 3(1): S2R6

[66] TestartB. Inversion sequences avoiding the pattern 010. 2022, arXiv:2212.07222

[67] WestJ. Permutations with forbidden subsequences and stack-sortable permutations. Ph D Thesis. Cambridge, MA: Massachusetts Institute of Technology, 1990

[68] West J. Generating trees and the Catalan and Schröder numbers. DiscreteMath 1995; 146(1/2/3): 247–262

[69] Xu Y X, Yan S H F. Alternating permutations with restrictions and standard Young tableaux. Electron J Combin 2012; 19(2): 49

[70] Yan C Y, Lin Z C. Inversion sequences avoiding pairs of patterns. Discrete Math Theor Comput Sci 2020/2021; 22(1): 23

[71] Yan S H F, Wang L T, Zhou R D P. On refinements of Wilf-equivalence for involutions. J Algebraic Combin 2023; 58(1): 69–94

RIGHTS & PERMISSIONS

Higher Education Press 2024