Size $n$ of ground set | (max. 12) | |
Forbidden patterns (max. length 6 for each) |
||
Predefined inputs | ||
Output format | ||
By imposing extra conditions for when a pattern matches, this classical notion of pattern-avoidance can be modified in several ways.
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) |