A Combinatorial proof of a result of Hetyei and Reiner on Foata-Strehl type permutation trees

Miklós Bóna

We give a combinatorial proof of the result of Hetyei and Reiner that there are exactly $n!/3$ permutations of length $n$ in the minmax tree representation of which the $i$th node is a leaf. We also prove the new result that the number of $n$-permutations in which this node has one child is $n!/3$ as well, implying that the same holds for those in which this node has two children.