Automorphisms on Catalan trees and bracketings

AbstractTwo mirror-image isomorphisms between general bracketings and binary bracketings are formalized which parallel the isomorphisms described by De Bruijn and Morselt between plane trees and trivalent plane trees. These maps lead to automorphisms on these four Catalan families. It is found that the orbit structure of these automorphisms is determined by certain “primitive” elements of the four families, and that the enumerator pn of these primitive elements satisfies the equations: pn = mn−2 + mn−1, where mn = Σk=0 (2kn)ck, cn the Catalan numbers, and cn+2=∑k=0nkpk+2. It is then shown that these automorphisms yield isomorphisms between several interesting subsets of the trees and brackets, most of them enumerated by mn. In particular, it is shown that the general bracketings containing no occurrence of “(g)(g)(g)” and those containing no occurrence of “((g))” are mapped to each other