Combinatorics of Permutations, 3rd Edition

4In Any Way but This. Pattern Avoidance. The Basics.

DOI: 10.1201/9780429274107-4

4.1 Notion of Pattern Avoidance

In earlier chapters, we have studied inversions of permutations. These were pairs of elements that could be anywhere in the permutation, but always related to each other the same way, that is, the one on the left was always larger.

There is a far-fetching generalization of this notion from pairs of entries to k-tuples of entries. Consider a “long” permutation, such as $p=25641387$, and a shorter one, say $q=132$. We then say that the 3-tuple of entries (2,6,4) in p forms a pattern or subsequence of type 132 because the entries (2,6,4) of p relate to each other as the entries 132 of q do. That is, the first one is the smallest, the ...