Subsequence containment by involutions

MaRDI QIDQ1773206zbMATH OpenFDO

Authors Aaron D. Jaggard

Publication date 25 April 2005

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0107130, https://eudml.org/doc/124542, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

partitionpattern avoidancepermutationYoung tableux

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial aspects of representation theory (05E10)

Abstract: Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in S_n which contain a given permutation au in S_k as a subsequence; this number depends on the patterns of the first j values of au for 1<=j<=k. We then use this to define a partition of 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 au_1... au_k is layered iff, for 1<=j<=k, the pattern of au_1... au_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.

Review text

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.

Recommendations

• Restricted 123-involutions
• Counting occurrences of 231 in an involution
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Refined restricted involutions
• On two related questions of Wilf concerning standard Young tableaux

Cited in

(2)

• Skew domino Schensted correspondence and sign-imbalance
• \(q\)-analog of tableau containment

This page was built for publication: Subsequence containment by involutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773206)