Generate pattern-avoiding permutations

Given two permutations $\pi=(a_1,\ldots,a_n)$ and $\tau=(b_1,\ldots,b_k)$, we say that $\pi$ contains the pattern $\tau$, if there is a subsequence $(a_{i_1},a_{i_2},\ldots,a_{i_k})$ of $\pi$, where $i_1\lt i_2\lt \cdots\lt i_k$, whose entries appear in the same relative order as $(b_1,\ldots,b_k)$. An occurrence of such a subsequence is referred to as a match of $\tau$ in $\pi$. Otherwise, we say that $\pi$ avoids the pattern $\tau$. For example, the permutation $\pi=451362$ contains the pattern $\tau=2314$, as witnessed by the subsequence $4516$, which is match of $\tau$ in $\pi$, whereas $\pi$ avoids $\tau'=1234$.

By imposing extra conditions for when a pattern matches, this classical notion of pattern-avoidance can be modified in several ways.

• In a vincular pattern [BS00] such as $\tau=2\underline{41}3$, two neighboring entries of $\tau$ are underlined, and a match of $\tau$ in $\pi$ requires that the two underlined entries match adjacent positions in $\pi$.
• In a barred pattern [Wes90] such as $\tau=3\bar{1}42$, one entry of $\tau$ is overlined, and $\pi$ avoids the pattern $\tau$ if every match of the unbarred entries can be extended to a match including the barred entry.
• A match of a boxed pattern [AKV13] such as $\tau=\;$$2143$ in a permutation $\pi$ occurs if in this match, no entry of $\pi$ at a position between the matched ones has a value between the smallest and largest value of the match.
• An even more general notion, which encompasses all the previously mentioned types of patterns as special cases, is that of a mesh pattern [BC11]. A mesh pattern is a pair $(\tau,M)$, where $\tau=(b_1,\ldots,b_k)$ is a permutation and $M$ is a $(k+1)\times (k+1)$ matrix with entries from $\{0,1\}$. Such a mesh pattern can be visualized by considering the grid representation of $\tau$, i.e., the set of points $(i,b_i)$ for $i=1,\ldots,k$ in the plane. All horizontal and vertical lines through these points define a grid with $(k+1)\times (k+1)$ cells, and we shade precisely those grid cells that correspond to 1-entries of $M$. For example, the mesh pattern $(231,M)$ with $M=\begin{pmatrix}0100 \\ 0100 \\ 1111 \\ 0100\end{pmatrix}$ is drawn as .
  A permutation $\pi$ contains a mesh pattern $(\tau,M)$, if the grid representation of $\pi$ contains the grid representation of $\tau$, and no rectangle corresponding to a shaded cell that comes from a 1-entry of $M$ contains a point of $\pi$ in its interior.

By these definitions, a classical pattern is a mesh pattern with no shaded cells, i.e., all entries of $M$ are 0s. A vincular pattern is a mesh pattern with a single column of shaded cells. A barred pattern is a mesh pattern with a single shaded cell. A boxed pattern is a mesh pattern where all cells in the bounding box of the points of $\tau$ are shaded. For more examples and illustrations of these different types of patterns, see [HHMW22] or one of the aforementioned papers where these patterns were introduced.

The paper [HHMW22] proposes a very general and versatile algorithm, called Algorithm J, for generating many different kinds of pattern-avoiding permutations, which works under some very mild constraints on the patterns. A pattern satisfying these constraints is called tame. Specifically, a classical permutation pattern is tame if the largest entry is not at the boundary. For example, $\tau=231$ is tame, but $\tau'=321$ is not tame. For the conditions when a vincular, barred, boxed or mesh pattern is tame, see [HHMW22]. The algorithm developed in [HHMW22] can generate all pattern-avoiding permutations for any Boolean formula $F$ composed of tame patterns of one of the types discussed before, conjunctions $\wedge$ and disjunctions $\vee$. A conjunction expresses that the permutation must avoid both of the patterns, and a disjunction expresses that the permutation must avoid at least one of the patterns. We write $S_n(F)$ for the set of permutations of length $n$ satisfying the constraints expressed by $F$. For example $S_n(231)$ is the set of permutations avoiding $231$, $S_n(231\wedge 132)$ is the set of permutations avoiding both $231$ and $132$, and $S_n(231\vee 132)$ is the set of permutations avoiding $231$ or $132$. A more complicated set that the algorithm can generate would be $S_n(231\wedge (2\underline{41}3\vee 3\bar{1}42))$.

The implementation of Algorithm J running on this website is due to Chigozie Agomo. The input field takes the formula $F$, with the following grammar rules:

conjunction $\wedge$	& (ampersand)
disjunction $\vee$	| (vertical bar)
classical pattern $231$	231 (consecutive digits)
vincular pattern $2\underline{41}3$	24_13 (underscore between the underlined entries)
barred pattern $3\bar{1}42$	3b142 (b before overlined entry)
mesh pattern $(231,M)$ with $M$ as above	231:0100 0100 1111 0100 (pattern, then colon, followed by matrix $M$ row by row from top to bottom)
precedence constraints	231 & (24_13 | 3b142) versus (231 & 24_13) | 3b142 (use parenthesis)

Pattern-avoiding permutations describe and count an abundance of different combinatorial objects, so there is a huge number of OEIS sequences related to them. Some sequences arising from tame patterns that can be generated with this program are listed below.

• none: OEIS A000142 (factorial numbers)
• 231: OEIS A000108 (Catalan numbers)
• 13_2: OEIS A000110 (Bell numbers)
• 132 & 231: OEIS A000079 (powers of 2)
• 2143: OEIS A005802
• 2143 & 3412: OEIS A029759
• 2413 & 3142: OEIS A006318 (Schröder numbers)
• 24_13 & 31_42; 24_13 & 34_12; 21_43 & 31_42: OEIS A001181 (Baxter numbers)
• 21_43 & 34_12: OEIS A214358
• 2413 & 3142 & 2143 & 3412: OEIS A006012
• 2413 & 3142 & 21_43 & 34_12: OEIS A078482
• 35_124 & 35_142 & 245_13 & 425_13: OEIS A342141
• 3b142 & 241b3: OEIS A098569
• 231:0100 0100 1111 0100: OEIS A022493 (Fishburn numbers)

[Zipped C++ source code (GNU GPL)]

• [AKV13] S. Avgustinovich, S. Kitaev, and A. Valyuzhenich. Avoidance of boxed mesh patterns on permutations. Discrete Appl. Math., 161(1-2):43–51, 2013.
• [BC11] P. Brändén and A. Claesson. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electron. J. Combin., 18(2):Paper 5, 14, 2011.
• [BS00] E. Babson and E. Steingrímsson. Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Art. B44b, 18, 2000.
• [HHMW22] E. Hartung, H. P. Hoang, T. Mütze, and A. Williams. Combinatorial generation via permutation languages. I. Fundamentals. Trans. Amer. Math. Soc., 375(4):2255–2291, 2022.
• [Wes90] J. West. Permutations with forbidden subsequences and stack-sortable permutations. ProQuest LLC, Ann Arbor, MI, 1990. Thesis (Ph.D.)–Massachusetts Institute of Technology.