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 TableauxConference paper

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

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

[en]
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].

[fr]
Dans cet article nous donnons une bijection entre les tableaux de permutations et les permutations. Cette bijection montre comment des statistiques naturelles sur les tableaux sont équidistribuées avec des statistiques classiques sur les permutations: descentes, minima de droite à gauche et motifs. Cette bijection nous sert ensuite, à l'aide d'un certain codage des tableaux par des mots, à donner des résultats sur l'énumération de permutations avec un nombre fixé de motifs 31-2, et à déterminer certaines sous-classes de tableaux en bijection avec les partitions d'ensembles. Une version étendue de ce travail est disponible [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: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] enumeration, bijections, permutations, tableaux, permutation patterns

Bibliographic References

27 Documents citing this article

Joanna N. Chen, 2021, Block decomposition and statistics arising from permutation tableaux, arXiv (Cornell University), 99, pp. 103419, 10.1016/j.ejc.2021.103419, http://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 and Algorithms, 57, 4, pp. 1248-1271, 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.

Soojin Cho;Kyoungsuk Park, 2018, A Combinatorial Proof of a Symmetry of (t, q)-Eulerian Numbers of Type B and Type D, Annals of Combinatorics, 22, 1, pp. 99-134, 10.1007/s00026-018-0372-6.

Joanna N. Chen;Robin D.P. Zhou, 2016, On the sign-imbalance of permutation tableaux, arXiv (Cornell University), 86, pp. 1-18, 10.1016/j.aam.2016.11.012, http://arxiv.org/abs/1602.00105.

Pawel Hitczenko;Amanda Lohss, 2016, Corners in Tree-Like Tableaux, The 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.

PAWEŁ HITCZENKO;SVANTE JANSON;PAWEŁ HITCZENKO;SVANTE JANSON, 2014, Weighted Random Staircase Tableaux, arXiv (Cornell University), 23, 6, pp. 1114-1147, 10.1017/s0963548314000327, http://arxiv.org/abs/1212.5498.

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

Valentin Féray, 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, 118, 4, pp. 1168-1189, 10.1016/j.jcta.2010.12.005.

Jean-Christophe Aval;Adrien Boussicault;Sandrine Dasse-Hartaut, 2011, Dyck tableaux, Theoretical Computer Science, 502, pp. 195-209, 10.1016/j.tcs.2011.11.038.

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

Philippe Nadeau, 2011, The structure of alternative tableaux, Journal of Combinatorial Theory Series A, 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, European Journal of Combinatorics, 32, 4, pp. 563-579, 10.1016/j.ejc.2011.01.003.

Sylvie Corteel;Lauren K. Williams, 2011, Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials, Duke Mathematical Journal, 159, 3, 10.1215/00127094-1433385.

Alexander Burstein;Niklas Eriksen, 2010, Combinatorial properties of permutation tableaux, Cambridge University Press eBooks, pp. 171-192, 10.1017/cbo9780511902499.009.

Einar Steingrímsson, 2010, Generalized permutation patterns – a short survey, Cambridge University Press eBooks, pp. 137-152, 10.1017/cbo9780511902499.007.

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, Rook placements in Young diagrams and permutation enumeration, arXiv (Cornell University), 47, 1, pp. 1-22, 10.1016/j.aam.2010.04.003, http://arxiv.org/abs/0811.0524.

Matthieu Josuat-Vergès, 2010, Bijections between pattern-avoiding fillings of Young diagrams, Journal of Combinatorial Theory Series A, 117, 8, pp. 1218-1230, 10.1016/j.jcta.2010.03.006.

Sylvie Corteel;Matthieu Josuat-Vergès;Lauren K. Williams, 2010, The Matrix Ansatz, orthogonal polynomials, and permutations, arXiv (Cornell University), 46, 1-4, pp. 209-225, 10.1016/j.aam.2010.04.009, http://arxiv.org/abs/1005.2696.

J. Bell;S. Launois;J. Lutley, 2009, An automaton-theoretic approach to the representation theory of quantum algebras, Advances in Mathematics, 223, 2, pp. 476-510, 10.1016/j.aim.2009.08.013.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 332 times.

This article's PDF has been downloaded 257 times.