Pattern avoidance in permutations: Linear and cyclic orders (Q1422119)

The author extends the concept of pattern avoidance to cyclically ordered sets. This modification allows circular shifts in the values and/or the positions of a permutation. In both cases, the enumeration problem for all patterns of length up to 4 is dealt with. Using Krattenthaler's bijections between pattern-avoiding permutations and Dyck paths, the author shows the correspondence between two classes of pattern-avoiding cyclic arrangements and classes of Dyck paths (non-decreasing Dyck paths, first considered by Barcucci et al., and Dyck paths having at most one long vertical or horizontal edge). Both of these path classes can also be linked with examples of simultaneous pattern avoidance in the classical (linear) case. The study of some of their parameters yields results on the distribution of certain statistics on 321-avoiding permutations. In particular, the number of 321-avoiding permutations with precisely \(k\) descents is given.