On pattern avoiding alternating permutations

DOI10.1016/J.EJC.2014.01.012MaRDI QIDQ402451zbMATH OpenOpenAlexFDO

Authors Joanna N. Chen, William Y. C. Chen, Robin D. P. Zhou

Publication date 28 August 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.2697

zbMATH Keywords

generating treesWilf-equivalence of alternating permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: An alternating permutation of length $n$ is a permutation $pi=p{i}_{1}p{i}_2\mathrm{...}p{i}_n$ such that $p{i}_1<p{i}_2>p{i}_3<p{i}_4>\mathrm{...}$. Let $A_n$ denote set of alternating permutations of $1,2,\mathrm{...},n$, and let $A_n(sigma)$ be set of alternating permutations in $A_n$ that avoid a pattern $sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by B'ona, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.

Recommendations

• On a family of conjectures of Joel Lewis on alternating permutations
• Generating trees and pattern avoidance in alternating permutations
• Alternating, pattern-avoiding permutations
• Ascent-descent Young diagrams and pattern avoidance in alternating permutations
• Pattern avoidance for alternating permutations and Young tableaux

Cites work

• Alternating permutations with restrictions and standard Young tableaux
• Alternating, pattern-avoiding permutations
• Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux
• Generating trees and pattern avoidance in alternating permutations
• On Wilf equivalence for alternating permutations
• Pattern avoidance for alternating permutations and Young tableaux
• Restricted 132-alternating permutations and Chebyshev polynomials
• The Hook Graphs of the Symmetric Group
• Wilf-equivalence for singleton classes

Cited in

(21)

• Alternating, pattern-avoiding permutations
• Classical length-5 pattern-avoiding permutations
• Wave linked partitions and 312-avoiding permutations with primacy being 1
• On pattern-avoiding Fishburn permutations
• (q, t)-Catalan numbers: gamma expansions, pattern avoidances, and the (-1)-phenomenon
• Pattern avoidance for alternating permutations and Young tableaux
• Avoiding vincular patterns on alternating words
• Pattern-avoiding alternating words
• Pattern avoidance in flattened permutations
• scientific article; zbMATH DE number 5831716 (Why is no real title available?)
• scientific article; zbMATH DE number 5138753 (Why is no real title available?)
• Generating trees and pattern avoidance in alternating permutations
• On the sub-permutations of pattern avoiding permutations
• Sign-imbalance of alternating permutations avoiding a pattern of length three
• Pattern avoiding alternating involutions
• On refinements of Wilf-equivalence for involutions
• Equidistribution of set-valued statistics on standard Young tableaux and transversals
• Vincular pattern avoidance on cyclic permutations
• Combinatorics of exterior peaks on pattern-avoiding symmetric transversals
• Pattern avoidance by even permutations
• Another look at bijections for pattern-avoiding permutations

This page was built for publication: On pattern avoiding alternating permutations

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