Tree-like tableaux

• Main Authors: Aval, Jean-Christophe, Boussicault, Adrien, Nadeau, Philippe
• Other Authors: Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Faculty of Mathematics Vienna, University of Vienna Vienna, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: tree-like tableaux; permutation tableaux; alternative tableaux; permutations; binary trees; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Iceland
• Online Access: https://hal.inria.fr/hal-01215092; https://hal.inria.fr/hal-01215092/document; https://hal.inria.fr/hal-01215092/file/dmAO0107.pdf

International audience 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. 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é.