Journal of Combinatorial Theory, Series A, 42, No. 1 (1986), pp. 15-30.
Ömer Egecioglu and Jeffrey B. Remmel
Bijections for Cayley Trees, Spanning Trees, and Their q-analogues
Abstract.
We construct a family of extremely simple bijections that yield
Cayley's famous formula for counting trees. The weight preserving
properties of these bijections furnish a number of multivariate
generating functions for weighted Cayley trees. Essentially the
same idea is used to derive bijective proofs and q-analogues
for the number of spanning trees of other graphs, including
the complete bipartite and complete tripartite graphs. These
bijections also allow the calculation of explicit formulas for the
expected number of various statistics on Cayley trees.
omer@cs.ucsb.edu