A survey of alternating permutations

2010/01/01 by Richard P. Stanley · 6 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Advanced Mathematical Identities #Mathematics #Combinatorics

paper · doi:10.1090/conm/531/10466

openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

Abstract. A permutation a1a2 · · · an of 1, 2,..., n is alternating if a1> a2 < a3> a4 < · · ·. We survey some aspects of the theory of alternating permutations, beginning with the famous result of André that if En is the number of alternating permutations of 1, 2,..., n, then P xn n≥0 En = sec x + tan x. n! Topics include refinements and q-analogues of En, various occurrences of En in mathematics, longest alternating subsequences of permutations, umbral enumeration of special classes of alternating permutations, and the connection between alternating permutations and the cd-index of the symmetric group. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday 1. Basic enumerative properties. Let Sn denote the symmetric group of all permutations of [n]: = 1, 2,..., n. A permutation w = a1a2 · · · an ∈ Sn is called alternating if a1> a2 < a3> a4 < · · ·. In other words, ai < ai+1 for i even, and ai> ai+1 for i odd. Similarly w is reverse alternating if a1 < a2> a3 < a4> · · ·. (Some authors reverse these definitions.) Let En denote the number of alternating permutations in Sn. (Set

Citations

• Bernoulli-Euler updown numbers associated with function singularities, their combinatorics and arithmetics
• Proof of a Conjecture of Chan, Robbins, and Yuen
• A continued fraction expansion for a q-tangent function
• On the distribution of the length of the longest increasing subsequence of random permutations
• A continued fraction expansion for a q-tangent function: An elementary proof
• Combinatorial Enumeration
• Combinatorics of geometrically distributed random variables: New q-tangent and q-secant numbers

Cited by

• The \varvecr-alternating permutations
• Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
• On models of the braid arrangement and their hidden symmetries
• The Möbius function of the consecutive pattern poset
• More bijections for Entringer and Arnold families
• Alternating permutation [wikipedia]

Related

• A Survey of Alternating Permutations
• Alternating permutations and symmetric functions
• A Note on Alternating Permutations
• On Pattern Avoiding Alternating Permutations
• A property of alternating groups