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. Tree-like tableaux
Conference paper

Tree-like tableaux

Jean-Christophe Aval (1), Adrien Boussicault (1), Philippe Nadeau ORCID (2) (3) (4)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Faculty of Mathematics [Vienna]
(3) Faculty of Mathematics [Univ. Vienna]
(4) Faculty of Mathematics = Fakultät für Mathematik [Vienne, Autriche]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2010
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Proceedings
DOI
10.46298/dmtcs.2891
License
https://about.hal.science/hal-authorisation-v1
Indicators
746
Views
575
Downloads

Tree-like tableaux

Jean-Christophe Aval (1), Adrien Boussicault (1), Philippe Nadeau ORCID (2) (3) (4)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Faculty of Mathematics [Vienna]
(3) Faculty of Mathematics [Univ. Vienna]
(4) Faculty of Mathematics = Fakultät für Mathematik [Vienne, Autriche]
Abstract
English
In this work we introduce and study tree-like tableaux, which are certain fillings of Ferrers diagrams in simple bijection with permutation tableaux and alternative tableaux. We exhibit an elementary insertion procedure on our tableaux which gives a clear proof that tableaux of size n are counted by n!, and which moreover respects most of the well-known statistics studied originally on alternative and permutation tableaux. Our insertion procedure allows to define in particular two simple new bijections between tree-like tableaux and permutations: the first one is conceived specifically to respect the generalized pattern 2-31, while the second one respects the underlying tree of a tree-like tableau.
French
Dans ce travail nous introduisons et étudions les tableaux boisés, qui sont certains remplissages de diagrammes de Ferrers en bijection simple avec les tableaux de permutation et les tableaux alternatifs. Nous décrivons une procédure d'insertion élémentaire sur nos tableaux qui donne une preuve limpide que les tableaux de taille n sont comptés par n!, et qui de plus respecte la plupart des statistiques standard sur les tableaux de permutation et tableaux alternatifs. Notre procédure d'insertion permet en particulier de définir deux nouvelles bijections simples entre tableaux et permutations: la première est conçue spécifiquement pour respecter le motif généralisé 2-31 sur les permutations, tandis que la deuxième respecte l'arbre binaire sous-jacent à un tableau boisé.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • tree-like tableaux
  • permutation tableaux
  • alternative tableaux
  • permutations
  • binary trees
Cited by

Source: OpenCitations

  • Stieltjes moment properties and continued fractions from combinatorial triangles

    Advances in Applied Mathematics

    Authors : Bao-Xuan Zhu ORCID

    Journal reference : Volume 130, 2021, pp. 102232

    DOI : 10.1016/j.aam.2021.102232
  • 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
  • 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
  • Permutation Graphs and the Abelian Sandpile Model, Tiered Trees and Non-Ambiguous Binary Trees

    The Electronic Journal of Combinatorics

    Authors : Mark Dukes ORCID, Thomas Selig ORCID, Jason P. Smith ORCID, Einar Steingrímsson ORCID

    Journal reference : Volume 26, 2019, pp.

    DOI : 10.37236/8225
  • The number of directed $k$-convex polyominoes

    Discrete Mathematics & Theoretical Computer Science

    Authors : Adrien Boussicault, Simone Rinaldi, Samanta Socci

    Journal reference : Volume DMTCS Proceedings, 27th..., 2015, pp.

    DOI : 10.46298/dmtcs.2465
  • Dyck tilings, linear extensions, descents, and inversions

    Discrete Mathematics & Theoretical Computer Science

    Authors : Jang Soo Kim ORCID, Karola Mészáros, Greta Panova ORCID, David B. Wilson

    Journal reference : Volume DMTCS Proceedings vol. AR,..., 2012, pp.

    DOI : 10.46298/dmtcs.3081
  • 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
  • Combinatorics of faithfully balanced modules

    arXiv (Cornell University)

    Authors : William Crawley-Boevey ORCID, Biao Ma ORCID, Baptiste Rognerud ORCID, Julia Sauter

    Journal reference : Volume 182, 2021, pp. 105472

    DOI : 10.1016/j.jcta.2021.105472
  • 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
  • Multi-Catalan tableaux and the two-species TASEP

    Annales de l’Institut Henri Poincaré D Combinatorics Physics and their Interactions

    Authors : Olya Mandelshtam ORCID

    Journal reference : Volume 3, 2016, pp. 321-348

    DOI : 10.4171/aihpd/30
  • Stammering tableaux

    Authors : Josuat-Vergès

    Journal reference : Volume , 2017, pp.

    DOI : 10.23638/dmtcs-19-3-3
  • Weighted Staircase Tableaux, Asymmetric Exclusion Process, and Eulerian Type Recurrences

    Lecture notes in computer science

    Authors : Paweł Hitczenko ORCID, Svante Janson ORCID

    Journal reference : Volume , 2014, pp. 490-501

    DOI : 10.1007/978-3-642-54423-1_43
Preview
Loading PDF preview...