Subsequence containment by involutions

Aaron D. Jaggard

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in ${\cal S}_{n}$ which contain a given permutation $\tau\in{\cal 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 ${\cal 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 iff, 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.

Détail

DOI : 10.37236/1911

Classification : 05A05, 05A15, 05E10
Mots-clés : permutation, partition, pattern avoidance, Young tableux