Bijections for Permutation Tableaux

Sylvie Corteel; Philippe Nadeau

doi:10.46298/dmtcs.3632

Sylvie Corteel ; Philippe Nadeau - Bijections for Permutation Tableaux

dmtcs:3632 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3632

Bijections for Permutation TableauxArticle

Authors: Sylvie Corteel ¹; Philippe Nadeau ^2,³

1 Laboratoire de Recherche en Informatique
2 Universität Wien
3 Universität Wien = University of Vienna

In this paper we propose a new bijection between permutation tableaux and permutations. This bijection shows how natural statistics on the tableaux are equidistributed to classical statistics on permutations: descents, RL-minima and pattern enumerations. We then use the bijection, and a related encoding of tableaux by words, to prove results about the enumeration of permutations with a fixed number of 31-2 patterns, and to define subclasses of permutation tableaux that are in bijection with set partitions. An extended version of this work is available in [6].

https://doi.org/10.46298/dmtcs.3632

Source: HAL:hal-01185167v1

Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Section: Proceedings

Published on: January 1, 2008

Imported on: May 10, 2017

Keywords: enumeration,bijections,permutations,tableaux,permutation patterns,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Bibliographic References

29 Documents citing this article

Joanna N. Chen, 2022, Block decomposition and statistics arising from permutation tableaux, arXiv (Cornell University), 99, pp. 103419, 10.1016/j.ejc.2021.103419, https://arxiv.org/abs/2102.07299.

Paweł Hitczenko;Aleksandr Yaroslavskiy, 2020, Asymptotic normality of the number of corners in tableaux associated with the partially asymmetric simple exclusion process, Random structures & algorithms (Print), 57, 4, pp. 1248-1271, 10.1002/rsa.20961, https://doi.org/10.1002/rsa.20961.

Hungyung Chang;Jun Ma;Jean Yeh, 2019, Enumerations of Permutations by Circular Descent Sets, Taiwanese Journal of Mathematics, 23, 6, 10.11650/tjm/190105, https://doi.org/10.11650/tjm/190105.

Olya Mandelshtam;Xavier Gérard Viennot, 2018, Rhombic alternative tableaux and assemblées of permutations, arXiv (Cornell University), 73, pp. 1-19, 10.1016/j.ejc.2018.05.002, http://arxiv.org/abs/1609.07638.

Soojin Cho;Kyoungsuk Park, 2018, A Combinatorial Proof of a Symmetry of (t, q)-Eulerian Numbers of Type B and Type D, arXiv (Cornell University), 22, 1, pp. 99-134, 10.1007/s00026-018-0372-6, https://arxiv.org/abs/1309.5809.

Joanna N. Chen;Robin D.P. Zhou, 2017, On the sign-imbalance of permutation tableaux, Advances in applied mathematics (Print), 86, pp. 1-18, 10.1016/j.aam.2016.11.012, https://doi.org/10.1016/j.aam.2016.11.012.

Amanda Lohss, 2016, The asymptotic distribution of symbols on diagonals of random weighted staircase tableaux, arXiv (Cornell University), 49, 4, pp. 795-818, 10.1002/rsa.20665, https://arxiv.org/abs/1512.00329.

Paweł Hitczenko;Amanda Lohss, 2016, Corners in Tree-Like Tableaux, Electronic Journal of Combinatorics, 23, 4, 10.37236/5712, https://doi.org/10.37236/5712.

Sylvie Corteel;Sandrine Dasse-Hartaut, 2016, A Bijection from Staircase Tableaux to Inversion Tables, Giving Some Eulerian and Mahonian Statistics, Annals of Combinatorics, 20, 4, pp. 737-754, 10.1007/s00026-016-0329-6.

Carol J. Wang;Zhongjin Chen, 2015, The parity of the number of permutation tableaux in a fixed shape, Applied Mathematics and Computation, 265, pp. 1090-1097, 10.1016/j.amc.2015.06.024.

Jang Soo Kim;Dennis Stanton, 2015, The Combinatorics of Associated Laguerre Polynomials, Symmetry Integrability and Geometry-methods and Applications, 10.3842/sigma.2015.039, https://doi.org/10.3842/sigma.2015.039.

Pawel Hitczenko;Svante Janson, 2014, Weighted Random Staircase Tableaux, arXiv (Cornell University), 23, 6, pp. 1114-1147, 10.1017/s0963548314000327, https://arxiv.org/abs/1212.5498.

Jean-Christophe Aval;Adrien Boussicault;Sandrine Dasse-Hartaut, 2013, Dyck tableaux, Theoretical computer science, 502, pp. 195-209, 10.1016/j.tcs.2011.11.038, https://doi.org/10.1016/j.tcs.2011.11.038.

Sylvie Corteel;Matthieu Josuat-Vergès;Jang Soo Kim, 2013, Crossings of signed permutations and $q$-Eulerian numbers of type $B$, The journal of combinatorics (Somerville, Mass. Online), 4, 2, pp. 191-228, 10.4310/joc.2013.v4.n2.a3, https://doi.org/10.4310/joc.2013.v4.n2.a3.

Valentin Feray, 2013, Asymptotic behavior of some statistics in Ewens random permutations, Electronic Journal of Probability, 18, none, 10.1214/ejp.v18-2496, https://doi.org/10.1214/ejp.v18-2496.

William Y. C. Chen;Lewis H. Liu;Carol J. Wang, 2013, Linked Partitions and Permutation Tableaux, The Electronic journal of combinatorics, 20, 3, 10.37236/3408, https://doi.org/10.37236/3408.

S. Corteel;R. Stanley;D. Stanton;L. Williams, 2012, Formulae for Askey-Wilson moments and enumeration of staircase tableaux, Transactions of the American Mathematical Society, 364, 11, pp. 6009-6037, 10.1090/s0002-9947-2012-05588-7, https://doi.org/10.1090/s0002-9947-2012-05588-7.

Jang Soo Kim, 2011, New interpretations for noncrossing partitions of classical types, Journal of combinatorial theory. Series A (Print), 118, 4, pp. 1168-1189, 10.1016/j.jcta.2010.12.005, https://doi.org/10.1016/j.jcta.2010.12.005.

Matthieu Josuat-Vergès, 2011, Rook placements in Young diagrams and permutation enumeration, arXiv (Cornell University), 47, 1, pp. 1-22, 10.1016/j.aam.2010.04.003, https://arxiv.org/abs/0811.0524.

Matthieu Josuat-Vergès, 2011, Combinatorics of the Three-Parameter PASEP Partition Function, Electronic Journal of Combinatorics, 18, 1, 10.37236/509, https://doi.org/10.37236/509.

Philippe Nadeau, 2011, The structure of alternative tableaux, arXiv (Cornell University), 118, 5, pp. 1638-1660, 10.1016/j.jcta.2011.01.012.

Sylvie Corteel;Jang Soo Kim, 2011, Combinatorics on permutation tableaux of type A and type B, arXiv (Cornell University), 32, 4, pp. 563-579, 10.1016/j.ejc.2011.01.003, https://arxiv.org/abs/1006.3812.

Sylvie Corteel;Lauren K. Williams, 2011, Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials, arXiv (Cornell University), 159, 3, 10.1215/00127094-1433385, http://arxiv.org/abs/0910.1858.

Sylvie Corteel;Matthieu Josuat-Vergès;Lauren K. Williams, 2011, The Matrix Ansatz, orthogonal polynomials, and permutations, Advances in applied mathematics (Print), 46, 1-4, pp. 209-225, 10.1016/j.aam.2010.04.009, https://doi.org/10.1016/j.aam.2010.04.009.

Alexander Burstein;Niklas Eriksen, Combinatorial properties of permutation tableaux, pp. 171-192, 2010, 10.1017/cbo9780511902499.009, https://hal.inria.fr/hal-01185149.

Einar Steingrimsson, Strathprints: The University of Strathclyde institutional repository (University of Strathclyde), Generalized permutation patterns – a short survey, pp. 137-152, 2010, 10.1017/cbo9780511902499.007, https://strathprints.strath.ac.uk/33799/1/St08_Generalized_permutation.pdf.

Jason Bell;Stephane Launois;Jamie Lutley, 2010, An automaton-theoretic approach to the representation theory of quantum algebras, arXiv (Cornell University), 223, 2, pp. 476-510, 10.1016/j.aim.2009.08.013, https://arxiv.org/abs/0901.4707.

Matthieu Josuat-Vergès, 2010, Combinatorics of the PASEP partition function, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AN,..., Proceedings, 10.46298/dmtcs.2855, https://doi.org/10.46298/dmtcs.2855.

Matthieu Josuat-Vergès, 2010, Bijections between pattern-avoiding fillings of Young diagrams, Journal of combinatorial theory. Series A (Print), 117, 8, pp. 1218-1230, 10.1016/j.jcta.2010.03.006, https://doi.org/10.1016/j.jcta.2010.03.006.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 158 times.

This article's PDF has been downloaded 144 times.