Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Bijections for Permu ...
Conference paper

Bijections for Permutation Tableaux

Sylvie Corteel (1), Philippe Nadeau ORCID (2) (3)
(1) Laboratoire de Recherche en Informatique
(2) Universität Wien
(3) Universität Wien = University of Vienna
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Proceedings
DOI
10.46298/dmtcs.3632
License
https://about.hal.science/hal-authorisation-v1
Indicators
552
Views
405
Downloads

Bijections for Permutation Tableaux

Sylvie Corteel (1), Philippe Nadeau ORCID (2) (3)
(1) Laboratoire de Recherche en Informatique
(2) Universität Wien
(3) Universität Wien = University of Vienna
Abstract
English
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].
French
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].
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • enumeration
  • bijections
  • permutations
  • tableaux
  • permutation patterns
Cited by

Source: OpenCitations

  • Crossings of signed permutations and $q$-Eulerian numbers of type $B$

    Journal of Combinatorics

    Authors : Sylvie Corteel ORCID, Matthieu Josuat-Vergès ORCID, Jang Soo Kim ORCID

    Journal reference : Volume 4, 2013, pp. 191-228

    DOI : 10.4310/joc.2013.v4.n2.a3

  • Combinatorial properties of permutation tableaux

    Cambridge University Press eBooks

    Authors : Alexander Burstein ORCID, Niklas Eriksen

    Journal reference : Volume , 2010, pp. 171-192

    DOI : 10.1017/cbo9780511902499.009

  • Weighted Random Staircase Tableaux

    arXiv (Cornell University)

    Authors : PAWEŁ HITCZENKO, SVANTE JANSON

    Journal reference : Volume 23, 2014, pp. 1114-1147

    DOI : 10.1017/s0963548314000327

  • The asymptotic distribution of symbols on diagonals of random weighted staircase tableaux

    arXiv (Cornell University)

    Authors : Amanda Lohss

    Journal reference : Volume 49, 2016, pp. 795-818

    DOI : 10.1002/rsa.20665

  • Combinatorics of the Three-Parameter PASEP Partition Function

    The Electronic Journal of Combinatorics

    Authors : Matthieu Josuat-Vergès ORCID

    Journal reference : Volume 18, 2011, pp.

    DOI : 10.37236/509

  • The parity of the number of permutation tableaux in a fixed shape

    Applied Mathematics and Computation

    Authors : Carol J. Wang ORCID, Zhongjin Chen

    Journal reference : Volume 265, 2015, pp. 1090-1097

    DOI : 10.1016/j.amc.2015.06.024

  • Enumerations of Permutations by Circular Descent Sets

    Taiwanese Journal of Mathematics

    Authors : Hungyung Chang, Jun Ma ORCID, Jean Yeh ORCID

    Journal reference : Volume 23, 2019, pp.

    DOI : 10.11650/tjm/190105

  • Rook placements in Young diagrams and permutation enumeration

    Advances in Applied Mathematics

    Authors : Matthieu Josuat-Vergès ORCID

    Journal reference : Volume 47, 2010, pp. 1-22

    DOI : 10.1016/j.aam.2010.04.003

  • Asymptotic behavior of some statistics in Ewens random permutations

    Electronic Journal of Probability

    Authors : Valentin Féray ORCID

    Journal reference : Volume 18, 2013, pp.

    DOI : 10.1214/ejp.v18-2496

  • On the sign-imbalance of permutation tableaux

    Advances in Applied Mathematics

    Authors : Joanna N. Chen ORCID, Robin D.P. Zhou ORCID

    Journal reference : Volume 86, 2016, pp. 1-18

    DOI : 10.1016/j.aam.2016.11.012

  • Combinatorics on permutation tableaux of type A and type B

    European Journal of Combinatorics

    Authors : Sylvie Corteel ORCID, Jang Soo Kim ORCID

    Journal reference : Volume 32, 2011, pp. 563-579

    DOI : 10.1016/j.ejc.2011.01.003

  • The structure of alternative tableaux

    Journal of Combinatorial Theory Series A

    Authors : Philippe Nadeau ORCID

    Journal reference : Volume 118, 2011, pp. 1638-1660

    DOI : 10.1016/j.jcta.2011.01.012

  • Combinatorics of the PASEP partition function

    Discrete Mathematics & Theoretical Computer Science

    Authors : Matthieu Josuat-Vergès ORCID

    Journal reference : Volume DMTCS Proceedings vol. AN,..., 2010, pp.

    DOI : 10.46298/dmtcs.2855

  • Generalized permutation patterns – a short survey

    Cambridge University Press eBooks

    Authors : Einar Steingrímsson ORCID

    Journal reference : Volume , 2010, pp. 137-152

    DOI : 10.1017/cbo9780511902499.007

  • A Combinatorial Proof of a Symmetry of (t, q)-Eulerian Numbers of Type B and Type D

    Annals of Combinatorics

    Authors : Soojin Cho ORCID, Kyoungsuk Park

    Journal reference : Volume 22, 2018, pp. 99-134

    DOI : 10.1007/s00026-018-0372-6

  • A Bijection from Staircase Tableaux to Inversion Tables, Giving Some Eulerian and Mahonian Statistics

    Annals of Combinatorics

    Authors : Sylvie Corteel ORCID, Sandrine Dasse-Hartaut

    Journal reference : Volume 20, 2016, pp. 737-754

    DOI : 10.1007/s00026-016-0329-6

  • Bijections between pattern-avoiding fillings of Young diagrams

    Journal of Combinatorial Theory Series A

    Authors : Matthieu Josuat-Vergès ORCID

    Journal reference : Volume 117, 2010, pp. 1218-1230

    DOI : 10.1016/j.jcta.2010.03.006

  • Block decomposition and statistics arising from permutation tableaux

    arXiv (Cornell University)

    Authors : Joanna N. Chen ORCID

    Journal reference : Volume 99, 2021, pp. 103419

    DOI : 10.1016/j.ejc.2021.103419

  • The Matrix Ansatz, orthogonal polynomials, and permutations

    arXiv (Cornell University)

    Authors : Sylvie Corteel ORCID, Matthieu Josuat-Vergès ORCID, Lauren K. Williams ORCID

    Journal reference : Volume 46, 2010, pp. 209-225

    DOI : 10.1016/j.aam.2010.04.009

  • Enumeration of Corners in Tree-like Tableaux

    Discrete Mathematics & Theoretical Computer Science

    Authors : Alice L. L. Gao, Emily X. L. Gao, Patxi Laborde-Zubieta, Brian Y. Sun ORCID

    Journal reference : Volume Vol. 18 no. 3, 2016, pp.

    DOI : 10.46298/dmtcs.1408

  • Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials

    Duke Mathematical Journal

    Authors : Sylvie Corteel ORCID, Lauren K. Williams ORCID

    Journal reference : Volume 159, 2011, pp.

    DOI : 10.1215/00127094-1433385

  • Corners in Tree-Like Tableaux

    The Electronic Journal of Combinatorics

    Authors : Paweł Hitczenko ORCID, Amanda Lohss

    Journal reference : Volume 23, 2016, pp.

    DOI : 10.37236/5712

  • Formulae for Askey-Wilson moments and enumeration of staircase tableaux

    Transactions of the American Mathematical Society

    Authors : S. Corteel ORCID, R. Stanley ORCID, D. Stanton ORCID, L. Williams ORCID

    Journal reference : Volume 364, 2012, pp. 6009-6037

    DOI : 10.1090/s0002-9947-2012-05588-7

  • Rhombic alternative tableaux and assemblées of permutations

    European Journal of Combinatorics

    Authors : Olya Mandelshtam ORCID, Xavier Viennot

    Journal reference : Volume 73, 2018, pp. 1-19

    DOI : 10.1016/j.ejc.2018.05.002

  • An automaton-theoretic approach to the representation theory of quantum algebras

    Advances in Mathematics

    Authors : J. Bell ORCID, S. Launois, J. Lutley

    Journal reference : Volume 223, 2009, pp. 476-510

    DOI : 10.1016/j.aim.2009.08.013

  • The Combinatorics of Associated Laguerre Polynomials

    Symmetry Integrability and Geometry Methods and Applications

    Authors : Jang Soo Kim ORCID, Dennis Stanton ORCID

    Journal reference : Volume , 2015, pp.

    DOI : 10.3842/sigma.2015.039

  • Dyck tableaux

    Theoretical Computer Science

    Authors : Jean-Christophe Aval, Adrien Boussicault, Sandrine Dasse-Hartaut

    Journal reference : Volume 502, 2011, pp. 195-209

    DOI : 10.1016/j.tcs.2011.11.038

  • Asymptotic normality of the number of corners in tableaux associated with the partially asymmetric simple exclusion process

    Random Structures and Algorithms

    Authors : Paweł Hitczenko ORCID, Aleksandr Yaroslavskiy

    Journal reference : Volume 57, 2020, pp. 1248-1271

    DOI : 10.1002/rsa.20961

  • New interpretations for noncrossing partitions of classical types

    Journal of Combinatorial Theory Series A

    Authors : Jang Soo Kim ORCID

    Journal reference : Volume 118, 2011, pp. 1168-1189

    DOI : 10.1016/j.jcta.2010.12.005

  • Linked Partitions and Permutation Tableaux

    The Electronic Journal of Combinatorics

    Authors : William Y.C. Chen, Lewis H. Liu, Carol J. Wang ORCID

    Journal reference : Volume 20, 2013, pp.

    DOI : 10.37236/3408
Preview
Loading PDF preview...