Symmetries in trees and parking functions
The author gives two new proofs of the following fact first discovered by Gessel: in the set of rooted labeled trees of \(n+1\) vertices rooted at the smallest vertex, the number of trees with \(a\) descents and \(b+1\) leaves equals the number of trees with \(b\) descents and \(a+1\) leaves (a descent is a vertex whose label is greater than at least one of its children labels). His approach uses decompositions of trees and leads to a generalization of a well-known bijection from \(\{1,\dots, n\}\) to increasing trees (i.e. trees with no descents) and to a generalization found by Knuth involving intransitive trees. One of these decompositions is related to symmetry in parking functions. The received results are generalized to binary trees.
scientific article; zbMATH DE number 1838964
scientific article