The Descent Set and Connectivity Set of a Permutation

Richard P. Stanley^{1} Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 USA

                      rstan@math.mit.edu

Abstract The descent set D(w) of a permutation w of 1, 2, …, n is a standard and wellstudied 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.

1 A duality between descents and connectivity.

Let 𝔖_{n} denote the symmetric group of permutations of [n] = {1, 2, …, n}, and let w = a_{1}a_{2} ⋯ a_{n} ∈ 𝔖_{n}. The descent set D(w) is defined by

D(w) = {i : a_{i} > a_{i+1}} ⊆ [n − 1].

The descent set is a well-known and much studied statistic on permutations with many applications, e.g., [6, Exam. 2.24, Thm. 3.12.1][7, §7.23]. Now define the connectivity set C(w) by

C(w) = {i : a_{j} < a_{k} for all j ≤ i < k} ⊆ [n − 1].  (1)

The connectivity set seems not to have been considered before except for equivalent definitions by Comtet [3, Exer. VI.14] and Callan [1] with no further development. H. Wilf has pointed out to me that the set of splitters of a permutation arising in the algorithm Quicksort [8, §2.2] coincides with the connectivity set. Some notions related to the connectivity set have been investigated. In particular, a permutation w with C(w) = ∅ is called connected or indecomposable. If f(n) denotes the number of connected permutations in 𝔖_{n}, then Comtet [3, Exer. VI.14] showed that

1Partially supported by NSF grant #DMS-9988459 and by the Institut Mittag-Leffler.

∑_{n≥1} f(n)x^{n} = 1 − \frac{1}{∑_{n≥0} n!x^{n}} ,

and he also considered the number #C(w) of components. He also obtained [2][3, Exer. VII.16] the complete asymptotic expansion of f(n). For further references on connected permutations, see Sloane [4]. In this paper we will establish a kind of “duality” between descent sets and connectivity sets.

We write S = {i_{1}, …, i_{k}}_{<} to denote that S = {i_{1}, …, i_{k}} and i_{1} < ⋯ < i_{k}. Given S = {i_{1}, …, i_{k}}_{<} ⊆ [n − 1], define

η(S) = i_{1}! (i_{2} − i_{1})! ⋯ (i_{k} − i_{k−1})! (n − i_{k})!.

Note that η(S) depends not only on S but also on n. The integer n will always be clear from the context. The first indication of a duality between C and D is the following result.

Proposition 1.1. Let S ⊆ [n − 1]. Then

#{w ∈ 𝔖_{n} : S ⊆ C(w)} = η(S)
#\{w ∈ 𝔖_{n} : S ⊇ D(w)\} = \frac{n!}{η(S)}.

Proof. The result for D(w) is well-known, e.g., [6, Prop. 1.3.11]. To obtain a permutation w satisfying S ⊇ D(w), choose an ordered partition (A_{1}, …, A_{k+1}) of [n] with #A_{j} = i_{j}−i_{j−1} (with i_{0} = 0, i_{k+1} = n) in n!/η(S) ways, then arrange the elements of A_{1} in increasing order, followed by the elements of A_{2} in increasing order, etc.

Similarly, to obtain a permutation w satisfying S ⊆ C(w), choose a permutation of [i_{1}] in i_{1}! ways, followed by a permutation of [i_{1} + 1, i_{2}] := {i_{1} + 1, i_{1} + 2, …, i_{2}} in (i_{2} − i_{1})! ways, etc. □

Let S, T ⊆ [n − 1]. Our main interest is in the joint distribution of the statistics C and D, i.e., in the numbers

X_{ST} = #\{w ∈ 𝔖_{n} : C(w) = \overline{S}, D(w) = T \},

where \overline{S} = [n − 1] − S. (It will be more notationally convenient to use this definition of X_{ST} rather than having C(w) = S.) To this end, define

Z_{ST} = #\{w ∈ 𝔖_{n} : \overline{S} ⊆ C(w), T ⊆ D(w)\}
= ∑_{{S′⊇S \atop T′⊇T}} X_{S′T′}.  (2)

For instance, if n = 4, S = {2, 3}, and T = {3}, then Z_{ST} = 3, corresponding to the permutations 1243, 1342, 1432, while X_{ST} = 1, corresponding to 1342. Tables of X_{ST} for n = 3 and n = 4 are given in Figure 1, and for n = 5 in Figure 2.

S\T ∅ 1 2 12
∅ 1
1 0 1
2 0 0 1
12 0 1 1 1
S\T ∅ 1 2 3 12 13 23 123
∅ 1
1 0 1
2 0 0 1
3 0 0 0 1
12 0 1 1 0 1
13 0 0 0 0 0 1
23 0 0 1 1 0 0 1
123 0 1 2 1 2 4 2 1

Figure 1: Table of X_{ST} for n = 3 and n = 4

S\T ∅ 1 2 3 4 12 13 14 23 24 34 123 124 134 234 1234
∅ 1
1 0 1
2 0 0 1
3 0 0 0 1
4 0 0 0 0 1
12 0 1 1 0 0 1
13 0 0 0 0 0 0 1
14 0 0 0 0 0 0 0 1
23 0 0 1 1 0 0 0 0 1
24 0 0 0 0 0 0 0 0 0 1
34 0 0 0 1 1 0 0 0 0 0 1
123 0 1 2 1 0 2 4 0 2 0 0 1
124 0 0 0 0 0 0 0 1 0 1 0 0 1
134 0 0 0 0 0 0 1 1 0 0 0 0 0 1
234 0 0 1 2 1 0 0 0 2 4 2 0 0 0 1
1234 0 1 3 3 1 3 10 8 6 10 3 3 8 8 3  1

Figure 2: Table of X_{ST} for n = 5

Theorem 1.1. We have

Z_{ST} = \{ \begin{matrix}η(\overline{S})/η(\overline{T}), & if S ⊇ T; \\ 0, & otherwise, \end{matrix}

Proof. Let w = a_{1} ⋯ a_{n} ∈ 𝔖_{n}. If i ∈ C(w) then a_{i} < a_{i+1}, so i ∉ D(w). Hence Z_{ST} = 0 if S ⊉ T.

Assume therefore that S ⊇ T. Let C(w) = {c_{1}, …, c_{j}}_{<} with c_{0} = 0 and c_{j+1} = n. Fix 0 ≤ h ≤ j, and let

[c_{h}, c_{h+1}] ∩ \overline{T} = \{c_{h} = i_{1}, i_{2}, …, i_{k} = c_{h+1}\}_{<}.

If w = a_{1} ⋯ a_{n} with \overline{S} ⊆ C(w) and T ⊆ D(w), then the number of choices for a_{c_{h}} + 1, a_{c_{h}} + 2, …, a_{c_{h+1}} is just the multinomial coefficient

\binom{c_{h+1} − c_{h}}{i_{2} − i_{1}, i_{3} − i_{2}, …, i_{k} − i_{k−1}} := \frac{(c_{h+1} − c_{h})!}{(i_{2} − i_{1})! (i_{3} − i_{2})! ⋯ (i_{k} − i_{k−1})!}.

Taking the product over all 0 ≤ h ≤ j yields η(\overline{S})/η(\overline{T}). □

Theorem 1.1 can be restated matrix-theoretically. Let M = (M_{ST}) be the matrix whose rows and columns are indexed by subsets S, T ⊆ [n − 1] (taken in some order), with

M_{ST} = \{ \begin{matrix}1, & if S ⊇ T; \\ 0, & otherwise. \end{matrix}

Let D = (D_{ST}) be the diagonal matrix with D_{SS} = η(\overline{S}). Let Z = (Z_{ST}), i.e., the matrix whose (S, T)-entry is Z_{ST} as defined in (2). Then it is straightforward to check that Theorem 1.1 can be restated as follows:

Z = DMD^{−1}.  (3)

Similarly, let X = (X_{ST}). Then it is immediate from equations (2) and (3) that

MXM = Z.  (4)

The main result of this section (Theorem 1.2 below) computes the inverse of the matrices X, Z, and a matrix Y = (Y_{ST}) intermediate between X and Z. Namely, define

Y_{ST} = #\{w ∈ 𝔖_{n} : \overline{S} ⊆ C(w), T = D(w)\}.  (5)

It is immediate from the definition of matrix multiplication and (4) that the matrix Y satisfies

Y = MX = ZM^{−1}.  (6)

In view of equations (3), (4) and (6) the computation of Z^{−1}, Y^{−1}, and X^{−1} will reduce to computing M^{−1}, which is a simple and well-known result. For any invertible matrix N = (N_{ST}), write N_{ST}^{−1} for the (S, T)-entry of N^{−1}.

Lemma 1.1. We have

M_{ST}^{−1} = (−1)^{#S+#T} M_{ST} .  (7)

Proof. Let f, g be functions from subsets of [n] to ℝ (say) related by

f(S) = ∑_{T ⊆S} g(T).  (8)

Equation (7) is then equivalent to the inversion formula

g(S) = ∑_{T ⊆S}(−1)^{#(S−T)}f(T).  (9)

This is a standard combinatorial result with many proofs, e.g., [6, Thm. 2.1.1, Exam. 3.8.3]. □

Theorem 1.2. The matrices Z, Y, X have the following inverses:

Z_{ST}^{−1} = (−1)^{#S+#T} Z_{ST}  (10)
Y_{ST}^{−1} = (−1)^{#S+#T} #\{w ∈ 𝔖_{n} : \overline{S} = C(w), T ⊆ D(w)\}  (11)
X_{ST}^{−1} = (−1)^{#S+#T} X_{ST} .  (12)

Proof. By equations (3), (4), and (6) we have

Z^{−1} = DM^{−1}D^{−1}, Y^{−1} = MDM^{−1}D^{−1}, X^{−1} = MDM^{−1}D^{−1}M.

Equation (10) is then an immediate consequence of Lemma 1.1 and the definition of matrix multiplication.

Since Y^{−1} = MZ^{−1} we have for fixed S ⊇ U that

Y_{SU}^{−1} = ∑_{T : S⊇T ⊇U}(−1)^{#T +#U}Z_{T U}
= ∑_{T : S⊇T ⊇U}(−1)^{#T +#U}#\{w ∈ 𝔖_{n} : \overline{T} ⊆ C(w), U ⊆ D(w)\}
= ∑_{\overline{T} : \overline{U}⊆\overline{T} ⊆\overline{S}}(−1)^{#T +#U}#\{w ∈ 𝔖_{n} : \overline{T} ⊆ C(w), U ⊆ D(w)\}.

Equation (11) is now an immediate consequence of the Principle of Inclusion-Exclusion (or of the equivalence of equations (8) and (9)). Equation (12) is proved analogously to (11) using X^{−1} = Y^{−1}M. □

Note. The matrix M represents the zeta function of the boolean algebra B_{n} [6, §3.6]. Hence Lemma 1.1 can be regarded as the determination of the Möbius function of B_{n} [6, Exam. 3.8.3]. All our results can easily be formulated in terms of the incidence algebra of B_{n}.

Note. The matrix Y arose from the theory of quasisymmetric functions in response to a question from Louis Billera and Vic Reiner and was the original motivation for this paper, as we now explain. See for example [7, §7.19] for an introduction to quasisymmetric functions. We will not use quasisymmetric functions elsewhere in this paper.

Let Comp(n) denote the set of all compositions α = (α_{1}, …, α_{k}) of n, i.e, α_{i} ≥ 1 and ∑ α_{i} = n. Let α = (α_{1}, …, α_{k}) ∈ Comp(n), and let 𝔖_{α} denote the subgroup of 𝔖_{n} consisting of all permutations w = a_{1} ⋯ a_{n} such that {1, …, α_{1}} = {a_{1}, …, a_{α_{1}}}, {α_{1} + 1, …, α_{1} + α_{2}} = {a_{α_{1}+1}, …, a_{α_{1}+α_{2}}}, etc. Thus 𝔖_{α} ≅ 𝔖_{α_{1}} × ⋯ × 𝔖_{α_{k}} and #𝔖_{α} = η(S), where S = {α_{1}, α_{1} + α_{2}, …, α_{1} + ⋯ + α_{k−1}}. If w ∈ 𝔖_{n} and D(w) = {i_{1}, …, i_{k}}_{<}, then define the descent composition co(w) by

co(w) = (i_{1}, i_{2} − i_{1}, …, i_{k} − i_{k−1}, n − i_{k}) ∈ Comp(n).

Let L_{α} denote the fundamental quasisymmetric function indexed by α [7, (7.89)], and define

R_{α} = ∑_{w∈𝔖_{α}} L_{co(w)}.  (13)

Given α = (α_{1}, …, α_{k}) ∈ Comp(n), let S_{α} = {α_{1}, α_{1} + α_{2}, …, α_{1} + ⋯ + α_{k−1}}. Note that w ∈ 𝔖_{α} if and only if S_{α} ⊆ C(w). Hence equation (13) can be rewritten as

R_{α} = ∑_{β} Y_{\overline{S_{α}}S_{β}}L_{β},

with Y_{\overline{S_{α}}S_{β}} as in (5). It follows from (5) that the transition matrix between the bases L_{α} and R_{α} is lower unitriangular (with respect to a suitable ordering of the rows and columns). Thus the set {R_{α} : α ∈ Comp(n)} is a ℤ-basis for the additive group of all homogeneous quasisymmetric functions over ℤ of degree n. Moreover, the problem of expressing the L_{β}’s as linear combinations of the R_{α}’s is equivalent to inverting the matrix Y = (Y_{ST}).

The question of Billera and Reiner mentioned above is the following. Let P be a finite poset, and define the quasisymmetric function

K_{P} = ∑_{f} x^{f},

where f ranges over all order-preserving maps f : P → {1, 2, … } and x^{f} = ∏_{t∈P} x_{f(t)} (see [7, (7.92)]). Billera and Reiner asked whether the quasisymmetric functions K_{P} generate (as a ℤ-algebra) or even span (as an additive abelian group) the space of all quasisymmetric functions. Let m denote an m-element antichain. The ordinal sum P ⊕ Q of two posets P, Q with disjoint elements is the poset on the union of their elements satisfying s ≤ t if either (1) s, t ∈ P and s ≤ t in P, (2) s, t ∈ Q and s ≤ t in Q, or (3) s ∈ P and t ∈ Q. If α = (α_{1}, …, α_{k}) ∈ Comp(n) then let P_{α} = α_{1} ⊕⋯⊕α_{k}. It is easy to see that K_{P_{α}} = R_{α}, so the K_{P_{α}}’s form a ℤ-basis for the homogeneous quasisymmetric functions of degree n, thereby answering the question of Billera and Reiner.

2 Multisets and inversions.

In this section we consider two further aspects of the connectivity set: (1) an extension to permutations of a multiset and (2) a q-analogue of Theorem 1.2 when the number of inversions of w is taken into account.

Let T = {i_{1}, …, i_{k}}_{<} ⊆ [n − 1]. Define the multiset

N_{T} = {1^{i_{1}}, 2^{i_{2}−i_{1}}, …, (k + 1)^{n−i_{k}}}.

Let 𝔖_{N_{T}} denote the set of all permutations of N_{T}, so #𝔖_{N_{T}} = n!/η(T); and let w = a_{1}a_{2} ⋯ a_{n} ∈ 𝔖_{N_{T}}. In analogy with equation (1) define

C(w) = {i : a_{j} < a_{k} for all j ≤ i < k}.

(Note that we could have instead required only a_{j} ≤ a_{k} rather than a_{j} < a_{k}. We will not consider this alternative definition here.)

Proposition 2.1. Let S, T ⊆ [n − 1]. Then

#\{w ∈ 𝔖_{N_{T}} : C(w) = S\} = (XM)_{\overline{S} \overline{T}}
= ∑_{U : U⊇\overline{T}} X_{\overline{S}U}
= #\{w ∈ 𝔖_{n} : C(w) = S, D(w) ⊇ \overline{T} \}.

Proof. The equality of the three expressions on the right-hand side is clear, so we need only show that

#\{w ∈ 𝔖_{N_{T}} : C(w) = S\} = #\{w ∈ 𝔖_{n} : C(w) = S, D(w) ⊇ \overline{T} \}.  (14)

Let T = \{i_{1}, …, i_{k}\}_{<} ⊆ [n − 1]. Given w ∈ 𝔖_{n} with C(w) = S and D(w) ⊇ \overline{T}, in w^{−1} replace 1, 2, …, i_{1} with 1’s, replace i_{1} + 1, …, i_{2} with 2’s, etc. It is easy to check that this yields a bijection between the sets appearing on the two sides of (14). □

Let us now consider q-analogues Z(q), Y (q), X(q) of the matrices Z, Y, X. The q-analogue will keep track of the number inv(w) of inversions of w = a_{1} ⋯ a_{n} ∈ 𝔖_{n}, where we define

inv(w) = #{(i, j) : i < j, a_{i} > a_{j}}.

Thus define

X(q)_{ST} = ∑_{{w∈𝔖n \atop C(w)=\overline{S}, D(w)=T}} q^{inv(w)},

and similarly for Z(q)_{ST} and Y (q)_{ST}. We will obtain q-analogues of Theorems 1.1 and 1.2 with completely analogous proofs.

Write (j) = 1 + q + ⋯ + q^{j−1} and (j)! = (1)(2) ⋯ (j), the standard q-analogues of j and j!. Let S = {i_{1}, …, i_{k}}_{<} ⊆ [n − 1], and define

η(S, q) = i_{1}! (i_{2} − i_{1})! ⋯ (i_{k} − i_{k−1})! (n − i_{k})!.

Let T ⊆ [n − 1], and let \overline{T} = \{i_{1}, …, i_{k}\}_{<}. Define

z(T) = \binom{i_{1}}{2} + \binom{i_{2} − i_{1}}{2} + ⋯ + \binom{n − i_{k}}{2}.

Note that z(T) is the least number of inversions of a permutation w ∈ 𝔖_{n} with T ⊆ D(w).

Z(q)_{ST} = \{ \begin{matrix}q^{z(T)}η(\overline{S}, q)/η(\overline{T} , q), & if \overline{S} ∩ T = ∅; \\ 0, & otherwise. \end{matrix}

Proof. Preserve the notation from the proof of Theorem 1.1. If (s, t) is an inversion of w (i.e., s < t and a_{s} > a_{t}) then for some 0 ≤ h ≤ j we have c_{h} + 1 ≤ s < t ≤ c_{h+1}. It is a standard fact of enumerative combinatorics (e.g., [5, (21)][6, Prop. 1.3.17]) that if U = {u_{1}, …, u_{r}}_{<} ⊆ [m − 1] then

∑_{{v∈𝔖m \atop D(v)⊆U}} q^{inv(v)} = \binom{m}{u_{1}, u_{2} − u_{1}, …, m − u_{r}}

:= \frac{(m)!}{(u_{1})! (u_{2} − u_{1})! ⋯ (m − u_{r})!},

a q-multinomial coefficient. From this it follows easily that if \overline{U} = \{y_{1}, …, y_{s}\}_{<} then

∑_{{v∈𝔖m \atop D(v)⊇U}} q^{inv(v)} = q^{z(T)}\binom{m}{y_{1}, y_{2} − y_{1}, …, m − y_{s}}.

Hence we can parallel the proof of Theorem 1.1, except instead of merely counting the number of choices for the sequence u = (a_{c_{h}}, a_{c_{h}} + 1, …, a_{c_{h+1}}) we can weight this choice by q^{inv(u)}. Then

∑_{u} q^{inv(u)} = q^{\binom{i_{2}−i_{1}}{2}+···+\binom{i_{k}−i_{k−1}}{2}}\binom{c_{h+1} − c_{h}}{i_{2} − i_{1}, i_{3} − i_{2}, …, i_{k} − i_{k−1}},

summed over all choices u = (a_{c_{h}}, a_{c_{h}} + 1, …, a_{c_{h+1}}). Taking the product over all 0 ≤ h ≤ j yields q^{z(T)}η(\overline{S}, q)/η(\overline{T} , q). □

Theorem 2.2. The matrices Z(q), Y (q), X(q) have the following inverses:

Z(q)_{ST}^{−1} = (−1)^{#S+#T} Z(1/q)_{ST}
Y (q)_{ST}^{−1} = (−1)^{#S+#T} ∑_{{w∈𝔖n \atop \overline{S}=C(w), T ⊆D(w)}} q^{−inv(w)}

X(q)_{ST}^{−1} = (−1)^{#S+#T} X(1/q)_{ST} .

Proof. Let D(q) = (D(q)_{ST}) be the diagonal matrix with D(q)_{SS} = η(\overline{S}, q). Let Q(q) be the diagonal matrix with Q(q)_{SS} = q^{z(S)}. Exactly as for (3), (4) and (6) we obtain

Z(q) = D(q)MD(q)^{−1}Q(q)
MX(q)M = Z(q)
Y (q) = MX(q) = Z(q)M^{−1}.

The proof now is identical to that of Theorem 1.2. □

Let us note that Proposition 2.1 also has a straightforward q-analogue; we omit the details.

3 Acknowledgments

I am grateful to the referee for several suggestions that have enhanced the readability of this paper.

References

[1] D. Callan, Counting stabilized-interval-free permutations, J. Integer Sequences (electronic) 7 (2004), Article 04.1.8.

[2] L. Comtet, Sur les coefficients de l’inverse de la série formelle ∑ n!t^{n}, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569–572.

[3] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence \underline{A003319}.

[5] R. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory (A) 20 (1976), 336–356.

[6] R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, 1986; second printing, Cambridge University Press, 1996.

[7] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999.

[8] H. Wilf, Algorithms and Complexity, second ed., A K Peters, 2002.

2000 Mathematics Subject Classification: Primary 05A05. Keywords: descent set, connected permutation, connectivity set.

(Concerned with sequence \underline{A003319}.)

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

Return to Journal of Integer Sequences home page.