A generalized enumeration of labeled trees and reverse Prüfer algorithm (Q2384578): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Seung-Hyun Seo / rank | |||
Property / author | |||
Property / author: Seung-Hyun Seo / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2021763682 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0601009 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A refinement of Cayley's formula for trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees / rank | |||
Normal rank |
Latest revision as of 10:42, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalized enumeration of labeled trees and reverse Prüfer algorithm |
scientific article |
Statements
A generalized enumeration of labeled trees and reverse Prüfer algorithm (English)
0 references
10 October 2007
0 references
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\).
0 references
tree
0 references
Prüfer code
0 references