Enumerating alternating trees
From MaRDI portal
A tree \(T_n\) with \(n\) labelled nodes is said to be an alternating tree if the labels of the nodes on every path form an alternating sequence. \textit{A. Postnikov} [J. Comb. Theory, Ser. A 79, No. 2, 360-366 (1997; Zbl 0876.05042)] used generating functions and Lagrange's inversion formula to derive an expression for the number of unrooted alternating trees \(T_n\). The present authors give a bijective proof of his result. They also show that there are \(2(n-1)^{n-1}\) and \((n-1)^{n-2}\) rooted and unrooted alternating ordered trees \(T_n\).
Recommendations
Cites work
Cited in
(13)- The pessimistic search and the straightening involution for trees
- Rooted forests that avoid sets of permutations
- A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
- Root cones and the resonance arrangement
- Embedding small digraphs and permutations in binary trees and split trees
- Enumerating Ordered Trees Lexicographically
- scientific article; zbMATH DE number 6928770 (Why is no real title available?)
- Enumeration of trees by inversions
- Increasing trees and alternating permutations
- Some equidistributed statistics and applications to hook length formulas
- Enumeration results for alternating tree families
- Alternating Whitney sums and matchings in trees. II
- A bijective enumeration of tiered trees
This page was built for publication: Enumerating alternating trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5937130)
