Mathematics – Combinatorics
Scientific paper
2005-11-02
Mathematics
Combinatorics
18 pages, 6 figures
Scientific paper
We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schr\"oder paths. The classical Chung-Feller theorem on free Dyck paths and some generalizations and variations with respect to Dyck paths and Schr\"oder paths with flaws turn out to be immediate consequences of the butterfly decomposition and the preorder traversal of plane trees. We obtain two involutions on free Dyck paths and free Schr\"oder paths, leading to two combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of the generating function for the number of chains in plane trees due to Klazar. We further study the average size of chains in plane trees with $n$ edges and show that this number asymptotically tends to ${n+9 \over 6}$.
Chen William Y. C.
Li Nelson Y.
Shapiro Louis W.
No associations
LandOfFree
The Butterfly Decomposition of Plane Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Butterfly Decomposition of Plane Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Butterfly Decomposition of Plane Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-639720