Enumerating Pattern-Avoiding Involutions using Combinatorial Exploration

Abstract

The enumeration of pattern-avoiding permutations has been a popular area of study over the past several decades, but comparatively little attention has been given to the topic of pattern-avoiding involutions. In this paper, we derive the algebraic generating functions of two Wilf-equivalence classes of involutions avoiding a single pattern of length $4$, $\mathrm{A}{\mathrm{v}}^{\mathrm{I}}(2431)$ and $\mathrm{A}{\mathrm{v}}^{\mathrm{I}}(3421)$. We then adapt the Mosaic method, a fast counting algorithm for permutations, to count involutions and apply it to substantially extend the known initial terms of the counting sequences for the remaining two Wilf-equivalence classes avoiding a pattern of length $4$, $\mathrm{A}{\mathrm{v}}^{\mathrm{I}}(1324)$ and $\mathrm{A}{\mathrm{v}}^{\mathrm{I}}(4231)$. Based on these extended sequences, we empirically analyze the asymptotic behavior of the counting sequences of these two classes.