Skip to Main content Skip to Navigation
Conference papers

Combinatorics of non-ambiguous trees

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01229716
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:20:30 AM
Last modification on : Friday, November 13, 2020 - 9:42:03 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:43:17 AM

File

dmAS0105.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229716, version 1

Collections

Citation

Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Matteo Silimbani. Combinatorics of non-ambiguous trees. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.49-60. ⟨hal-01229716⟩

Share

Metrics

Record views

157

Files downloads

379