Pattern-restricted permutations composed of 3-cycles (Q2138988)

The authors enumerate permutations that are comprised solely of (disjoint) \(3\)-cycles and avoid one or more patterns of length \(3\). Since such permutations must have length (defined as the number of symbols permuted in this area) divisible by \(3\), the formulas are given for permutations of length \(3n\). By symmetry, there are only four patterns of length \(3\) to consider, \(231\), \(132\), \(321\), and \(123\), although this last case is trivial (there are no such permutations of length \(9\) or greater). It is proved that the number of \(231\)-avoiding permutations of length \(3n\) that are comprised solely of \(3\)-cycles is \(3^{n-1}\), and more complicated enumerative results are given for the other two nontrivial cases. For the \(132\)-avoiding case, the enumeration is expressed as a summation involving Motzkin and Catalan numbers, while in the \(321\)-avoiding case, the number of permutations is expressed as a weighted sum involving Dyck path statistics. For some context, involutions can be characterized as permutations comprised of \(1\)- and \(2\)-cycles, and pattern-avoidance in involutions has been considered almost since the beginning of the study of pattern-avoidance, see [\textit{R. Simion} and \textit{F. W. Schmidt}, Eur. J. Comb., 6, 383--406 (1985; Zbl 0615.05002)] for initial investigations and [\textit{M. Bóna et al.}, Australas. J. Comb. 64, Part 1, 88-119 (2016; Zbl 1333.05018)] for later work. The interest in pattern-avoiding permutations with other cycle structures arose later. At the end of their paper, \textit{M. Bóna} and \textit{R. Smith} [Discrete Math., 342, 11, 3194--3200 (2019; Zbl 1419.05006)] asked for the enumeration of \(132\)-avoiding permutations of length \(n\) and order \(3\) (meaning they are comprised of \(1\)- and \(3\)-cycles), though the first actual result on pattern-avoiding permutations of order \(3\) was obtained by \textit{A. Burcroff} and \textit{C. Defant} [Discrete Math., 343, 11, 1--11 (2020; Zbl 1447.05002)], who enumerated the \(231\)-avoided permutations of order \(3\).