PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 00, Number 0, Xxxx 2005

SIGNED WORDS AND PERMUTATIONS, I; A FUNDAMENTAL TRANSFORMATION

DOMINIQUE FOATA AND GUO-NIU HAN

This paper is dedicated to the memory of Percy Alexander MacMahon.

Abstract. The statistics major index and inversion number, usually defined on ordinary words, have their counterparts in signed words, namely the socalled flag-major index and flag-inversion number. We give the construction of a new transformation on those signed words that maps the former statistic onto the latter one. It is proved that the transformation also preserves two other set-statistics: the inverse ligne of route and the lower records.

1. Introduction

The second fundamental transformation, as it was called later on (see [16], chap. 10 or [15], ex. 5.1.1.19), was described in these proceedings [8]. Let w = x_{1}x_{2} … x_{m} be a (finite) word, whose letters x_{1}, x_{2}, …, x_{m} are integers. The integer-valued statistics Inversion Number “inv” and Major Index “maj” attached to the word w are defined by

(1.1)  inv w := ∑_{1≤i≤m−1} ∑_{i<j} χ(x_{i} > x_{j}};
(1.2)  maj w := ∑_{1≤i≤m−1} i χ(x_{i} > x_{i+1});

making use of the χ-notation that maps each statement A to the value χ(A) = 1 or 0 depending on whether A is true or not.

If m = (m_{1}, m_{2}, …, m_{r}) is a sequence of r nonnegative integers, the rearrangement class of the nondecreasing word 1^{m_{1}}2^{m_{2}} … r^{m_{r}}, that is, the class of all the words than can be derived from 1^{m_{1}}2^{m_{2}} … r^{m_{r}} by permutation of the letters, is denoted by R_{m}. The second fundamental transformation, denoted by Φ, maps each word w on another word Φ(w) and has the following properties:

(a) maj w = inv Φ(w);

(b) Φ(w) is a rearrangement of w and the restriction of Φ to each rearrangement class R_{m} is a bijection of R_{m} onto itself.

Further properties were proved later on by Foata, Schützenberger [10] and Björner, Wachs [5], in particular, when the transformation is restricted to act on rearrangement classes R_{m} such that m_{1} = ⋯ = m_{r} = 1, that is, on symmetric groups 𝔖_{r}.

\begin{matrix}c \\ ◯ \end{matrix}2005 American Mathematical Society

Received by the editors March 7, 2005.

1991 Mathematics Subject Classification. Primary 05A15, 05A30, 05E15.

Key words and phrases. Flag-inversion number, flag-major index, length function, signed permutations, signed words.

The purpose of this paper is to construct an analogous transformation not simply on words, but on signed words, so that new equidistribution properties on classical statistics, such as the (Coxeter) length function (see [7, p. 9], [14, p. 12]), defined on the group B_{n} of the signed permutations can be derived. By signed word we understand a word w = x_{1}x_{2} … x_{m}, whose letters are positive or negative integers. If m = (m_{1}, m_{2}, …, m_{r}) is a sequence of nonnegative integers such that m_{1} +m_{2} + ⋯ + m_{r} = m, let B_{m} be the set of all rearrangements w = x_{1}x_{2} … x_{m} of the sequence 1^{m_{1}}2^{m_{2}} … r^{m_{r}}, with the convention that some letters i may be replaced by their opposite values −i. For typographical reasons we shall use the notation \overline{i} := −i in the sequel. The class B_{m} contains 2^{m}\binom{m}{m_{1},m_{2},... ,m_{r}} signed words. When m_{1} = m_{2} = ⋯ = m_{r} = 1, m = r, the class B_{m} is simply the group B_{m} of the signed permutations of order m.

Next, the statistics “inv” and “maj” must be adapted to signed words and correspond to classical statistics when applied to signed permutations. Let

(ω; q)_{n} := \{ \begin{matrix}1, & if n = 0; \\ (1 − ω)(1 − ωq) … (1 − ωq^{n−1}), & if n ≥ 1; \end{matrix}

denote the usual q-ascending factorial in a ring element ω and

\left[{m_{1} + ⋯ + m_{r} \atop m_{1}, …, m_{r}}\right]_{q} := \frac{(q; q)_{m_{1}+···+m_{r}}}{(q; q)_{m_{1}} ⋯ (q; q)_{m_{r}}}

be the q-multinomial coefficient. Back to MacMahon [17, 18, 19] it was known that the above q-multinomial coefficient, which is the true q-analog of the cardinality of R_{m}, was the generating function for the class R_{m} by either one of the statistics “inv” or “maj.” Consequently, the generating function for B_{m} by the new statistics that are to be introduced on B_{m} must be a plausible q-analog of the cardinality of B_{m}. The most natural q-analog we can think of is certainly (−q; q)_{m}\left[{m_{1}+···+m_{r} \atop m_{1},... ,m_{r}}\right]_{q},

that tends to 2^{m}\binom{m_{1}+···+m_{r}}{m_{1},... ,m_{r}} when q tends to 1. As a substitute for “inv” we are led to introduce the following statistic “finv,” called the flag-inversion number, which will be shown to meet our expectation, that is,

(1.3)  (−q; q)_{m}\left[{m_{1} + ⋯ + m_{r} \atop m_{1}, …, m_{r}}\right]_{q} = ∑_{w∈B_{m}} q^{finv w}.

This identity is easily proved by induction on r. Let w = x_{1}x_{2} … x_{m} be a signed word from the class B_{m}. To define finv w we use “inv” defined in (1.1), together with

(1.4)  \overline{inv} w := ∑_{1≤i≤m−1} ∑_{i<j} χ(\overline{x}_{i} > x_{j})

and define

(1.5)  finv w := inv w + \overline{inv} w + ∑_{1≤j≤m} χ(x_{j} < 0).

The salient feature of this definition of “finv” is the fact that it does not involve the values of the letters, but only the comparisons between letters, so that it can be applied to each arbitrary signed word. Moreover, the definition of “finv” is similar to that of “fmaj” given below in (1.7). Finally, its restriction to the group B_{m} of the signed permutations is the traditional length function:

(1.6)  finv|_{B_{m}} = ℓ.

This is easily shown, for instance, by using the formula derived by Brenti [6] for the length function ℓ over B_{n}, that reads.

ℓ w = inv w + ∑_{1≤j≤m} |x_{j}| χ(x_{j} < 0).

Next, the statistic “maj” is to be replaced by “fmaj”, the flag-major index, introduced by Adin and Roichman [1] for signed permutations. The latter authors (see also [2]) showed that “fmaj” was equidistributed with the length function ℓ over B_{n}. Their definition of “fmaj” can be used verbatim for signed words, as well as their definition of “fdes.” For a signed word w = x_{1}x_{2} … x_{m} those definitions read:

(1.7)  fmaj w := 2 maj w + ∑_{1≤j≤m} χ(x_{j} < 0);
(1.8)  fdes w := 2 des w + χ(x_{1} < 0);

where “des” is the usual number of descents des w := ∑_{i} χ(x_{i} > x_{i+1}). We postpone the construction of our transformation Ψ on signed words to the next section. The main purpose of this paper is to prove the following theorem.

Theorem 1.1. The transformation Ψ constructed in section 2 has the following properties:

(a) fmaj w = finv Ψ(w) for every signed word w;

(b) the restriction of Ψ to each rearrangement class B_{m} of signed words is a bijection of B_{m} onto itself, so that “fmaj” and “finv” are equidistributed over each class B_{m}.

Definition 1.1. Let w = x_{1}x_{2} … x_{m} ∈ B_{m} be a signed word. We say that a nonnegative integer i belongs to the inverse ligne of route, Iligne w, of w, if one of the following two conditions holds:

(1) i = 0, m_{1} ≥ 1 and the rightmost letter x_{k} satisfying |x_{k}| = 1 is equal to \overline{1};

(2) i ≥ 1, m_{i} = m_{i+1} = 1 and the rightmost letter that belongs to \{i, \overline{i}, i+1, \overline{i + 1}\} is equal to i or \overline{i + 1}.

For example, with w = \overline{4} 4 \overline{1} 3 2 5 \overline{5} 6 \overline{7} we have: Iligne w = \{0, 2, 6\}.

Remark. The expression “line of route” was used by Foulkes [11,12]. We have added the letter “g” making up “ligne of route,” thus bringing a slight touch of French. Notice that 0 may or may not belong to the inverse ligne of route. The ligne of route of a signed word w = x_{1}x_{2} … x_{m} is defined to be the set, denoted by Ligne w, of all the i’s such that either 1 ≤ i ≤ m − 1 and x_{i} > x_{i+1}, or i = 0 and x_{1} < 0. In particular, maj w = ∑_{0≤i≤m−1} i χ(i ∈ Ligne w). Finally, if w is a signed

permutation, then Iligne w = Ligne w^{−1}. For ordinary permutations, some authors speak of descent set and descent set of the inverse, instead of ligne of route and inverse ligne of route, respectively.

Theorem 1.2. The transformation Ψ constructed in section 2 preserves the inverse ligne of route:

(c) Iligne Ψ(w) = Iligne w for every signed word w.

Definition 1.2. Let w = x_{1}x_{2} … x_{m} be a signed word of length m. A letter x_{i} is said to be a lower record of w, if either i = m, or 1 ≤ i ≤ m − 1 and |x_{i}| < |x_{j}| for all j such that i + 1 ≤ j ≤ m. When reading the lower records of w from left to right, we get a signed subword x_{i_{1}}x_{i_{2}} … x_{i_{k}}, called the lower record subword, denoted by Lower w, which has the property that: min_{i} x_{i} = |x_{i_{1}}| < |x_{i_{2}}| < ⋯ < |x_{i_{k}}| = |x_{m}|. The notion of lower record is classical in the statistical literature. In combinatorics the expression “strict right-to-left minimum” is also used.

With our previous example w = \overline{4} 4 \overline{1} 3 2 5 \overline{5} 6 \overline{7} we get Lower w = \overline{1} 2 \overline{5} 6 \overline{7}. Our third goal is to prove the following result.

Theorem 1.3. The transformation Ψ constructed in section 2 preserves all the lower records:

(d) Lower Ψ(w) = Lower w for every signed word w.

For each signed permutation w = x_{1}x_{2} … x_{m} let

(1.11)  ifmaj w := 2 ∑_{1≤j≤m} i χ(j ∈ Iligne w) + ∑_{1≤j≤m} χ(x_{j} < 0);
(1.12)  ifdes w := 2 ∑_{1≤j≤m} χ(j ∈ Iligne w) + χ(x_{i} = −1 for some i).

It is immediate to verify that

finv w = finv w^{−1}, ifmaj w = fmaj w^{−1}, ifdes w = fdes w^{−1},

where w^{−1} denotes the inverse of the signed permutation w (written as a linear word w^{−1} = w^{−1}(1) … w^{−1}(m)).

Let i w := w^{−1}; then the chain

w  \underrightarrow{i}  w_{1}  \underrightarrow{Ψ}  w_{2}  \underrightarrow{i}  w_{3}
(\begin{matrix}fdes \\ ifmaj \end{matrix})  (\begin{matrix}ifdes \\ fmaj \end{matrix})  (\begin{matrix}ifdes \\ finv \end{matrix})  (\begin{matrix}fdes \\ finv \end{matrix})

shows that the four generating polynomials ∑ t^{fdes w}q^{ifmaj w}, ∑ t^{ifdes w}q^{fmaj w}, ∑ t^{ifdes w}q^{finv w} and ∑ t^{fdes w}q^{finv w} (w ∈ B_{m}) are identical. Their analytic expression will be derived in a forthcoming paper [9].

2. The construction of the transformation

For each signed word w = x_{1}x_{2} … x_{m} the first or leftmost (resp. last or rightmost) letter x_{1} (resp. x_{m}) is denoted by F (w) (resp. L(w)). Next, define s_{1} w := \overline{x}_{1}x_{2} … x_{m}. The transformation s_{1} changes the sign of the first letter. Together with s_{1} the main ingredients of our transformation are the bijections γ_{x} and δ_{x} defined for each integer x, as follows.

If L(w) ≤ x (resp. L(w) > x), then w admits the unique factorization

(v_{1}y_{1}, v_{2}y_{2}, …, v_{p}y_{p}),

called its x-right-to-left factorisation having the following properties:

(i) each y_{i} (1 ≤ i ≤ p) is a letter verifying y_{i} ≤ x (resp. y_{i} > x); (ii) each v_{i} (1 ≤ i ≤ p) is a factor which is either empty or has all its letters

greater than (resp. smaller than or equal to) x.

Then, γ_{x} is defined to be the bijection that maps w = v_{1}y_{1}v_{2}y_{2} … v_{p}y_{p} onto the signed word

(2.1)  γ_{x}(w) := y_{1}v_{1}y_{2}v_{2} … y_{p}v_{p}.

In a dual manner, if F (w) ≥ x (resp. F (w) < x) the signed word w admits the unique factorization

(z_{1}w_{1}, z_{2}w_{2}, …, z_{q}w_{q})

called its x-left-to-right factorisation having the following properties:

(i) each z_{i} (1 ≤ i ≤ q) is a letter verifying z_{i} ≥ x (resp. z_{i} < x); (ii) each w_{i} (1 ≤ i ≤ q) is a factor which is either empty or has all its letters less

than (resp. greater than or equal to) x. Then, δ_{x} is defined to be the bijection that sends w = z_{1}w_{1}z_{2}w_{2} … z_{q}w_{q} onto the signed word

(2.2)  δ_{x}(w) := w_{1}z_{1}w_{2}z_{2} … w_{q}z_{q}.

Next, if (v_{1}y_{1}, v_{2}y_{2}, …, y_{p}v_{p}) is the x-right-to-left factorization of w, we define

(2.3)  β_{x}(w) := \{ \begin{matrix}δ\overline{x} γ_{x}(w), & if either \overline{x} ≤ y_{1} ≤ x, or x < y_{1} < \overline{x}; \\ δ\overline{x} s_{1} γ_{x}(w), & otherwise. \end{matrix}

The fundamental transformation Ψ on signed words that is the main object of this paper is defined as follows: if w is a one-letter signed word, let Ψ(w) := w; if it has more than one letter, write the word as wx, where x is the last letter. By induction determine Ψ(w), then apply β_{x} to Ψ(w) and define Ψ(wx) to be the juxtaposition product:

(2.4)  Ψ(wx) := β_{x}(Ψ(w)) x.

The proof of Theorem 1.1 is given in section 3. It is useful to notice the following relation

(2.5) y_{1} ≤ x ⇔ L(w) ≤ x and the identity

(2.6) Ψ(wx) = Ψ(w)x, whenever x < − max{|x_{i}|} or x ≥ max{|x_{i}|}.

Example. Let w = 3 \overline{2} 1 \overline{3} \overline{4} 3. The factorizations used in the definitions of γ_{x} and δ\overline{x} are indicated by vertical bars. First, Ψ(3) = 3. Then

| 3 | ⟶^{γ\overline{2}} 3 ⟶^{s_{1}} | \overline{3} | ⟶^{δ_{2}} \overline{3}, so that Ψ(3 \overline{2}) = \overline{3} \overline{2};

| \overline{3} | \overline{2} | ⟶^{γ_{1}} \overline{3} \overline{2} ⟶^{s_{1}} | 3 \overline{2} | ⟶^{δ\overline{1}} \overline{2} 3, so that Ψ(3 \overline{2} 1) = \overline{2} 3 1;

| \overline{2} | 3 | 1 | ⟶^{γ\overline{3}} | \overline{2} 3 | 1 | ⟶^{δ_{3}} 3 \overline{2} 1, so that Ψ(3 \overline{2} 1 \overline{3}) = 3 \overline{2} 1 \overline{3};

and Ψ(3 \overline{2} 1 \overline{3} \overline{4}) = 3 \overline{2} 1 \overline{3} \overline{4}, because of (2.6);

| 3 | \overline{2} | 1 | \overline{3} | \overline{4} | ⟶^{γ_{3}} | 3 | \overline{2} | 1 | \overline{3} \overline{4} | ⟶^{δ\overline{3}} 3 \overline{2} 1 \overline{4} \overline{3}.

Thus, with w = 3 \overline{2} 1 \overline{3} \overline{4} 3 we get Ψ(w) = 3 \overline{2} 1 \overline{4} \overline{3} 3. We verify that fmaj w = finv Ψ(w) = 19, Iligne w = Iligne Ψ(w) = {1}, Lower w = Lower Ψ(w) = 1 3.

3. Proof of Theorem 1.1

Before proving the theorem we state a few properties involving the above statistics and transformations. Let |w| be the number of letters of the signed word w and |w|_{>x} be the number of its letters greater than x with analogous expressions involving ths subscripts “≥ x”, “< x” and “≤ x”. We have:

(3.1)  fmaj wx = fmaj w + χ(x < 0) + 2 |w| χ(L(w) > x);
(3.2)  finv wx = finv w + |w|_{>x} + |w|_{<\overline{x}} + χ(x < 0);
(3.3)  finv γ_{x}(w) = finv w + |w|_{≤x} − |w| χ(L(w) ≤ x);
(3.4)  finv δ_{x}(w) = finv w + |w|_{≥x} − |w| χ(F (w) ≥ x).

Next, let y_{1} denote the first letter of the signed word w′′. Then

(3.5)  finv s_{1} w′′ = finv w′′ + χ(y_{1} > 0) − χ(y_{1} < 0);
(3.6)  |s_{1} w′′|_{>x} = |w′′|_{>x} + χ(x > 0)(χ(y_{1} < \overline{x}) − χ(x < y_{1}))
+ χ(x < 0)(χ(y_{1} ≤ x) − χ(\overline{x} ≤ y_{1})).

Theorem 1.1 is now proved by induction on the word length. Assume that fmaj w = finv Ψ(w) for a given w. Our purpose is to show that

(3.7)  fmaj wx = finv Ψ(wx)

holds for all letters x. Let w′ = Ψ(w), so that by (2.4) the words w and w′ have the same rightmost letter. Denote the x-right-to-left factorization of w′ by (v_{1}y_{1}, …, v_{p}y_{p}). By (2.3) the signed word v := β_{x}(w′) is defined by the chain

(3.8)  w′ = v_{1}y_{1} … v_{p}y_{p} ⟶^{γ_{x}} w′′ = y_{1}v_{1} … y_{p}v_{p} = z_{1}w_{1} … z_{q}w_{q}

⟶^{δ\overline{x}} v = w_{1}z_{1} … w_{q}z_{q}

if either \overline{x} ≤ y_{1} ≤ x, or x < y_{1} < \overline{x}, and by the chain

(3.9)  w′ = v_{1}y_{1} … v_{p}y_{p} ⟶^{γ_{x}} w′′ = y_{1}v_{1} … y_{p}v_{p}

⟶^{s_{1}} w′′′ = \overline{y}_{1}v_{1} … y_{p}v_{p} = z_{1}w_{1} … z_{q}w_{q}

⟶^{δ\overline{x}} v = w_{1}z_{1} … w_{q}z_{q},

otherwise. Notice that (z_{1}w_{1}, …, z_{q}w_{q}) designates the \overline{x}-left-to-right factorization of w′′ in chain (3.8) and of w′′′ in chain (3.9).

(i) Suppose that one of the conditions \overline{x} ≤ y_{1} ≤ x, x < y_{1} < \overline{x} holds, so that (3.8) applies. We have

finv Ψ(wx) = finv vx = finv v + |v|_{>x} + |v|_{<\overline{x}} + χ(x < 0)  [by (3.2)]
finv v = finv δ\overline{x}(w′′) = finv w′′ + |w′′|_{≥\overline{x}} − |w′′| χ(F (w′′) ≥ \overline{x}) [by (3.4)]
finv w′′ = finv γ_{x}(w′) = finv w′ + |w′|_{≤x} − |w′| χ(L(w′) ≤ x)  [by (3.3)]
finv w′ = fmaj w  [by induction]
fmaj w = fmaj wx − χ(x < 0) − 2 |w| χ(L(w) > x).  [by (3.1)]

By induction,

(3.10)  L(w) = L(w′) and χ(L(w′) > x) = 1 − χ(L(w′) ≤ x).

Also F (w′′) = y_{1}. As w′, w′′, v are true rearrangements of each other, we have |v|_{>x} + |w′|_{≤x} = |w|, |v|_{<\overline{x}} + |w′′|_{≥\overline{x}} = |w|. Hence,

finv Ψ(wx) = fmaj wx + |w|[χ(L(w′) ≤ x) − χ(y_{1} ≥ \overline{x})].

By (2.5), if \overline{x} ≤ y_{1} ≤ x holds, then L(w′) ≤ x and the expression between brackets is null. If x < y_{1} < \overline{x} holds, then L(w′) > x and the same expression is also null. Thus (3.7) holds.

(ii) Suppose that none of the conditions \overline{x} ≤ y_{1} ≤ x, x < y_{1} < \overline{x} holds, so that (3.9) applies. We have

finv Ψ(wx) = finv vx = finv v + |v|_{>x} + |v|_{<\overline{x}} + χ(x < 0)  [by (3.2)]
finv v = finv δ\overline{x}(w′′′)=finv w′′′ + |w′′′|_{≥\overline{x}} − |w′′′| χ(F (w′′′) ≥ \overline{x}) [by (3.4)]
finv w′′′ = finv s_{1} w′′ = finv w′′ + χ(y_{1} > 0) − χ(y_{1} < 0)  [by (3.5)]
finv w′′ = finv γ_{x}(w′) = finv w′ + |w′|_{≤x} − |w′| χ(L(w′) ≤ x)  [by (3.3)]
finv w′ = fmaj w  [by induction]
fmaj w = fmaj wx − χ(x < 0) − 2 |w| χ(L(w) > x).  [by (3.1)]

Moreover, F (w′′′) = \overline{y}_{1}, so that χ(F (w′′′) ≥ \overline{x}) = χ(\overline{y}_{1} ≥ \overline{x}) = χ(y_{1} ≤ x) = χ(L(w′) ≤ x) = χ(L(w) ≤ x). As v and w′′′ are rearrangements of each other, we have |v|_{<\overline{x}} + |w′′′|_{≥\overline{x}} = |w|. Using (3.6) since |v|_{>x} = |w′′′|_{>x} = |s_{1}w′′|_{>x} we have:

finv Ψ(wx) = |w′′|_{>x} + χ(x > 0)(χ(y_{1} < \overline{x}) − χ(x < y_{1}))
+ χ(x < 0)(χ(y_{1} ≤ x) − χ(\overline{x} ≤ y_{1})) + χ(x < 0)
+ |w| − |w| χ(y_{1} ≤ x) + χ(y_{1} > 0) − χ(y_{1} < 0)
+ |w′|_{≤x} − |w′| χ(y_{1} ≤ x)
+ fmaj wx − χ(x < 0) − 2 |w| + 2|w| χ(y_{1} ≤ x)
= fmaj wx + χ(x > 0)(χ(y_{1} < \overline{x}) − χ(x < y_{1}))
+ χ(x < 0)(χ(y_{1} ≤ x) − χ(\overline{x} ≤ y_{1}))
+ χ(y_{1} > 0) − χ(y_{1} < 0)
= fmaj wx,

for, if none of the conditions \overline{x} ≤ y_{1} ≤ x, x < y_{1} < \overline{x} holds, then one of the following four ones holds: (a) y_{1} > x > 0; (b) \overline{y}_{1} > x > 0; (c) y_{1} ≤ x < 0; (d) \overline{y}_{1} ≤ x < 0; and in each case the sum of the factors in the above sum involving χ is zero.

The construction of Ψ is perfectly reversible. First, note that s_{1} is an involution and the maps γ_{x}, δ\overline{x} send each class B_{m} onto itself, so that their inverses are perfectly defined. They can also be described by means of left-to-right and right-to-left factorizations. Let us give the construction of the inverse Ψ^{−1} of Ψ. Of course, Ψ^{−1}(v) := v if v is a one-letter word. If vx is a signed word, whose last letter is x, determine v′ := δ−1 ; \overline{x}(v) and let z_{1} be its first letter. If one of the conditions \overline{x} ≤ z_{1} ≤ x or x < z_{1} < \overline{x} holds, the chain (3.8) is to be used in reverse order, so that Ψ^{−1}(vx) := (Ψ^{−1} γ_{x}^{−1} δ−1 ; \overline{x}(v))x. If none of those two conditions holds, then

Ψ^{−1}(vx) := (Ψ^{−1} γ_{x}^{−1} s_{1} δ−1 ; \overline{x}(v))x. □

4. Proofs of Theorems 1.2 and 1.3

Before proving Theorem 1.2 we note the following two properties.

Property 4.1. Let I_{x} = {i ∈ ℤ : i < −|x|} (resp. J_{x} = {i ∈ ℤ : −|x| < i < |x|}, resp. K_{x} = {i ∈ ℤ : |x| < i}) and w be a signed word. Then, the bijections γ_{x} and δ\overline{x} do not modify the mutual order of the letters of w that belong to I_{x} (resp. J_{x}, resp. K_{x}).

Proof. Let y ∈ I_{x} and z ∈ I_{x} (resp. y ∈ J_{x} and z ∈ J_{x}, resp. y ∈ K_{x} and z ∈ K_{x}) be two letters of w with y to the left of z. In the notations of (2.1) (resp. of (2.2)) both y, z are, either among the y_{i}’s (resp. the z_{i}’s), or letters of the v_{i}’s (resp. the w_{i}’s). Accordingly, y remains to the left of z when γ_{x} (resp. δ\overline{x}) is applied to w. □

Property 4.2. Let w = x_{1}x_{2} … x_{m} ∈ B_{m} be a signed word and i be a positive integer such that m_{i} = m_{i+1} = 1. Furthermore, let x be an integer such that x ∉ \{i, \overline{i}, i + 1, \overline{i + 1}\}. Then the following conditions are equivalent:

(a) i ∈ Iligne w; (b) i ∈ Iligne s_{1}w; (c) i ∈ Iligne γ_{x}w; (d) i ∈ Iligne δ\overline{x}w.

Proof. (a)⇔(b) holds by definition 1.1, because s_{1} has no action on the rightmost letter belonging to \{i, \overline{i}, i + 1, \overline{i + 1}\}. For the other equivalences we can say the following. If the two letters of w that belong to \{i, \overline{i}, i + 1, \overline{i + 1}\} are in I_{x} (resp. J_{x}, resp. K_{x}), Property 4.1 applies. Otherwise, if i ∈ Iligne w, then w is either of the form … \overline{i + 1} … i … or … i … \overline{i + 1} … and the order of those two letters is immaterial. □

Theorem 1.2 holds for each one-letter signed word. Let w = x_{1}x_{2} … x_{m} ∈ B_{m} be a signed word, x a letter and i a positive integer. Assume that Iligne w = Iligne Ψ(w).

If x = i, then i ∈ Iligne wx if and only if w contains no letter equal to ±i and exactly one letter equal to ±(i + 1). As β_{x}Ψ(w) is a rearrangement of w with possibly sign changes for some letters, the last statement is equivalent to saying that β_{x}Ψ(w) has no letter equal to ±i and exactly one letter equal to ±(i+1). This is also equivalent to saying that i ∈ Iligne β_{x}Ψ(w)x = Iligne Ψ(wx). In the same manner, we can show that

if x = \overline{i + 1}, then i ∈ Iligne wx if and only if i ∈ Iligne Ψ(wx);

if x = \overline{i}, then i ∉ Iligne wx and i ∉ Iligne Ψ(wx);

if x = i + 1, then i ∉ Iligne wx and i ∉ Iligne Ψ(wx).

Now, let i be such that none of the integers i, \overline{i + 1}, \overline{i}, i + 1 is equal to x. There is nothing to prove if m_{i} = m_{i+1} = 1 does not hold, as i does not belong to any of the sets Iligne w, Iligne β_{x}Ψ(w). Otherwise, the result follows from Property 4.2 because Ψ is a composition product of β_{x}, s_{1} and γ\overline{x}. Finally, the equivalence [0 ∈ Iligne β_{x}(w)x] ⇔ [0 ∈ Iligne wx] follows from Proposition 4.1 when |x|> 1 and the result is evident when |x|=1. □

The proof of Theorem 1.3 also follows from Property 4.1. By definition the lower records of wx, other than x, belong to J_{x}. As the bijections γ_{x} and δ\overline{x} do not modify the mutual order of the letters of w that belong to J_{x}, we have Lower wx = Lower β_{x}(w)x when the chain (3.8) is used. When (3.9) is applied, so that y_{1} ∉ J_{x}, we also have z_{1} = \overline{y}_{1} ∉ J_{x}. Thus, neither y_{1}, nor z_{1} can be lower records for each word ending with x. Again, Lower wx = Lower β_{x}(w)x. □

5. Concluding remarks

Since the works by MacMahon, much attention has been given to the study of statistics on the symmetric group or on classes of word rearrangements, in particular by the M.I.T. school ([25, 26, 27, 13, 6]). It was then natural to extend those studies to other classical Weyl groups, as was done by Reiner [20, 21, 22, 23, 24] for the signed permutation group. Today the work has been pursued by the Israeli and Roman schools [1, 2, 3, 4]. The contribution of Adin, Roichman [1] has been essential with their definition of the flag major index for signed permutations. In our forthcoming paper [9] we will derive new analytical expressions, in particular for several multivariable statistics involving “fmaj,” “finv” and the number of lower records.

References

1. Ron M. Adin and Yuval Roichman, The flag major index and group actions on polynomial rings, Europ. J. Combin. 22 (2001), 431–446.

2. Ron M. Adin, Francesco Brenti and Yuval Roichman, Descent Numbers and Major Indices for the Hyperoctahedral Group, Adv. in Appl. Math. 27 (2001), 210–224.

3. Riccardo Biagioli, Major and descent statistics for the even-signed permutation group, Adv. in Appl. Math. 31 (2003), 163–179.

4. Riccardo Biagioli and Fabrizio Caselli, Invariant algebras and major indices for classical Weyl groups, Proc. London Math. Soc. 88 (2004), 603–631.

5. Anders Björner and Michelle L. Wachs, Permutation Statistics and Linear Extensions of Posets, J. Combin. Theory, Ser. A 58 (1991), 85–114.

7. N. Bourbaki, Groupes et algèbres de Lie, Chapitres 4,5 et 6, Hermann, Paris, 1968.

6. Francesco Brenti, q-Eulerian Polynomials Arising from Coxeter Groups, Europ. J. Combinatorics 15 (1994), 417–441.

8. Dominique Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240.

9. Dominique Foata and Guo-Niu Han, Signed words and permutations, III; the MacMahon Verfahren, (preprint) (2005).

10. Dominique Foata and Marcel-Paul Schützenberger, Major Index and Inversion number of Permutations, Math. Nachr. 83 (1978), 143–159.

11. Herbert O. Foulkes, Tangent and secant numbers and representations of symmetric groups, Discrete Math. 15 (1976), 311–324.

12. Herbert O. Foulkes, Eulerian numbers, Newcomb’s problem and representations of symmetric groups, Discrete Math. 30 (1980), 3–49.

13. Ira Gessel, Generating functions and enumeration of sequences, Ph. D. thesis, Dept. Math., M.I.T., Cambridge, Mass., 111 p., 1977.

14. James E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Univ. Press, Cambridge, (Cambridge Studies in Adv. Math., 29), 1990.

15. Donald E. Knuth, The Art of Computer Programming, vol.3, Sorting and Searching, Addison-Wesley, Reading, 1973.

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

17. Percy Alexander MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), 314–321.

18. Percy Alexander MacMahon, Combinatory Analysis, vol. 1 and 2, Cambridge, Cambridge Univ. Press, 1915 (Reprinted by Chelsea, New York, 1995).

19. Percy Alexander MacMahon, “Collected Papers, vol. 1” [G.E. Andrews, ed.], Cambridge, Mass., The M.I.T. Press, 1978.

20. V. Reiner, Signed permutation statistics, Europ. J. Combinatorics 14 (1993), 553–567.

21. V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combinatorics 14 (1993), 569–579.

22. V. Reiner, Upper binomial posets and signed permutation statistics, Europ. J. Combinatorics 14 (1993), 581–588.

23. V. Reiner, Descents and one-dimensional characters for classical Weyl groups, Discrete Math. 140 (1995), 129–140.

24. V. Reiner, The distribution of descents and length in a Coxeter group,, Electronic J. Combinatorics 2, # R25 (1995).

25. Richard P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. vol. 119, Amer. Math. Soc., Providence, RI, 1972.

26. Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), 336–356.

27. John Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992), 307–320.

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

  E-mail address: foata@math.u-strasbg.fr

I.R.M.A. UMR 7501, Université Louis Pasteur et CNRS, 7 rue René-Descartes, F-67084 Strasbourg, France

  E-mail address: guoniu@math.u-strasbg.fr