Pattern avoiding permutations

Consider a permutation of the numbers 1 to n. There are n! of these. A permutation P contains a (usually smaller) permutation p if there is a subsequence of elements of P that are in the same relative order as the elements of the pattern p. So the permutation 45123 contains the pattern 312 as the elements 413 (also 412 and 512 and 513) are in the same relative order as 312. A permutation avoids p if it does not contain (in this sense) p. It is interesting to compute the number of patterns of a given length that avoid a pattern or patterns.

Consecutive pattern avoiding permutations

Consecutive pattern avoiding permutations are very similar, but have the extra requirement on containing that the subsequence be consecutive. This means it is easier to avoid a pattern, so there tend to be more of them. One can also have a partially consecutive requirement : a pattern ab-c would require a and b to be consecutive, but c may occur any time after b. We enumerated many of these for On consecutive pattern-avoiding permutations of length 4, 5 and beyond. The enumerations are available for length 3, 4, 5, 6, and for length 4 pairs, divided into apparent Wilf classes, and with occasional easily findable OEIS and EGFs.