Hopf-algebraic structure of families of trees (Q753918)

The naive algebraic structure \(\chi\) of the sets Tree(\(\chi\)) of finite rooted trees and Forest(\(\chi\)) of finite forests of elements of Tree(\(\chi\)) is axiomatized in a way to allow additional structures like labels, colors, orders etc. A cocommutative graded connected Hopf algebra \(k(\chi)\) with basis Tree(\(\chi\)) is associated with each model of \(\chi\). Using the Milnor-Moore and the Poincaré-Birkhoff-Witt theorems the structure of \(k(\chi)\) and its associated Lie algebra is studied and used for counting certain families of trees. In particular an old formula of Cayley's (1857) for the number of (ordered, labeled) rooted trees is proved in this way.