ABSTRACT
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 middle one is the largest, and the last one is of medium size. The reader is invited to find a pattern of type 321 in p. On the other hand, there is no pattern of type 12345 in p, therefore we will say that p avoids 12345. The notion of pattern avoidance is at the center of this entire chapter, so
we will make it formal.
