
4
In Any Way but This. Pattern Avoidance.
The Basics.
4.1 The 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