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)

• On the sub-permutations of pattern avoiding permutations
• Combinatorics of exterior peaks on pattern-avoiding symmetric transversals
• Equidistribution of set-valued statistics on standard Young tableaux and transversals
• Classical length-5 pattern-avoiding permutations
• On pattern-avoiding Fishburn permutations
• On refinements of Wilf-equivalence for involutions
• Avoiding vincular patterns on alternating words
• Pattern-avoiding alternating words
• Vincular pattern avoidance on cyclic permutations
• Pattern avoidance by even permutations
• Another look at bijections for pattern-avoiding permutations
• Alternating, pattern-avoiding permutations
• \((q, t)\)-Catalan numbers: gamma expansions, pattern avoidances, and the \((-1)\)-phenomenon
• Generating trees and pattern avoidance in alternating permutations
• 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?)
• Sign-imbalance of alternating permutations avoiding a pattern of length three
• Pattern avoidance for alternating permutations and Young tableaux
• Pattern avoiding alternating involutions
• Wave linked partitions and 312-avoiding permutations with primacy being 1

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)