Séminaire Lotharingien de Combinatoire 53 (2005), Article B53a

A NOTE ON SOME MAHONIAN STATISTICS

BOB CLARKE^{∗}

Abstract. We construct a class of mahonian statistics on words, related to the classical statistics maj and inv. These statistics are constructed via Foata’s second fundamental transformation.

1. Introduction

Consider the alphabet X = [r] = {1, 2, …, r}.

A word w = w_{1}w_{2} ⋯ w_{n} on X is a finite string of not-necessarily distinct elements of X. The set of all words on X is written X^{∗}. The rearrangement class R(w) of a word w is the set of all words that can be obtained by permuting the letters of w. If the letters of w are distinct, then w is a permutation and R(w) is the set of elements of the symmetric group S_{n}.

The statistics inv and maj are defined on X^{∗} by

inv w = #{ (i, j) | 1 ≤ i < j ≤ n, w_{i} > w_{j} },
maj w = ∑{ i | 1 ≤ i < n, w_{i} > w_{i+1} }.

It is a result of MacMahon [5] that inv and maj are equidistributed on any rearrangement class R(c). Foata [2, 3] gave a bijective proof using his second fundamental transformation. A statistic equidistributed with inv (or maj) is called mahonian.

Let a, b ∈ X. The cyclic interval ]]a, b]] has been defined by Han [4] as

]]a, b]] = \begin{cases}(a, b], & if a ≤ b; \\ X \ (b, a], & otherwise. \end{cases}

In particular, ]]a, a]] = ∅.

Han has redefined the statistics maj and inv in terms of cyclic intervals as follows. If 1 ≤ j ≤ n, define the j-factor of w as Fact_{j} w = w_{1}w_{2} … w_{j−1}. Write w_{n+1} = ∞. Then

∗School of Mathematical Sciences, University of Adelaide, Australia 5005, robert.clarke at adelaide.edu.au.

inv w = ∑_{j=2}^{n} |Fact_{j} w ∩ ]]w_{j}, ∞]]| ,

maj w = ∑_{j=2}^{n} |Fact_{j} w ∩ ]]w_{j}, w_{j+1}]]| .

We define the partial statistics s_{j} and t_{j} by

s_{j} = s_{j}(w) = |Fact_{j} w ∩ ]]w_{j}, w_{j+1}]]| ,
t_{j} = t_{j}(w) = |Fact_{j} w ∩ ]]w_{j}, ∞]]| ,

2 ≤ j ≤ n. Then s_{n} = t_{n} and

inv w = t_{2}(w) + ⋯ + t_{n}(w),
maj w = s_{2}(w) + ⋯ + s_{n}(w).

Our main result is the following.

Theorem 1. Let e = (e_{2}, …, e_{n−1}) = ℤ_{2}^{n−2}. For each j, 1 < j ≤ n, let

u_{j} = \begin{cases}s_{j}, & if e_{j} = 0; \\ t_{j}, & if e_{j} = 1. \end{cases}

Put u_{n} = s_{n} = t_{n}. Then the statistic

inmaj_{e} w = u_{2} + ⋯ + u_{n}

is mahonian.

Note that maj w = inmaj_{(0,...,0)} w, inv w = inmaj_{(1,...,1)} w. This theorem defines 2^{n−2} mahonian statistics, all but two of which seem to be new (although implicit in Foata’s second fundamental transformation).

Although this result suggests that for each j, the partial statistics s_{j} and t_{j} are equidistributed, this is not in general true — on the rearrangement class R(1 1 2 3), the statistics s_{3} and t_{3} are differently distributed.

2. Foata’s second fundamental transformation

Let w = w_{1}w_{2} … w_{n} be a word on X and let a ∈ X. If w_{n} ≤ a, the a-factorization of w is w = v_{1}b_{1} … v_{p}b_{p}, where each b_{i} is a letter less than or equal to a, and each v_{i} is a word (possibly empty), all of whose letters are greater than a. Similarly, if w_{n} > a, the a-factorization of w is w = v_{1}b_{1} … v_{p}b_{p}, where each b_{i} is a letter greater than a, and each v_{i} is a word (possibly empty), all of whose letters are less than or equal to a. In each case we define

γ_{a}(w) = b_{1}v_{1} … b_{p}v_{p}.

With the above notations, let a = w_{n} and let w′ = w_{1} … w_{n−1}. The second fundamental transformation Φ is defined recursively by Φ(w) = w, if w has length 1, and

Φ(w) = γ_{a}(Φ(w′))a,

if w has length n > 1. Then

inv Φ(w) = maj w,

see [3].

Let us define the mapping Φ_{1} as the juxtaposition product

Φ_{1}(w) = γ_{a}(w′)a.

The following result follows easily from the proof of the result in [3].

Lemma 2. With the above notation,

inv Φ_{1}(w) = \begin{cases}inv w′ & if w_{n−1} ≤ w_{n}, \\ inv w′ + n − 1 & if w_{n−1} > w_{n} \end{cases}
= inv w′ + maj w − maj w′.
□

Since Φ_{1} is a bijection, this shows that the statistic

inv w′ + maj w − maj w′

is mahonian. Now it is routine to verify that, in the notation of the previous section,

inv w′ + maj w − maj w′ = t_{2} + ⋯ + t_{n−2} + s_{n−1} + s_{n}
= inmaj_{(1,...,1,0)} w.

Hence inmaj_{(1,...,1,0)} is mahonian.

More generally, let 1 ≤ j ≤ n. Write w = u_{1}u_{2}, where u_{1} is a word of length j. Then we can show in the same way as before that there is a bijection Φ′ satisfying

inv Φ′(w) = inv u_{1} + maj w − maj u_{1} = t_{2} + ⋯ + t_{j−1} + s_{j} + ⋯ + s_{n}
= inmaj_{(1,...,1,0,...,0)}

for all words w on n letters. Hence the statistic inmaj_{(1,...,1,0,...,0)} is mahonian (where the subscript contains j − 2 ones and n − j zeros).

Proof of Theorem 1. Let e = (e_{2}, …, e_{n−1}) ∈ ℤ^{n−1} as before. We will show that inmaj_{e} is mahonian, by showing that there is a bijection Φ_{e} satisfying inv Φ_{e}(w) = inmaj_{e} w. We have shown this above for e of the form (1, …, 1, 0, …, 0).

We use induction on the number of zeros in the vector e. The result is true if e contains no zeros, as in this case inmaj_{e} = inv.

Suppose the result is true for all vectors e′ containing fewer zeros than e. Let k be the smallest index such that e_{k} = 0 and let j be the largest index such that e_{i} = 0 for k ≤ i ≤ j. If j = n − 1 then the result follows, so suppose that j < n − 1. Then e_{j+1} = 1. Thus

inmaj_{e} w = t_{2} + ⋯ + t_{k−1} + s_{k} + ⋯ + s_{j} + t_{j+1} + u_{j+2} + ⋯ + u_{n},

where u_{i} = t_{i} or s_{i}.

Let f be the vector of length j − 1 whose components are e_{2}, …, e_{j}, i.e., f = (1, …, 1, 0, …, 0) (with k − 2 ones). Then there is a bijection Φ_{f} satisfying

inv Φ_{f}v = inmaj_{f} v

for all words v of length j + 1. Define a bijection θ on words of length n by

θ(v_{1}v_{2}) = Φ_{f}(v_{1})v_{2},

where v_{1} and v_{2} are words of lengths j + 1 and n − j − 1 respectively. Let g = (g_{i}) be the vector defined by

g_{i} = \begin{cases}1, & if 2 ≤ i ≤ j; \\ e_{i}, & if i > j. \end{cases}

Then

inmaj_{g} θ(v_{1}v_{2}) = (t_{2} + ⋯ + t_{j+1})Φ_{f}(v_{1}) + (u_{j+2} + ⋯ + u_{n})Φ_{f}(v_{1})v_{2}
= (u_{2} + ⋯ + u_{j+1})v_{1} + (u_{j+2} + ⋯ + u_{n})v_{1}v_{2}
= inmaj_{e} v_{1}v_{2}.

Now, as g contains fewer zeros than e, there is a bijection Φ_{g} such that

inv Φ_{g}(w) = inmaj_{g} w

for all words w on n letters. Hence, putting Φ_{e} = Φ_{g} ∘ θ,

inv Φ_{e}(w) = inv Φ_{g}(θ(w)) = inmaj_{g} θ(w) = inmaj_{e} w.
□

Finally, we refer the reader to [1] for a rather different application of Foata’s second fundamental transformation.

References

[1] A. Björner and M. Wachs, Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A 58 (1991), 85–114.

[2] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240.

[3] D. Foata, Rearrangements of Words, in M. Lothaire, Combinatorics on Words, Cambridge University Press, Cambridge, 1997.

[4] Guo-Niu Han, Une transformation fondamentale sur les réarrangements de mots, Advances in Math. 105 (1994), 26–41.

[5] (Major) P.A. MacMahon, Combinatory Analysis, vol. 1, Cambridge, Cambridge University Press, 1915. (Reprinted by Chelsea, New York, 1955.)