A new bijection between RNA secondary structures and plane trees and its consequences
*小锋 陈 (合肥工业大学)
In this paper, we first present a new bijection between RNA secondary structures and plane trees. Combined with the Schmitt-Waterman bijection between these objects, we then obtain a bijection on plane trees that relates the horizontal fiber decomposition associated to internal vertices to the degrees of odd-level vertices while the vertical path decomposition associated to leaves is related to the degrees of even-level vertices. To the best of our knowledge, only the former relation (i.e., horizontal vs odd-level) due to Deutsch is known. As a consequence, we obtain enumeration results for various classes of plane trees, e.g., refining the Narayana numbers and the enumeration involving young leaves due to Chen, Deutsch and Elizalde, and counting a newly introduced ‘vertical’ version of k-ary trees.