A generalized enumeration of labeled trees and reverse Prüfer algorithm (Q2384578): Difference between revisions

Let \(\mathcal{T}_n\) be the set of trees on \([n]=\{1,2, \dots, n \}\). A vertex \(v\) of a rooted tree \(T \in \mathcal{T} _n\) is called a leader if \(v\) has no smaller descendants in \(\mathcal{T}\). \textit{I. M. Gessel} and \textit{S. Seo} [Electron. J. Comb. 11, Research paper R27, 23 p. (2004--2005; Zbl 1080.05005)] showed by using generating functions that \[ \sum _{T \in {\mathcal{T} _n}} u^{l(T)}c^{d_T(1)} = uP_{n-1}(1,u,cu) \,, \] where \(l(T)\) is the number of leaders in \(T\), \(d_T(1)\) is the degree of 1 in \(T\), and \(P_n(a,b,c)=c\prod _{i=1}^{n-1}(ia +(n-i)b+c)\). A new proof of this formula is presented by giving an algorithm (the reverse Prüfer algorithm) which produces a code from a tree in \(\mathcal{T} _n\).