Enumeration of some labelled trees

A Cayley tree on \([n]\) is a tree with \(n\) vertices, labeled \(1,2,\dots, n\), such that one vertex, called the root, is distinguished. It was stated by Cayley and proved in many places that there are \(n^{n-1}\) such trees. The paper under review proves bijectively that there are \(\left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right) n^{n-k}\) Cayley trees such that exactly \(k\) neighbours of the root have a smaller label than does the root, giving a combinatorial interpretation to the binomial formula \((n+1)^n= \sum^n_{k=0}\left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right) n^{n- k}\). Several other binomial formulae are given interpretations in terms of Cayley trees. The family of Cayley trees on \([n+1]\) rooted at the vertex labeled 1 is related to the enumeration of minimal factorizations of the \(n\)-cycle \((1,2,\dots, n)\) as a product of transpositions, and the fact that there are \(n^n\) such trees is used to prove bijectively that there are \(2n^n\) ordered alternating trees (defined in the article) on \([n+1]\). For the entire collection see [Zbl 0941.00013].

Recommendations

Cited in

(26)

This page was built for publication: Enumeration of some labelled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4502530)