Combinatorics of non-ambiguous trees

2013/05/16 by Jean-Christophe Aval, Adrien Boussicault, Aval, Jean-Christophe +5 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1305.3716

openalex publication_date 2013/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Homology character of the parabolic coset poset

Related

• Non-ambiguous trees: new results and generalisation
• Non-ambiguous trees: new results and generalisation (Full version)
• Complete non-ambiguous trees and associated permutations: new enumerative results
• Alternative Proof of the Determinant of Complete Non-Ambiguous Trees
• The structure of alternative tableaux