Séminaire Lotharingien de Combinatoire 58 (2007), Article B58a

DECREASES AND DESCENTS IN WORDS

Dominique Foata and Guo-Niu Han

ABSTRACT. The generating function for words by a multivariable statistic involving decrease, increase, descent and rise values is explicitly calculated by using the MacMahon Master Theorem and the properties of the first fundamental transformation on words. Applications to statistical study of the symmetric group are also given.

1. Introduction

In our recent papers [2, 3, 4, 5, 6, 7, 8, 9] that involve the calculations of factorial generating functions for the symmetric and hyperoctahedral groups, we have obtained several results on statistical distributions on words. In this paper we take up again the study of those word statistics in a more general context. They do not necessarily have counterparts on permutations, but are essential in this word calculus. The MacMahon Master Theorem [14, p. 97–98] and the first fundamental transformation on words [13, Chap. 10] will be our basic tools.

The number of decreases is a crucial statistic; as such it is at the origin of our word studies. The definition of decrease slightly differs from the definition of the classical descent. Let w = x_{1}x_{2} ⋯ x_{n} be an arbitrary word, whose letters are nonnegative integers. Recall that a positive integer i is said to be a descent (or descent place) of w if 1 ≤ i ≤ n − 1 and x_{i} > x_{i+1}. We say that i is a decrease of w if 1 ≤ i ≤ n − 1 and x_{i} = x_{i+1} = ⋯ = x_{j} > x_{j+1} for some j such that i ≤ j ≤ n − 1. The letter x_{i} is said to be a decrease value (respectively descent value) of w. The set of all decreases (respectively descents) is denoted by DEC(w) (respectively DES(w)). Each descent is a decrease, but not conversely. This means that DES(w) ⊂ DEC(w). However, DES(w) = DEC(w) when w is a word without repetitions.

In the present paper our intention is to go back to the study of the number of decreases, this time associated with several other word statistics, and derive the Ur-result that should have been at the origin of several of our statistical distribution studies. This Ur-result is stated in Theorem 1.1, but has two equivalent forms, as written in Theorems 1.2 and 1.3.

DOMINIQUE FOATA AND GUO-NIU HAN

In parallel with the notion of decrease, we say that that a positive integer i is an increase (respectively a rise) of w if 1 ≤ i ≤ n and x_{i} = x_{i+1} = ⋯ = x_{j} < x_{j+1} for some j such that i ≤ j ≤ n (respectively if 1 ≤ i ≤ n and x_{i} < x_{i+1}). By convention, x_{n+1} = +∞. The letter x_{i} is said to be an increase value (respectively a rise value) of w. Thus, the rightmost letter x_{n} is always a rise value. Again, the set of all increases (respectively rises) is denoted by INC(w) (respectively RISE(w)). Each rise is an increase, but not conversely. This means that RISE(w) ⊂ INC(w).

Furthermore, a position i (1 ≤ i ≤ n) is said to be a record if x_{j} ≤ x_{i} for all j such that 1 ≤ j ≤ i − 1. The letter x_{i} is said to be a record value. The set of all records of w is denoted by REC(w).

Introduce six sequences of commuting variables (X_{i}), (Y_{i}), (Z_{i}), (T_{i}), (Y′_{i}), (T′_{i}) (i = 0, 1, 2, …), and for each word w = x_{1}x_{2} … x_{n} from [0, r]^{∗} define the weight ψ(w) of w = x_{1}x_{2} … x_{n} to be

(1.1) ψ(w) := ∏_{i∈DES} X_{x_{i}} ∏_{i∈RISE\REC} Y_{x_{i}} ∏_{i∈DEC\DES} Z_{x_{i}}

× ∏_{i∈(INC\RISE)\REC} T_{x_{i}} ∏_{i∈RISE∩REC} Y′_{x_{i}} ∏_{i∈(INC\RISE)∩REC} T′_{x_{i}},

where the argument “(w)” has not been written for typographic reasons. For example, i ∈ RISE \ REC stands for i ∈ RISE(w) \ REC(w).

Example. For the word w = 3 2 4 4 5 5 5 3 1 1 1 4 1 3 5 the sets DES, DEC, INC, RISE, REC of w are indicated by bullets.

w = 3 2 4 4 5 5 5 3 1 1 1 4 1 3 5
DES = •  • •  •
DEC = •  • • • •  •
RISE =  •  •  •  • • •
INC =  • • •  • • •  • • •
REC = •  • • • • •  •

We have ψ(w) = X_{3}Y_{2}T′_{4}Y′_{4}Z_{5}Z_{5}X_{5}X_{3}T_{1}T_{1}Y_{1}X_{4}Y_{1}Y_{3}Y′_{5}.

Now let C be the (r + 1) × (r + 1) matrix

(1.2) C = ( \begin{matrix}0 & \frac{X_{1}}{1 − Z_{1}} & \frac{X_{2}}{1 − Z_{2}} & ⋯ & \frac{X_{r−1}}{1 − Z_{r−1}} & \frac{X_{r}}{1 − Z_{r}} \\ \frac{Y_{0}}{1 − T_{0}} & 0 & \frac{X_{2}}{1 − Z_{2}} & ⋯ & \frac{X_{r−1}}{1 − Z_{r−1}} & \frac{X_{r}}{1 − Z_{r}} \\ \frac{Y_{0}}{1 − T_{0}} & \frac{Y_{1}}{1 − T_{1}} & 0 & ⋯ & \frac{X_{r−1}}{1 − Z_{r−1}} & \frac{X_{r}}{1 − Z_{r}} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ \frac{Y_{0}}{1 − T_{0}} & \frac{Y_{1}}{1 − T_{1}} & \frac{Y_{2}}{1 − T_{2}} & ⋯ & 0 & \frac{X_{r}}{1 − Z_{r}} \\ \frac{Y_{0}}{1 − T_{0}} & \frac{Y_{1}}{1 − T_{1}} & \frac{Y_{2}}{1 − T_{2}} & ⋯ & \frac{Y_{r−1}}{1 − T_{r−1}} & 0 \end{matrix} ) .

DECREASES AND DESCENTS IN WORDS

Theorem 1.1. The generating function for the set [0, r]^{∗} by the weight ψ is given by

(1.3)  ∑_{w∈[0,r]^{∗}} ψ(w) = \frac{∏_{0≤j≤r}(1 + \frac{Y′_{j}}{1 − T′_{j}} )}{det(I − C)},

where I is the identity matrix of order (r + 1).

Of course, the expression 1/ det(I −C) is too redolent of the MacMahon Master Theorem [14, p. 97–98] for not having it play a crucial role in the proof of (1.3). It does indeed. However we further need the properties of the first fundamental transformation, as it is developed in Cartier-Foata [1] and also in Lothaire [13, Chap. 10]. As mentioned earlier, Theorem 1.1 must be regarded as our Ur-result. Its proof is given in Section 2. Its two equivalent forms come next. Theorem 1.2. We also have:

(1.4)  ∑_{w∈[0,r]^{∗}} ψ(w) = \frac{\begin{matrix}∏_{0≤j≤r} & \frac{1 − Z_{j}}{1 − Z_{j} + X_{j}} \\ ∏_{0≤j≤r} & \frac{1 − T′_{j}}{1 − T′_{j} + Y′_{j}} \end{matrix}}{1 − ∑_{0≤l≤r} \begin{matrix}∏_{0≤j≤l−1} & \frac{1 − Z_{j}}{1 − Z_{j} + X_{j}} \\ ∏_{0≤j≤l−1} & \frac{1 − T_{j}}{1 − T_{j} + Y_{j}} \end{matrix} \frac{X_{l}}{1 − Z_{l} + X_{l}}} .

By definition each letter equal to 0 cannot be a decrease value. Consequently, the weight ψ(w) of each word w must not contain the variables X_{0}, Z_{0}. There is then another expression for the right-hand side of (1.4) which does not involve the variables X_{0}, Z_{0}. To obtain it we factor out (1 − Z_{0})/(1 − Z_{0} + X_{0}) from both numerator and denominator of the right-hand side, as done in the next theorem. Theorem 1.3. We also have:

(1.5)  ∑_{w∈[0,r]^{∗}} ψ(w) = \frac{\begin{matrix}∏_{1≤j≤r} & \frac{1 − Z_{j}}{1 − Z_{j} + X_{j}} \\ ∏_{0≤j≤r} & \frac{1 − T′_{j}}{1 − T′_{j} + Y′_{j}} \end{matrix}}{1 − ∑_{1≤l≤r} \begin{matrix}∏_{1≤j≤l−1} & \frac{1 − Z_{j}}{1 − Z_{j} + X_{j}} \\ ∏_{0≤j≤l−1} & \frac{1 − T_{j}}{1 − T_{j} + Y_{j}} \end{matrix} \frac{X_{l}}{1 − Z_{l} + X_{l}}} .

Theorem 1.2 (and therefore Theorem 1.3) is proved in Section 3 by using a determinantal manipulation and summing the weights ψ(w) according to their so-called keys. An alternate proof of Theorem 1.2, which is not reproduced in this paper, is based on the word-analog of the Kim–Zeng transformation [11] and follows the pattern developed in our previous paper [9]. Specializations of those two theorems for deriving generating functions on words only appear in Section 6. There is however a specialization of (1.5) that deserves a special development and is now presented.

Let γ be the homomorphism defined by the following substitutions of variables:

γ := {X_{j} ← s Y_{j−1}, Z_{j} ← s Y_{j−1}, T_{j} ← Y_{j}, T′_{j} ← Y′_{j}}.

For each word w = x_{1}x_{2} ⋯ x_{n} ∈ [0, r]^{∗} we then have:

(1.6)  γ ψ(w) = ∏_{x_{i}∈INC∩REC} Y′_{x_{i}} × ∏_{x_{i}∈DEC} sY_{x_{i}−1} × ∏_{x_{i}∈INC\REC} Y_{x_{i}}.

Applying γ to (1.5) we get:

(1.7)  ∑_{w∈[0,r]^{∗}} γ ψ(w) = \frac{\frac{∏_{1≤j≤r}(1 − sY_{j−1})}{∏_{0≤j≤r}(1 − Y′_{j})}}{1 − ∑_{1≤l≤r} \frac{∏_{1≤j≤l−1}(1 − sY_{j−1})}{∏_{0≤j≤l−1}(1 − Y_{j})}sY_{l−1}} .

The above right-hand side can be further simplified as stated in the following theorem, whose proof is given in Section 4.

Theorem 1.4. We have:

(1.8) ∑_{w∈[0,r]^{∗}} γ ψ(w)

= \frac{(1 − s) ∏_{0≤j≤r−1}(1 − Y_{j}) ∏_{0≤j≤r−1}(1 − s Y_{j})}{∏_{0≤j≤r}(1 − Y′_{j}) ( ∏_{0≤j≤r−1}(1 − Y_{j}) − s ∏_{0≤j≤r−1}(1 − s Y_{j}))}.

For each word w = x_{1}x_{2} ⋯ x_{n} let inrec w denote the number of letters of w, which are increase and record values. Also let dec w be the number of decreases in w and tot w = x_{1} + x_{2} + ⋯ + x_{n} be the sum of the letters of w. Also make the substitution Y′_{j} ← RY_{j}, where R is a new variable and let ψ_{R} := γ ψ |_{Y′_{j}←R Y_{j}}, so that (1.6) becomes:

(1.9)  ψ_{R}(w) = R^{inrec w}s^{dec w} ∏_{x_{i}∈DEC} Y_{x_{i}−1} × ∏_{x_{i}∈INC} Y_{x_{i}}.

On the other hand, let

(1.10)  H(Y) := ∏_{i≥0}(1 − Y_{i})^{−1};
(1.11)  H_{r}(Y) := ∏_{0≤i≤r−1}(1 − Y_{i})^{−1} (r ≥ 0).

Using the homomorphism ψ_{R}, identity (1.8) may be rewritten as:

(1.12)  ∑_{w∈[0,r]^{∗}} ψ_{R}(w) = \frac{(1 − s)H_{r+1}(RY)}{H_{r}(sY) − sH_{r}(Y)}.

The left-hand side of (1.12) can be further expressed as a series over the symmetric groups 𝔖_{n} (n = 0, 1, …). If σ = σ(1)σ(2) ⋯ σ(n) is a permutation of 12 ⋯ n, let z = z_{1}z_{2} ⋯ z_{n} be the word defined by:

(1.13)  z_{i} := #{j : i ≤ j ≤ n − 1, σ(j) > σ(j + 1)} (1 ≤ i ≤ n),

so that z_{1} is the number of descents, des σ, and tot z = z_{1} + z_{2} + ⋯ + z_{n} is the major index, maj σ, of σ. Also, let exc σ := {i : 1 ≤ i ≤ n−1, σ(i) > i} be the number of excedances and fix σ be the number of fixed points of σ. Finally, let NIW_{n} (respectively NIW_{n}(k)) denote the set of words c = c_{1}c_{2} ⋯ c_{n}, of length n, whose letters are integers satisfying c_{1} ≥ c_{1} ≥ ⋯ ≥ c_{n} ≥ 0 (respectively k ≥ c_{1} ≥ c_{1} ≥ ⋯ ≥ c_{n} ≥ 0). With each pair (σ, c) ∈ 𝔖_{n} × NIW_{n} we associate the monomial

(1.14)  Y_{(σ,c)} := ∏_{j<σ(j)} Y_{c_{j}+z_{j}−1} × ∏_{j≥σ(j)} Y_{c_{j}+z_{j}}.

Theorem 1.5. We have:

(1.15) ∑_{n≥0} ∑_{{σ∈𝔖_{n} \atop des σ≤r}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(r−des σ)} Y_{(σ,c)} = \frac{(1 − s)H_{r+1}(RY)}{H_{r}(sY) − sH_{r}(Y)} (r ≥ 0).

When r tends to infinity in (1.15), we get the identity

(1.16)  ∑_{n≥0} ∑_{σ∈𝔖_{n}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}} Y_{(σ,c)} = \frac{(1 − s)H(RY)}{H(sY) − sH(Y)},

derived by Shareshian and Wachs [15, Theorem 2.1] using a quasisymmetric function approach. However, starting from (1.15), we can obtain a graded form of (1.16) as follows. Let

(1.17)  Y (σ; t) := ∑_{k≥0} t^{k} ∑_{c∈NIW_{n}(k)} Y_{(σ,c)}.

Theorem 1.6. The graded form of (1.16) reads:

(1.18) ∑_{n≥0} ∑_{σ∈𝔖_{n}} R^{fix σ}s^{exc σ}t^{des σ}Y (σ; t) = ∑_{r≥0} t^{r} \frac{(1 − s)H_{r+1}(RY)}{H_{r}(sY) − sH_{r}(Y)}.

Section 5 starts with redescribing the Gessel–Reutenauer standardization [10] and showing how it is used to prove Theorem 1.5. The graded form (1.18) is deduced from Theorem 1.5 by a standard series manipulation. We end the paper by giving some specializations of our Ur-theorem and also by showing that the distribution of (fix, exc, des, maj) over the symmetric groups that was found earlier in [9] using the word-analog of the Kim–Zeng transformation [11], can also be deduced from our Ur-result in two different manners.

2. Proof of Theorem 1.1

A word w = y_{1}y_{2} ⋯ y_{n} ∈ [0, r]^{∗} having no equal letters in succession is called an h-derangement (horizontal derangement). The set of all hderangement words in [0, r]^{∗} is denoted by [0, r]_{h}^{∗}. Let α be the substitution of variables defined by

α := {Z_{i} ← 0, T_{i} ← 0, T′_{i} ← 0}.

Then

α ψ(w) = ψ(w) = ∏_{i∈DES} X_{x_{i}} ∏_{i∈RISE\REC} Y_{x_{i}} ∏_{i∈RISE∩REC} Y′_{x_{i}},

if w is an h-derangement and α ψ(w) = 0 otherwise. The following specialization of Theorem 1.1 is obtained by taking the image of identity (1.3) under α.

Theorem 2.1. We have

(2.1)  ∑_{w∈[0,r]_{h}^{∗}} ψ(w) = \frac{∏_{0≤j≤r}(1 + Y′_{j})}{det(I − α C)}.

Even though Theorem 2.1 is a special case of Theorem 1.1, it can still be used as a lemma to prove Theorem 1.1. We proceed as follows.

Proof of Theorem 1.1. Let w be a word from [0, r]^{∗}. The key of w is defined to be the h-derangement k derived from w by erasing all letters x_{i} such that x_{i} = x_{i+1}. For instance, the key of w = 324455531114135 is the h-derangement k = 3245314135.

Let β be the substitution of variables defined by

β := {X_{i} ← X_{i}/(1 − Z_{i}), Y_{i} ← Y_{i}/(1 − T_{i}), Y′_{i} ← Y′_{i}/(1 − T′_{i})}.

Then, the generating function for the set of all w whose key is k by the weight ψ is given by

∑_{w, key(w)=k} ψ(w) = β ψ(k).

Since β α C = C we have

∑_{w∈[0,r]^{∗}} ψ(w) = ∑_{k∈[0,r]_{h}^{∗}} ∑_{key(w)=k} ψ(w) = ∑_{k∈[0,r]_{h}^{∗}} β ψ(k)

= β( ∑_{k∈[0,r]_{h}^{∗}} ψ(k)) = β \frac{∏_{0≤j≤r}(1 + Y′_{j})}{det(I − α C)} [by (2.1)]

= \frac{∏_{0≤j≤r}(1 + β Y′_{j})}{det(I − β α C)} = \frac{∏_{0≤j≤r}(1 + \frac{Y′_{j}}{1 − T′_{j}} )}{det(I − C)}.

Proof of Theorem 2.1. A letter x_{i} which is a record and also a rise value is called a riserec value. For each h-derangement k = x_{1}x_{2} ⋯ x_{n} let w_{0} be the nondecreasing word composed of all the riserec values of k and let k_{0} be the word obtained from k by erasing all the riserec values of k. Since the letters of w_{0} can be uniquely inserted into the word k_{0} for reconstructing k, the map

(2.2)  k ↦ (w_{0}, k_{0})

is a bijection of the set of all h-derangements onto the the set of all pairs (w_{0}, k_{0}) such that w_{0} is a nondecreasing word and k_{0} is an h-derangement without any riserec value. Moreover, if a letter x_{j} of k is a record value and therefore becomes a letter, say, x_{0,i} of w_{0}, then x_{0,i} is a rise of w_{0} if and only if x_{j} is a rise of k. Therefore

(2.3)  ψ(k) = ψ(w_{0})ψ(k_{0}).

Next apply the first fundamental transformation to k_{0} (see [13, § 10.5]), say, u = F_{1}(k_{0}). Let us recall how F_{1} is defined by means of an example. Start with the word k_{0} = 5 3 6 5 3 2 4 6 1 2 4 3 1 and cut it before each record value to get k_{0} = 5 3 | 6 5 3 2 4 | 6 1 2 4 3 1 =: w_{1} | w_{2} | w_{3}. In each compartment move the leftmost letter to the end to obtain the cyclic shifts δw_{1} = 3 5, δw_{2} = 5 3 2 4 6, δw_{3} = 1 2 4 3 1 6 and form the two-row

matrix (\begin{matrix}δw_{1} & δw_{2} & δw_{3} \\ w_{1} & w_{2} & w_{3} \end{matrix}) = (\begin{matrix}3 & 5 & 5 & 3 & 2 & 4 & 6 & 1 & 2 & 4 & 3 & 1 & 6 \\ 5 & 3 & 6 & 5 & 3 & 2 & 4 & 6 & 1 & 2 & 4 & 3 & 1 \end{matrix}). Finally, rearrange the

vertical biletters of that two-row matrix in such a way that the entries on the top row are in nondecreasing order, assuming that two biletters \binom{a}{a′}, \binom{b}{b′} can commute only when a ≠ b. We then obtain the two-row matrix

F_{1}(k_{0}) := (\overline{u} ; u) = (\begin{matrix}1 & 1 & 2 & 2 & 3 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 \\ 6 & 3 & 3 & 1 & 5 & 5 & 4 & 2 & 2 & 3 & 6 & 4 & 1 \end{matrix}).

We can characterize the word u = y_{1}y_{2} ⋯ y_{m} when we start with an hderangement k_{0}. Let \overline{u} = z_{1}z_{2} ⋯ z_{m} be the nondecreasing rearrangement of u (and of k_{0}). By construction y_{i} ≠ z_{i} for 1 ≤ i ≤ m. Such a word u is called a v-derangement (vertical derangement). Denote the set of all v-derangements in [0, r]^{∗} by [0, r]_{v}^{∗}. Then F_{1} provides a bijection of the set of all h-derangements onto the set of all pairs (w_{0}, u) such that w_{0} is a nondecreasing word and u is a v-derangement:

k ↦ (w_{0}, k_{0}) ↦ (w_{0}, u) where F_{1}(k_{0}) = \binom{\overline{u}}{u}.

Example. k = 2535653246124316 ↦ (w_{0} = 256, k_{0} = 5365324612431)

↦ (w_{0} = 256, u = 6331554223641),

since  F_{1}(k_{0}) = (\overline{u} ; u) = (\begin{matrix}1 & 1 & 2 & 2 & 3 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 \\ 6 & 3 & 3 & 1 & 5 & 5 & 4 & 2 & 2 & 3 & 6 & 4 & 1 \end{matrix} ) .

Let Φ be the homomorphism generated by

Φ\binom{i}{j} := \{ \begin{matrix}X_{j}, & if j > i; \\ Y_{j}, & if j < i. \end{matrix}

By the property [13, Chap. 10] of the first fundamental transformation, we have

(2.4)  ψ(k) = ψ(w_{0})ψ(k_{0}) = ψ(w_{0})Φ\binom{\overline{u}}{u}.

Let ND(r) be the set of all non-decreasing words from [0, r]^{∗}. It follows from the properties of the above bijections that

∑_{w∈[0,r]_{h}^{∗}} ψ(w) = ∑_{w_{0}∈ND(r)} ψ(w_{0}) ∑_{u∈[0,r]_{v}^{∗}} Φ\binom{\overline{u}}{u};

∑_{w_{0}∈ND(r)} ψ(w_{0}) = ∏_{0≤j≤r}(1 + Y′_{j}).

There remains to prove the identity:

(2.5)  ∑_{u∈[0,r]_{v}^{∗}} Φ\binom{\overline{u}}{u} = \frac{1}{det(I − α C)}.

The proof is based on the celebrated MacMahon Master Theorem, using the noncommutative version developed in [1, Chap. 4]. Also see [13, Chap. 10]. Consider the matrix

C′′ = ( \begin{matrix}0 & \binom{0}{1} & \binom{0}{2} & ⋯ & \binom{0}{r−1} & \binom{0}{r} \\ \binom{1}{0} & 0 & \binom{1}{2} & ⋯ & \binom{1}{r−1} & \binom{1}{r} \\ \binom{2}{0} & \binom{2}{1} & 0 & ⋯ & \binom{2}{r−1} & \binom{2}{r} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ \binom{r−1}{0} & \binom{r−1}{1} & \binom{r−1}{2} & ⋯ & 0 & \binom{r−1}{r} \\ \binom{r}{0} & \binom{r}{1} & \binom{r}{2} & ⋯ & \binom{r}{r−1} & 0 \end{matrix} ) .

As shown in the references just mentioned, there holds the identity

(2.6)  \frac{1}{det(I − C′′)} = ∑_{u∈[0,r]_{v}^{∗}} \binom{\overline{u}}{u}.

Applying Φ to both sides of (2.6) yields (2.5).

3. Proof of Theorem 1.2

The proof of Theorem 1.2 is similar to the proof of Theorem 1.1 given in the previous section. First we prove the following specialization of Theorem 1.2.

Theorem 3.1. We have:

(3.1)  ∑_{w∈[0,r]_{h}^{∗}} ψ(w) = \frac{∏_{0≤j≤r} \frac{1 + Y′_{j}}{1 + X_{j}}}{1 − ∑_{0≤l≤r} ∏_{0≤j≤l−1} \frac{1 + Y_{j}}{1 + X_{j}} \frac{X_{l}}{1 + X_{l}}} .

Proof. Denote the left-hand side of (3.1) by LHS. From Theorem 2.1 we have

LHS = \frac{∏_{0≤j≤r}(1 + Y′_{j})}{D},

where

D = | \begin{matrix}1 & −X_{1} & −X_{2} & ⋯ & −X_{r−1} & −X_{r} \\ −Y_{0} & 1 & −X_{2} & ⋯ & −X_{r−1} & −X_{r} \\ −Y_{0} & −Y_{1} & 1 & ⋯ & −X_{r−1} & −X_{r} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ −Y_{0} & −Y_{1} & −Y_{2} & ⋯ & 1 & −X_{r} \\ −Y_{0} & −Y_{1} & −Y_{2} & ⋯ & −Y_{r−1} & 1 \end{matrix} |.

In the above determinant subtract the r-th row from the (r + 1)-st one; then the (r − 1)-st from the r-th row; …, the first row from the second. We obtain:

D = | \begin{matrix}1 & −X_{1} & −X_{2} & ⋯ & −X_{r−1} & −X_{r} \\ −1 − Y_{0} & 1 + X_{1} & 0 & ⋯ & 0 & 0 \\ 0 & −1 − Y_{1} & 1 + X_{2} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 + X_{r−1} & 0 \\ 0 & 0 & 0 & ⋯ & −1 − Y_{r−1} & 1 + X_{r} \end{matrix} |.

Now expand the determinant by the cofactors of the first row. We get:

D = ∏_{1≤j≤r} (1 + X_{j}) − ∑_{1≤l≤r}( ∏_{0≤j≤l−1}(1 + Y_{j}) ∏_{l+1≤j≤r} (1 + X_{j}))X_{l}.

We further have:

D = ∏_{1≤j≤r} (1 + X_{j}) + X_{0} ∏_{1≤j≤r} (1 + X_{j})

− ∑_{0≤l≤r}( ∏_{0≤j≤l−1}(1 + Y_{j}) ∏_{l≤j≤r} (1 + X_{j}))\frac{X_{l}}{1 + X_{l}} .

DECREASES AND DESCENTS IN WORDS

Hence,

(3.2)  LHS = \frac{∏_{0≤j≤r} \frac{(1 + Y′_{j})}{(1 + X_{j})}}{1 − ∑_{0≤l≤r} ∏_{0≤j≤l−1} \frac{(1 + Y_{j})}{(1 + X_{j})} \frac{X_{l}}{1 + X_{l}}} .

Proof of Theorem 1.2. As in the proof of Theorem 1.1 we may write:

∑_{w∈[0,r]^{∗}} ψ(w) = ∑_{k∈[0,r]_{h}^{∗}} ∑_{key(w)=k} ψ(w) = ∑_{k∈[0,r]_{h}^{∗}} β ψ(k) = β(LHS).

Using (3.2) it is immediate to verify that β(LHS) is equal to the right-hand side of (1.4).

4. Proof of Theorem 1.4

First, we may check that

∏_{0≤j≤r}(1 − sY_{j}) − ∏_{0≤j≤r}(1 − Y_{j})

= ∑_{0≤l≤r} ∏_{0≤j≤l}(1 − sY_{j}) ∏_{l+1≤j≤r}(1 − Y_{j}) − ∑_{0≤l≤r} ∏_{0≤j≤l−1}(1 − sY_{j}) ∏_{l≤j≤r}(1 − Y_{j})
=(1 − s) ∑_{0≤l≤r} Y_{l} ∏_{0≤j≤l−1}(1 − sY_{j}) ∏_{l+1≤j≤r}(1 − Y_{j}).

Proof of Theorem 1.4. Using (1.7) we have:

\frac{1}{1 − s ∑_{0≤l≤r−1} Y_{l} ∏_{0≤j≤l−1}(1 − sY_{j})/ ∏_{0≤j≤l}(1 − Y_{j})}

= \frac{∏_{0≤j≤r−1}(1 − Y_{j})}{∏_{0≤j≤r−1}(1 − Y_{j}) − s ∑_{0≤l≤r−1} Y_{l} ∏_{0≤j≤l−1}(1 − sY_{j}) ∏_{l+1≤j≤r−1}(1 − Y_{j})}

= \frac{∏_{0≤j≤r−1}(1 − Y_{j})}{∏_{0≤j≤r−1}(1 − Y_{j}) − s( ∏_{0≤j≤r−1}(1 − sY_{j}) − ∏_{0≤j≤r−1}(1 − Y_{j}))/(1 − s)}

= \frac{(1 − s) ∏_{0≤j≤r−1}(1 − Y_{j})}{∏_{0≤j≤r−1}(1 − Y_{j}) − s ∏_{0≤j≤r−1}(1 − sY_{j})}.

5. Proofs of Theorems 1.5 and 1.6

An updated version of the Gessel–Reutenauer standardization [10] is fully described in our previous paper [9], Section 5. The standardization consists of mapping each word w from [0, r]^{∗} of length n onto a pair (σ, c), where σ ∈ 𝔖_{n} and c = c_{1}c_{2} ⋯ c_{n} is a word of length n, whose letters are nonnegative integers having the property: r − des σ ≥ c_{1} ≥ c_{2} ≥ ⋯ ≥ c_{n} ≥ 0, the symbol des σ being the number of descents of σ. We recall the construction of the inverse (σ, c) ↦ w by means of an example.

\begin{aligned}Id & = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ → σ & = & 1 & \underline{5} & \underline{6} & \underline{8} & \underline{13} & \underline{14} & 7 & \underline{17} & 4 & 10 & \underline{15} & \underline{18} & \underline{19} & 2 & 9 & 16 & \underline{20} & \underline{22} & 3 & 11 & 12 & 21 \\ z & = & 4 & 4 & 4 & 4 & 4 & 4 & 3 & 3 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ → c & = & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \overline{c} & = & 6 & 6 & 6 & 6 & 6 & 6 & 5 & 4 & 3 & 3 & 3 & 3 & 3 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 \\ σ & = & (16) & (12 & 18 & 22 & 21) & (10) & (7) & (4 & 8 & 17 & 20 & 11 & 15 & 9) & (2 & 5 & 13 & 19 & 3 & 6 & 14) & (1) \\ σ̌ & = & 16 & 12 & 18 & 22 & 21 & 10 & 7 & 4 & 8 & 17 & 20 & 11 & 15 & 9 & 2 & 5 & 13 & 19 & 3 & 6 & 14 & 1 \\ ↦ w & = & 2 | & \underline{3} & \underline{2} & 1 & 1 | & 3 | & 5 | & \underline{6} & \underline{4} & \underline{2} & 1 & \underline{3} & 2 & 3 | & \underline{6} & \underline{6} & \underline{3} & 1 & \underline{6} & \underline{6} & 2 | & 6 \end{aligned}

In the example n = 22. The second row contains the values σ(i) (i = 1, 2, …, n) of the starting permutation σ. The excedances σ(i) > i are underlined, while the fixed points σ(i) = i are written in boldface. The third row is the vector z = z_{1}z_{2} ⋯ z_{n} defined by (1.13) so that z_{1} = des σ and tot z = z_{1} + z_{2} + ⋯ + z_{n} is the major index of σ denoted by maj σ, as already mentioned in the Introduction. The fourth row is the starting nonincreasing word c = c_{1}c_{2} ⋯ c_{n}. The fifth row \overline{c} = \overline{c}_{1}\overline{c}_{2} ⋯ \overline{c}_{n} is the word defined by

\overline{c}_{i} := z_{i} + c_{i} (1 ≤ i ≤ n).

In the sixth row the permutation σ is represented as the product of its disjoint cycles. Each cycle starts with its minimum element and those minimum elements are in decreasing order when reading the whole word from left to right. When removing the parentheses in the sixth row we obtain the seventh row denoted by σ̌ = σ̌(1)σ̌(2) ⋯ σ̌(n). The bottom row is the word w = x_{1}x_{2} ⋯ x_{n} corresponding to the pair (σ, c) defined by

x_{i} := \overline{c}_{σ̌(i)} (1 ≤ i ≤ n).

For instance, σ̌(9) = 8 and \overline{c}(8) = 4. Hence x_{9} = 4. The decrease values of w have been underlined.

It can be verified that all the above steps are reversible and that w ↦ (σ, c) is a bijection of the set of all words from [0, r]^{∗} of length n onto the set of pairs (σ, c) such that σ ∈ 𝔖_{n}, des σ ≤ r and c = c_{1}c_{2} ⋯ c_{n} is a word satisfying r − des σ ≥ c_{1} ≥ c_{2} ≥ ⋯ ≥ c_{n} ≥ 0. Furthermore, x_{i} is a decrease value of w if and only if σ̌(i) < σ̌(i + 1), if and only if σ̌(i) < σ(σ̌(i)). Also x_{i} is an increase and record value of w if and only if σ̌(i) is a fixed point of σ. Hence,

ψ_{R}(w) = R^{inrec w}s^{dec w} ∏_{x_{i}∈DEC} Y_{x_{i}−1} ∏_{x_{i}∈INC} Y_{x_{i}}

= R^{fix σ}s^{exc σ} ∏_{σ̌(i)<σ(σ̌(i))} Y_{\overline{c}_{σ̌(i)}−1} ∏_{σ̌(i)≥σ(σ̌(i))} Y_{\overline{c}_{σ̌(i)}}

= R^{fix σ}s^{exc σ} ∏_{j<σ(j)} Y_{\overline{c}_{j}−1} ∏_{j≥σ(j)} Y_{\overline{c}_{j}}

= R^{fix σ}s^{exc σ} ∏_{j<σ(j)} Y_{c_{j}+z_{j}−1} ∏_{j≥σ(j)} Y_{c_{j}+z_{j}}

= R^{fix σ}s^{exc σ}Y_{(σ,c)}.

Consequently,

(5.1)  ∑_{w∈[0,r]^{∗}} ψ_{R}(w) = ∑_{n≥0} ∑_{{σ∈𝔖_{n} \atop des σ≤r}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(r−des σ)} Y_{(σ,c)}.

This achieves the proof of Theorem 1.5 by taking identity (1.12) into account.

For the proof of Theorem 1.6 we multiply both sides of (1.15) by t^{r} and sum over r ≥ 0. We obtain:

∑_{r≥0} t^{r} \frac{(1 − s)H_{r+1}(RY)}{H_{r}(sY) − sH_{r}(Y)}

= ∑_{r≥0} t^{r} ∑_{n≥0} ∑_{{σ∈𝔖_{n} \atop des σ≤r}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(r−des σ)} Y_{(σ,c)}

= ∑_{n≥0} ∑_{r≥0} t^{r} ∑_{0≤j≤r} ∑_{{σ∈𝔖_{n} \atop des σ=r−j}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(j)} Y_{(σ,c)}

= ∑_{n≥0} ∑_{j≥0} t^{j} ∑_{r≥j} t^{r−j} ∑_{{σ∈𝔖_{n} \atop des σ=r−j}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(j)} Y_{(σ,c)}

= ∑_{n≥0} ∑_{j≥0} t^{j} ∑_{k≥0} t^{k} ∑_{{σ∈𝔖_{n} \atop des σ=k}} R^{fix σ}s^{exc σ} ∑_{c∈NIW_{n}(j)} Y_{(σ,c)}

= ∑_{n≥0} ∑_{σ∈𝔖_{n}} R^{fix σ}s^{exc σ}t^{des σ} ∑_{j≥0} t^{j} ∑_{c∈NIW_{n}(j)} Y_{(σ,c)}

= ∑_{n≥0} ∑_{σ∈𝔖_{n}} R^{fix σ}s^{exc σ}t^{des σ}Y (σ; t).

6. Specializations and q-Calculus

In Theorem 1.4, replace Y_{j}, Y′_{j} (j ≥ 0) by u. We get the identity

(6.1)  ∑_{w∈[0,r]^{∗}} s^{dec w}u^{λw} = \frac{1 − s}{(1 − u)^{r+1}(1 − us)^{−r} − s(1 − u)},

where λw denotes the length of w.

Now replace X_{j} (j ≥ 0) by us and the other variables by u in Theorem 1.2. We then recover the classical generating function for words by number of descents:

(6.2)  ∑_{w∈[0,r]^{∗}} s^{des w}u^{λw} = \frac{1 − s}{(1 − u + us)^{r+1} − s}.

As was proved in our paper [9] (formula (1.15)), when multiplying (6.1) (and not (6.2)) by t^{r} and summing over r ≥ 0 we get the generating function for the pair (exc, des) over the symmetric groups:

(6.3)  ∑_{r≥0} t^{r} ∑_{w∈[0,r]^{∗}} s^{dec w}u^{λw} = ∑_{n≥0} \frac{u^{n}}{(1 − t)^{n+1}} ∑_{σ∈𝔖_{n}} s^{exc σ}t^{des σ}.

Now, recall the traditional notation of the q-ascending factorial

(a; q)_{n} = \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}), & if n ≥ 1. \end{matrix}

Theorem 6.1. The factorial generating function for the distributions of the vector (fix, exc, des, maj) over the symmetric groups 𝔖_{n} is given by

(6.4) ∑_{n≥0} \frac{u^{n}}{(t; q)_{n+1}} ∑_{σ∈𝔖_{n}} R^{fix σ}s^{exc σ}t^{des σ}q^{maj σ}

= ∑_{r≥0} t^{r} \frac{1}{(uR; q)_{r+1}} \frac{(1 − sq) (u; q)_{r} (usq; q)_{r}}{((u; q)_{r} − sq(usq; q)_{r})} .

The theorem was proved in our previous paper [9] by means of the wordanalog of the Kim–Zeng transformation [11] and the Gessel–Reutenauer standardization. Here, it is a simple consequence of Theorem 1.6 by applying the homomorphism ϕ generated by ϕ(Y_{j}) := uq^{j} (j ≥ 0) and ϕ(s) := sq to both sides of (1.18).

We proceed as follows. First, ϕH_{r}(Y) = ∏_{0≤j≤r−1}(1 − uq^{j})^{−1} = 1/(u; q)_{r} and

\begin{aligned}ϕ\frac{(1 − s)H_{r+1}(RY)}{H_{r}(sY) − sH_{r}(Y)} & = \frac{(1 − sq)/(uR; q)_{r+1}}{1/(usq; q)_{r} − sq/(u; q)_{r}} \\ & = \frac{(1 − sq)(u; q)_{r} (usq; q)_{r}}{(uR; q)_{r+1} (((u; q)_{r} − sq(usq; q)_{r})}. \end{aligned}

Then, for (σ, c) ∈ 𝔖_{n} × NIW_{n}

ϕY_{(σ,c)} = u^{n}q^{tot c+tot z−exc σ} = q^{maj σ−exc σ}u^{n}q^{tot c};
ϕY (σ; t) = q^{maj σ−exc σ}u^{n} ∑_{j≥0} t^{j} ∑_{c∈NIW_{n}(j)} q^{tot c} = q^{maj σ−exc σ} \frac{u^{n}}{(t; q)_{n+1}} ;

so that

ϕ(R fix^{σ} s^{exc σ}t^{des σ}Y (σ; t)) = R^{fix σ}(sq)^{exc σ}t^{des σ}q^{maj σ−exc σ} \frac{u^{n}}{(t; q)_{n+1}} .

Hence, the image of identity (1.18) under ϕ gives back (6.4).

There is still another proof, which we now describe. In identity (1.4) make the substitutions X_{j} ← usq^{j}, Y_{j} ← uq^{j}, Z_{j} ← usq^{j}, T_{j} ← uq^{j}, Y′_{j} ← uRq^{j}, T′_{j} ← uRq^{j}. The weight ψ(w) becomes s^{dec w}R^{inrec w}u^{λw}q^{tot w}, and (1.4) yields the identity

(6.5)  ∑_{w∈[0,r]^{∗}} s^{dec w}R^{inrec w}u^{λw}q^{tot w} = \frac{\frac{(us; q)_{r+1}}{(uR; q)_{r+1}}}{1 −∑_{0≤l≤r} \frac{(us; q)_{l}}{(u; q)_{l}} usq^{l}} .

Now, use the q-telescoping argument provided by Krattenthaler [12]:

\frac{(us; q)_{l}}{(u; q)_{l}} usq^{l} = \frac{sq}{1 − sq} (\frac{(us; q)_{l+1}}{(u; q)_{l}} − \frac{(us; q)_{l}}{(u; q)_{l−1}} ) (1 ≤ l ≤ r).

We obtain:

(6.6) ∑_{w∈[0,r]^{∗}} s^{dec w}R^{inrec w}u^{λw}q^{tot w} = \frac{1}{(uR; q)_{r+1}} \frac{(1 − sq) (u; q)_{r} (usq; q)_{r}}{((u; q)_{r} − sq(usq; q)_{r})} .

The summation can also be made over the symmetric groups by using the Gessel–Reutenauer standardization w ↦ (σ, c). This time only the following properties are needed:

dec w = exc σ; tot w = maj σ + tot c; inrec w = fix σ.

Multiply (6.6) by t^{r} and sum over r ≥ 0. We get:

∑_{r≥0} t^{r} ∑_{n≥0} ∑_{{σ∈𝔖_{n} \atop des σ≤r}} ∑_{c∈NIW_{n}(r−des σ)} s^{exc σ}R^{fix σ}u^{n}q^{maj σ+tot c}

= ∑_{r≥0} t^{r} \frac{1}{(uR; q)_{r+1}} \frac{(1 − sq) (u; q)_{r} (usq; q)_{r}}{((u; q)_{r} − sq(usq; q)_{r})} .

Following the same pattern as in the proof of Theorem 1.6 we again derive identity (6.4).

Acknowledgements. The authors should like to thank Christian Krattenthaler and Jiang Zeng for their careful readings and knowledgeable remarks.

References

[1] Pierre Cartier, Dominique Foata. Problèmes combinatoires de commutation et réarrangements. Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85), 88 pages. Also freely available on the Sémin. Lothar. Combin. website.

[2] Dominique Foata, Guo-Niu Han. Signed words and permutations, I: A fundamental transformation, Proc. Amer. Math. Soc., vol. 135, 2007, p. 31–40.

[3] ——, ——. Signed words and permutations, II; The Euler–Mahonian polynomials, Electronic J. Combin., 11(2), #R22, 2005, 18 pages.

[4] ——, ——. Signed words and permutations, III; The MacMahon Verfahren, Sémin. Lothar. Combin., 54, [B25a], 2006, 20 pages.

[5] ——, ——. Signed words and permutations, IV; Fixed and pixed points, preprint 21 pages, Israel J. Math., 2006, (to appear).

[6] ——, ——. Signed words and permutations, V; A sextuple distribution, preprint 24 pages, Ramanujan J., 2007, (to appear).

[7] ——, ——. Fix-Mahonian Calculus, I: Two transformations, preprint 16 pages, 2006, Europ. J. Combin. (to appear).

[8] ——, ——. Fix-Mahonian Calculus, II: Further statistics, preprint 13 pages, 2006, J. Combinatorial Theory, Ser. A (to appear).

[9] ——, ——. Fix-Mahonian Calculus, III: A quadruple distribution, preprint 26 p., 2007, Monatshefte für Math. (to appear).

[10] Ira Gessel, Christophe Reutenauer. Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, vol. 64, 1993, p. 189– 215.

[11] Dongsu Kim, Jiang Zeng. A new decomposition of derangements, J. Combin. Theory Ser. A, vol. 96, 2001, p. 192–198.

[12] Christian Krattenthaler. Personal communication, 2007.

[13] M. Lothaire. Combinatorics on Words. Addison-Wesley, London 1983 (Encyclopedia of Math. and its Appl., 17).

[14] Percy Alexander MacMahon. Combinatory Analysis, vol. 1 and 2. Cambridge, Cambridge Univ. Press, 1915. (Reprinted by Chelsea, New York, 1955).

[15] John Shareshian, Michelle Wachs. q-Eulerian polynomials, excedance number and major index, Electronic Research Announcements of the Amer. Math. Soc., vol. 13, 2007, p. 33-45. See also the proceedings of the FPSAC 2007, Tianjin.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu@math.u-strasbg.fr