Continued fractions for permutation statistics

Abstract

We explore a bijection between permutations and colored Motzkin paths that has been used in different forms by Foata and Zeilberger, Biane, and Corteel. By giving a visual representation of this bijection in terms of so-called cycle diagrams, we find simple translations of some statistics on permutations (and subsets of permutations) into statistics on colored Motzkin paths, which are amenable to the use of continued fractions. We obtain new enumeration formulas for subsets of permutations with respect to fixed points, excedances, double excedances, cycles, and inversions. In particular, we prove that cyclic permutations whose excedances are increasing are counted by the Bell numbers.

final version formatted for DMTCS

References in corpus (2)

• Exact and asymptotic enumeration of cyclic permutations according to descent set
• Cycle up-down permutations

Cited by in corpus (6)

• Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions
• Exact and asymptotic enumeration of cyclic permutations according to descent set
• Consecutive patterns in circular permutations
• Brändén's $(p,q)$-Eulerian polynomials, André permutations and continued fractions
• Bijective Enumeration and Sign-Imbalance for Permutation Depth and Excedances
• Equidistributions around special kinds of descents and excedances