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

DOI10.1007/BF02558469zbMATH0927.05003OpenAlexW2016409962MaRDI QIDQ1293437FDOQ1293437

Authors Miklós Bóna

Publication date 13 December 1999

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9703209

zbMATH Keywords

treepermutationsgroup actionfixed points

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Exact enumeration problems, generating functions (05A15)

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 $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.

Recommendations

• Minimax trees and André polynomials
• A short proof of a result of Foata and Zeilberger
• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• scientific article; zbMATH DE number 892276

Cites work

• Andre Permutations, Lexicographic Shellability and the cd-Index of a Convex Polytope
• Permutation trees and variation statistics

Cited in

(2)

• Minimax trees and André polynomials
• A combinatorial proof of a result of Gessel and Greene

This page was built for publication: A combinatorial proof of a result of Hetyei and Reiner on Foata-Strehl-type permutation trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293437)