ABSTRACT
Most, however, date the study of permutation classes to 1968, when Knuth published Volume 1 of The Art of Computer Programming [118]. In Section 2.2.1 of that book, Knuth introduced sorting with stacks and double-ended queues (deques), which leads naturally to the notion of permutation patterns. In particular, Knuth observed that a permutation can be sorted by a stack if and only if it avoids 231 and showed that these permutations are also counted by the Catalan numbers. He inspired many subsequent papers, including those of Even and Itai [85] in 1971, Tarjan [156] in 1972, Pratt [140] in 1973, Rotem [145] in 1975, and Rogers [144] in 1978.
