Subsequence containment by involutions (Q1773206)

Summary: Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in \({\mathcal S}_{n}\) which contain a given permutation \(\tau\in{\mathcal S}_{k}\) as a subsequence; this number depends on the patterns of the first \(j\) values of \(\tau\) for \(1\leq j\leq k\). We then use this to define a partition of \({\mathcal S}_{k}\), analogous to Wilf-classes in the study of pattern avoidance, and examine properties of this equivalence. In the process, we show that a permutation \(\tau_1\ldots\tau_k\) is layered if and only if, for \(1\leq j\leq k\), the pattern of \(\tau_1\ldots\tau_j\) is an involution. We also obtain a result of Sagan and Stanley counting the standard Young tableaux of size \(n\) which contain a fixed tableau of size \(k\) as a subtableau.