Combinatorial statistics on alternating permutations
type: Item
instance of: scholarly article
title: Combinatorial statistics on alternating permutations
zbMATH Open document ID: 0916.05002
DOI: 10.1023/A:1008689811936
published in: Journal of Algebraic Combinatorics
publication date: 1999-07-19T00:00:00Z
review text: Following the definition of the genus of a hypermap given in [\textit{R. Cori}, ``Un code pur les graphes planaires et ses applications,'' Astérisque 27, 1-169 (1975; Zbl 0313.05115)], specialized to hypermaps of one vertex, the paper under review defines a permutation \(\alpha\) of \(\{1, 2,\dots,N\}\) to be of genus 0 if the number of cycles of \(\alpha\) plus the number of cycles of \(\alpha^{-1} (1,2, \dots,N)\) is equal to \(N+1\). It is shown that genus-0 alternating permutations are counted by Schröder numbers. This result is generalized to count these permutations according to the number of alternating descents (\(i\) is an alternating descent of \(\alpha\) if \(\alpha (i+2) >\alpha(i))\) in terms of the \(q\)-analogue of Schröder numbers. Alternating genus-0 permutations are shown to be Baxter permutations, and alternating Baxter permutations are counted in terms of the \(q\)-analogue of Catalan numbers. These results are used to relate the alternating descent statistic to lattice path enumeration, the rank generating function and characteristic polynomial of noncrossing partition lattices, and polytopes obtained as face-figures of the associahedron [\textit{C. W. Lee}, ``The associahedron and triangulations of the \(n\)-gon,'' Eur. J. Comb. 10, No. 6, 551-560 (1989; Zbl 0682.52004)].
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1228568
zbMATH Keywords: permutation
zbMATH Keywords: Schröder numbers
zbMATH Keywords: Baxter permutations
zbMATH Keywords: Catalan numbers
zbMATH Keywords: alternating descent statistic
zbMATH Keywords: lattice path enumeration
zbMATH Keywords: associahedron
author: Serge Dulucq
author: Rodica Simion
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: A Theorem on Reciprocal Polynomials with Applications to Permutations and Compositions
cites work: On Fixed Points of the Composite of Commuting Functions
cites work: Shellable and Cohen-Macaulay Partially Ordered Sets
cites work: Q3952144
cites work: Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths
cites work: The number of Baxter permutations
cites work: Q4769056
cites work: Q4071773
cites work: Shuffle of parenthesis systems and Baxter permutations
cites work: Maps, hypermaps and their automorphisms: A survey. I
cites work: Q4867146
cites work: Multichains, non-crossing partitions and trees
cites work: Chains in the lattice of noncrossing partitions
cites work: The lattice of non-crossing partitions and the Birkhoff-Lewis equations
cites work: Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
cites work: The associahedron and triangulations of the \(n\)-gon
cites work: Baxter permutations rise again
cites work: The enumeration of Hamiltonian polygons in triangular maps
cites work: Q5549086
cites work: Q3922688
cites work: On the structure of the lattice of noncrossing partitions
cites work: Q3748279
cites work: A Census of Hamiltonian Polygons
cites work: Counting rooted maps by genus. II
cites work: Q3847965
cites work: Lectures on Polytopes
full work available at URL: a:1008689811936
OpenAlex ID: W73795681
description: scientific article; zbMATH DE number 1228568