Complete non-ambiguous trees and associated permutations: new enumerative results

MaRDI QIDQ6509374arXivFDO

Authors Thomas Selig, Haoyue Zhu

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Abstract: We study a link between complete non-ambiguous trees (CNATs) and permutations exhibited by Daniel Chen and Sebastian Ohlig in recent work. In this, they associate a certain permutation to the leaves of a CNAT, and show that the number of $n$-permutations that are associated with exactly one CNAT is $2^{n-2}$. We connect this to work by the first author and co-authors linking complete non-ambiguous trees and the Abelian sandpile model. This allows us to prove a number of conjectures by Chen and Ohlig on the number of $n$-permutations that are associated with exactly $k$ CNATs for various $k>1$, via bijective correspondences between such permutations. We also exhibit a new bijection between $(n-1)$-permutations and CNATs whose permutation is the decreasing permutation $n(n-1)cdots1$. This bijection maps the left-to-right minima of the permutation to dots on the bottom row of the corresponding CNAT, and descents of the permutation to empty rows of the CNAT.

This page was built for publication: Complete non-ambiguous trees and associated permutations: new enumerative results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509374)