Callan, David

A combinatorial derivation of the number of labeled forests

J. Integer Seq. 6(4), Art. 03.4.7, 3 p., electronic only (2003)

Summary

Summary: Lajos Takács gave a somewhat formidable alternating sum expression for the number of forests of unrooted trees on $n$ labeled vertices. Here we use a weight-reversing involution on suitable tree configurations to give a combinatorial derivation of Takács' result.

Mathematics Subject Classification

05C05

Keywords/Phrases

tree, labeled forest, partially-paired rooted n-forest, inversion-initiating vertex, weight-reversing involution

Downloads