𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Permutation Trees and Variation Statistics

✍ Scribed by Gábor Hetyei; Ethan Reiner

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
277 KB
Volume
19
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we exploit binary tree representations of permutations to give a combinatorial proof of Purtill's result [8] that

where A n is the set of André permutations, v cd (σ ) is the cd-statistic of an André permutation and v ab (σ ) is the ab-statistic of a permutation. Using Purtill's proof as a motivation we introduce a new 'Foata-Strehl-like' action on permutations. This Z n-1 2 -action allows us to give an elementary proof of Purtill's theorem, and a bijection between André permutations of the first kind and alternating permutations starting with a descent. A modified version of our group action leads to a new class of André-like permutations with structure similar to that of simsun permutations.

📜 SIMILAR VOLUMES

Signed Permutation Statistics and Cycle
Signed Permutation Statistics and Cycle Type
✍ Victor Reiner 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 294 KB

We derive a multivariate generating function which counts signed permutations by their cycle type and two other descent statistics, analogous to a result of Gessel and Reutenauer [4,5] for (unsigned) permutations. The derivation uses a bijection which is the hyperoctahedral analogue of Gessel's neck

Permutation graphs: Connected domination
Permutation graphs: Connected domination and Steiner trees
✍ Charles J. Colbourn; Lorna K. Stewart 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 702 KB

Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

Representation of permutations, combinat
Representation of permutations, combinations and dihedral elements as trees
✍ B.J. Arnow 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 162 KB

Permutations and combinations of n objects as well as the elements of the dihedral group of order 2n (i.e. flips and rotation of an n-gun) are represented as nodes of trees. The algorithms for generating the nodes and traversing the trees are illustrated using flowcharts and specific walk-throughs f