Jean-Christophe Aval ; Adrien Boussicault ; Mathilde Bouvel ; Matteo Silimbani - Combinatorics of non-ambiguous trees

dmtcs:12792 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.12792
Combinatorics of non-ambiguous treesArticle

Authors: Jean-Christophe Aval 1; Adrien Boussicault 1; Mathilde Bouvel 1; Matteo Silimbani 1

  • 1 Laboratoire Bordelais de Recherche en Informatique

This article investigates combinatorial properties of non-ambiguous trees. These objects we define may be seen either as binary trees drawn on a grid with some constraints, or as a subset of the tree-like tableaux previously defined by Aval, Boussicault and Nadeau. The enumeration of non-ambiguous trees satisfying some additional constraints allows us to give elegant combinatorial proofs of identities due to Carlitz, and to Ehrenborg and Steingrímsson. We also provide a hook formula to count the number of non-ambiguous trees with a given underlying tree. Finally, we use non-ambiguous trees to describe a very natural bijection between parallelogram polyominoes and binary trees.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: tree,polyomino,non-ambiguous tree,tree-like tableau,hook formula,Bessel function,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Permutation classes: from structure to combinatorial properties; Funder: Swiss National Science Foundation; Code: 151254

Consultation statistics

This page has been seen 59 times.
This article's PDF has been downloaded 55 times.