A COMBINATORIAL PROOF OF A RESULT OF HETYEI AND REINER ON FOATA-STREHL TYPE PERMUTATION TREES

MIKLÓS BÓNA

Abstract. 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 ith 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.