A New Bijection Between Ordered Trees and Legal Bracketings

The Catalan numbers[formula]are known to enumerate the legal bracketings of lengthn [1]as well as the ordered trees withn+1vertices. There exists a classical bijection (cf. [2]) between these objects that will be denoted byGthroughout the paper. e a new bijectionFbetween the same objects that has some interesting combinatorial properties. In particular,Ftransforms an operation on the legal bracketings introduced by Kreweras [3] into a simple operation on trees. ition, we prove that the productG · Fr-1is the bijectionWdiscovered by Vaille (cited in [5]). elp to derive some combinatorial properties ofWin a straightforward manner.