  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 various 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 top
row of the corresponding CNAT, and descents of the permutation to empty rows of
the CNAT.
