Enumerating alternating trees (Q5937130): Difference between revisions

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\).