The Descent Set and Connectivity Set of a Permutation

2005/07/11 by Richard P. Stanley, Stanley, Richard P.
Computer Science · Mathematics · #05A05 #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Topological and Geometric Data Analysis #math.CO #msc:05A05

paper · pdf · doi:10.48550/arxiv.math/0507224

12 pages

arxiv created 2005/07/11 · openalex publication_date 2005/07/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The descent set D(w) of a permutation w of 1,2,...,n is a standard and well-studied statistic. We introduce a new statistic, the connectivity set C(w), and show that it is a kind of dual object to D(w). The duality is stated in terms of the inverse of a matrix that records the joint distribution of D(w) and C(w). We also give a variation involving permutations of a multiset and a q-analogue that keeps track of the number of inversions of w.

Related

• Permutations with a Given X-Descent Set
• Equidistribution of (X,Y)-descents, (X,Y)-adjacent pairs, and (X,Y)-place-value pairs on permutations
• Width-k Generalizations of Classical Permutation Statistics
• A central limit theorem for a new statistic on permutations
• The peak and descent statistics over ballot permutations