Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8

The Descent Set and Connectivity Set of a Permutation

Richard P. Stanley
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA 02139
USA

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.

(Concerned with sequence A003319 .)

Received July 18 2005; revised version received August 16 2005. Published in Journal of Integer Sequences, August 24 2005.