Non-Ambiguous Trees: new results and generalisation (Full version)

Bérénice Delcroix-Oger (1) , Florent Hivert (2) , Patxi Laborde-Zubieta (3) , Jean-Christophe Aval (3) , Adrien Boussicault (3)

1 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
2 LRI - Laboratoire de Recherche en Informatique
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique

We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yields a new formula for the number of NATs. We also obtain q-versions of our formula. We finally generalise NATs to higher dimension.

Mots clés: binary trees; ordered trees; q-analogues; permutations; hook-length formulas; Non-ambiguous trees; qanalogues

Domaines: Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, Adrien Boussicault. Non-Ambiguous Trees: new results and generalisation (Full version). European Journal of Combinatorics, 2021, 95, pp.103331. ⟨hal-03165269v2⟩