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

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 Tutte polynomial of the associated permutation graph. 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)⋯1. 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.