Annals of Combinatorics 1 (1997) 119-122

A Combinatorial Proof of a Result of Hetyei and Reiner on Foata-Strehl-Type Permutation Trees

Miklós Bóna

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Received March 18, 1997

AMS Subject Classification: 05E10, 05E15

Abstract. We give a combinatorial proof of the known result that there are exactly n!/3 permutations of length n in the minmax tree representation of which the ith node is a leaf.

Keywords: permutations, trees, group action, fixed points


1.  D. Foata and M.P. Schützenberger, Nombres d'Euler et permutations alternantes, In: A Survey of Combinatorial Theory, J.N. Srivastava et al., Eds., Amsterdam, North--Holland, 1973, pp. 173–187.

2.  D. Foata and V. Strehl, Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z. 137 (1974) 257–264.

3.  D. Foata and V. Strehl, Euler numbers and variations of permutations, In: Colloquio Internazionale sulle Teorie Combinatorie, Roma, 1973, Atti Dei Convegni Lincei 17, Accademia Nazionale dei Lincei, 1976, Tomo I, pp. 119–131.

4.  G. Hetyei and E. Reiner, Permutation trees and variation statistics, In: Proc. of the 9th Conference on Formal Power Series and Algebraic Combinatorics, Vienna, 1997, to appear.

5.  M. Purtill, Andrè permutations, lexicographic shellability, and the cd--index of a convex polytope, Trans. Amer. Math. Soc. 338 (1) (1993) 77–104.

Get the LaTex | DVI | PS file of this abstract.