** Abstract:** 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öder paths. The
classical Chung-Feller theorem on free Dyck paths and some generalizations and
variations with respect to Dyck paths and Schröder 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öder 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 .
**AMS Classification:** 05A15, 05A19, 05C05.
** Keywords:** Plane tree, doubly rooted plane tree, chains in plane trees, k-colored
plane tree, butterfly decomposition, Dyck path, Schröder path.
** Download: ** Pdf |