The pessimistic search and the straightening involution for trees (Q1266368)

The trees \(T\) considered here have \(n\) vertices labeled 1 (the root of \(T\)) through \(n\). Vertex \(i\) is said to be above vertex \(j\) if vertex \(i\) lies in the path joining vertex \(j\) to the root. An inversion in \(T\) is a pair of vertices \((i, j)\) such that \(i<j\) and \(j\) is above \(i\). The inversion polynomial for all rooted trees of order \(n\) is given by \(J_n(q)= \sum_{| T|= n}q^{\text{inv}(T)}\) where \(\text{inv}(T)\) is the number of inversions of \(T\). This polynomial was determined by \textit{C. L. Mallows} and \textit{J. Riordan} [Bull. Am. Math. Soc. 74, 92-94 (1968; Zbl 0242.05004)] in terms of a generating function. The pessimistic search on \(T\) may be recursively defined as follows. Suppose \(r\) is the root of \(T\) and \(\{T_1, T_2,\dots, T_k\}\) is the set of subtrees of the root \(r\) linearly ordered by the overall minimum elements contained in the subtrees. In the pessimistic search one visits the root first, then recursively searches \(T_1, T_2,\dots, T_k\). The pessimistic order of \(T\) is the sequence of vertices of \(T\) which reflects the pessimistic search. Next, the straightening involution is developed; it relates the inversion polynomial evaluated at \(q=-1\) to the number of even rooted trees. Finally, the author obtains a differential equation for the inversion polynomial of cyclic trees evaluated at \(q=-1\) thus solving a problem posed by \textit{I. M. Gessel}, \textit{B. E. Sagan} and \textit{Y.-N. Yeh} [J. Graph Theory 19, No. 4, 435-459 (1995; Zbl 0833.05045)].