Skip to Main content Skip to Navigation
Conference papers

Pattern avoidance in alternating permutations and tableaux (extended abstract)

Abstract : We give bijective proofs of pattern-avoidance results for a class of permutations generalizing alternating permutations. The bijections employed include a modified form of the RSK insertion algorithm and recursive bijections based on generating trees. As special cases, we show that the sets $A_{2n}(1234)$ and $A_{2n}(2143)$ are in bijection with standard Young tableaux of shape $\langle 3^n \rangle$. Alternating permutations may be viewed as the reading words of standard Young tableaux of a certain skew shape. In the last section of the paper, we study pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape $\lambda / \mu$ whose reading words avoid $213$ is a natural $\mu$-analogue of the Catalan numbers. Similar results for the patterns $132$, $231$ and $312$.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01186309
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 24, 2015 - 3:49:27 PM
Last modification on : Tuesday, March 7, 2017 - 3:12:25 PM
Long-term archiving on: : Wednesday, November 25, 2015 - 6:12:36 PM

File

dmAN0123.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01186309, version 1

Collections

Citation

Joel Brewster Lewis. Pattern avoidance in alternating permutations and tableaux (extended abstract). 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. pp.391-402. ⟨hal-01186309⟩

Share

Metrics

Record views

117

Files downloads

791