Ars Combinatoria, 25B (1988), pp. 3-30.
Ömer Egecioglu and L. P. Shen
A Bijective Proof for the Number of Labeled q-trees
Abstract.
We give a bijective proof that the number of vertex labeled q-trees on n
vertices is given by ${n \choose q}(qn-q^2+1)^{n-q-2}$. The bijection
transforms each pair (S,f) where S is a q-element subset of an n-set,
and f is a function mapping an $(n-q-2)$-set to a
$(qn-q^2+1)$-set into a labeled q-tree on n nodes by a cut-and-paste process.
As a special case, q=1 yields a new bijective proof of Cayley's formula
for labeled trees. The general bijection also provides for the enumeration
of labeled q-trees in which a specified subset of the vertices forms a clique.
omer@cs.ucsb.edu