A New Bijection Between Ordered Trees and Legal Bracketings

AbstractThe 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.We give 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.In addition, we prove that the productG·Fr-1is the bijectionWdiscovered by Vaille (cited in [5]).FandGhelp to derive some combinatorial properties ofWin a straightforward manner