The rotation \(\chi\)-lattice of ternary trees (Q5943902)

A regular ternary tree is a rooted, ordered tree in which every internal node has exactly three sons. The author defines a left rotation \(\to\) on ternary trees which generalizes a well-known rotation transformation on binary trees. Specifically, to a ternary tree \(T\) with \(n\) internal nodes associate a tree \(T'\) obtained either by replacing some subtree \(\circ T_1T_2\circ T_3T_4T_5\) of \(T\) (where \(\circ\) is an internal node) by the subtree \(\circ T_1\circ T_2T_3T_4T_5\) or by replacing some subtree \(\circ T_1\circ T_2T_3T_4T_5\) by the subtree \(\circ\circ T_1T_2T_3T_4T_5\). The author introduces two new codings of ternary trees and proves a characterization of the left rotation \(T\to T'\) in terms of the new codings. This characterization generalizes the one on binary trees the author gave in ``Enumerating, ranking and unranking binary trees'' [Comput. J. 29, 171-175 (1986; Zbl 0585.68066)]. The author proves that the class of ternary trees with \(n\) internal nodes is a \(\chi\)-lattice in the sense of \textit{K. Leutola} and \textit{J. Nieminen} [``Posets and generalized lattices'', Algebra Univers. 16, 344-354 (1983; Zbl 0514.06003)] and gives algorithms for computing meets and joins. The author closes by noting the generalization to \(k\)-ary trees (every internal node has exactly \(k\) sons) and gives several conjectures.