Bijections for ternary trees and non-crossing trees (Q1613443): Difference between revisions

Consider the set \(P_n\) of the vertices of a regular \(n\)-gon. A non-crossing tree is a connected acyclic graph with vertex set \(P_n\) whose edges are straight line segments that do not cross. Using the idea of rotation correspondence the authors establish a new bijection between the set of non-crossing trees of size \(n+1\) and the set of ternary trees of size \(n\). Furthermore two bijective proofs for a recurrence relation for the number of ternary trees of fixed size are presented.