# Generate pattern-avoiding permutations

Generate all permutations of the set $\{1,2,\ldots,n\}$ avoiding certain patterns.
 Size $n$ of ground set (max. 12) Forbidden patterns(max. length 6 for each) Predefined inputs –none– 231 13_2 132 & 231 (no peaks) 2143 (vexillary) 2143 & 3412 (skew-merged) 2143 & 2413 & 3142 & 3412 (X-shaped) 2413 & 3142 (separable) 24_13 & 31_42 (Baxter) 24_13 & 34_12 (twisted Baxter) 21_43 & 31_42 21_43 & 34_12 2413 & 3142 & 2143 & 3412 2413 & 3142 & 21_43 & 34_12 24_13 & 31_42 & 21_43 & 34_12 35_124 & 35_142 & 245_13 & 425_13 (2-clumped) 3b142 & 241b3 [2143] 231:0100 0100 1111 0100 132 | 231 (24_13 & 31_42) | 231 Output format graphics (≤500 objects) text (≤10000 objects) file (≤100000 objects)
Output  numbering graphics

## Object info

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 [HHMW20] or one of the aforementioned papers where these patterns were introduced.

The paper [HHMW20] 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 [HHMW20]. The algorithm developed in [HHMW20] 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)

## Enumeration (OEIS)

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.