Alternating, pattern-avoiding permutations

MaRDI QIDQ1010899zbMATH OpenFDO

Authors Joel Brewster Lewis

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0805.1964, https://eudml.org/doc/129705, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n7.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

132-avoiding permutationsavoiding permutations patternscounting alternating permutations

Mathematics Subject Classification ID

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

Abstract: We study the problem of counting alternating permutations avoiding collections of permutation patterns including 132. We construct a bijection between the set S_n(132) of 132-avoiding permutations and the set A_{2n + 1}(132) of alternating, 132-avoiding permutations. For every set p_1, ..., p_k of patterns and certain related patterns q_1, ..., q_k, our bijection restricts to a bijection between S_n(132, p_1, ..., p_k), the set of permutations avoiding 132 and the p_i, and A_{2n + 1}(132, q_1, ..., q_k), the set of alternating permutations avoiding 132 and the q_i. This reduces the enumeration of the latter set to that of the former.

Review text

Summary: We study the problem of counting alternating permutations avoiding collections of permutation patterns including \(132\). We construct a bijection between the set \(S_n(132)\) of \(132\)-avoiding permutations and the set \(A_{2n + 1}(132)\) of alternating, \(132\)-avoiding permutations. For every set \(p_1, \dots, p_k\) of patterns and certain related patterns \(q_1, \dots, q_k\), our bijection restricts to a bijection between \(S_n(132, p_1, \dots, p_k)\), the set of permutations avoiding \(132\) and the \(p_i\), and \(A_{2n + 1}(132, q_1, \dots, q_k)\), the set of alternating permutations avoiding \(132\) and the \(q_i\). This reduces the enumeration of the latter set to that of the former.

Recommendations

• Generating trees and pattern avoidance in alternating permutations
• On pattern avoiding alternating permutations
• Pattern avoidance in alternating permutations and tableaux (extended abstract)
• Pattern avoidance in alternating sign matrices
• Pattern avoidance for alternating permutations and Young tableaux

Cited in

(19)

• On a family of conjectures of Joel Lewis on alternating permutations
• (q, t)-Catalan numbers: gamma expansions, pattern avoidances, and the (-1)-phenomenon
• Pattern avoidance in alternating sign matrices
• Pattern avoidance for alternating permutations and Young tableaux
• Avoiding vincular patterns on alternating words
• Pattern-avoiding alternating words
• scientific article; zbMATH DE number 5831716 (Why is no real title available?)
• scientific article; zbMATH DE number 5138753 (Why is no real title available?)
• scientific article; zbMATH DE number 1375582 (Why is no real title available?)
• On pattern avoiding alternating permutations
• Generating trees and pattern avoidance in alternating permutations
• Pattern avoidance and Young tableaux
• BIJECTIVITY BETWEEN COIN-STACKS AND PERMUTATIONS AVOIDING 132-PATTERN
• Sign-imbalance of alternating permutations avoiding a pattern of length three
• Pattern avoiding alternating involutions
• On refinements of Wilf-equivalence for involutions
• A bijection for length-5 patterns in permutations
• Equidistribution of set-valued statistics on standard Young tableaux and transversals
• Combinatorics of exterior peaks on pattern-avoiding symmetric transversals

This page was built for publication: Alternating, pattern-avoiding permutations

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