GRAPHICAL MAJOR INDICES, II

D. FOATA† AND C. KRATTENTHALER†

Département de mathématique, Université Louis Pasteur, 7, rue René Descartes, F-67084 Strasbourg, France

           e-mail: foata@math.u-strasbg.fr

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

            e-mail: KRATT@Pap.Univie.Ac.At

ABSTRACT. Generalizations of the classical statistics “maj” and “inv” (the major index and the number of inversions) on words are introduced that depend on a graph on the underlying alphabet and the behaviour of each letter at the end of a word. The question of characterizing those graphs that lead to equidistributed “maj” and “inv” is posed and answered. This work extends a previous result of Foata and Zeilberger who considered the same problem under the assumption that all letters have the same behaviour at the end of a word.

0. Introduction

Let X be a finite alphabet and U be a relation on X. Without loss of generality we may assume X = {1, 2, …, r}. As U is a subset of X × X, the relation U can also be considered as a directed graph without multiple edges on X. This explains the ‘graphical’ in our title. Given such a relation U, in [5] extensions maj′_{U} and inv′_{U} of the classical major index and the number of inversions, respectively, were introduced for words w = x_{1}x_{2} … x_{m} with letters from X by

maj′_{U} w = ∑_{i=1}^{m−1} i · χ(x_{i+1}Ux_{i})  (0.1a)

inv′_{U} w = ∑_{1≤i<j≤m} χ(x_{j}Ux_{i}).  (0.1b)

1991 Mathematics Subject Classification: Primary 05A15; Secondary 05A10, 05A30. Key words and phrases: permutations, words, permutation statistics, major index,

inversions, q-exponential † Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400, the second author was also supported by the Austrian Science Foundation FWF, grant P10191-PHY

(Here, as usual, χ(A) = 1 if A is true, and χ(A) = 0 otherwise.) Note that maj′_{<} is the classical major index maj (introduced by MacMahon [9, 12] as “greater index”, see also [1, Def. 3.5]),

maj w = ∑_{i=1}^{m−1} i · χ(x_{i+1} < x_{i}),

and inv′_{<} is the usual number of inversions (often attributed to Netto [13, pp. 92f], though he cites earlier occurences; maybe the first occurence under this name is [18]; but probably MacMahon [11, 12] was the first to consider inversions of words instead of just permutations; see also [1, Def. 3.4]),

inv w = ∑_{1≤i<j≤m} χ(x_{j} < x_{i}).

Let c = (c(1), c(2), …, c(r)) be a sequence of r nonnegative integers, and let v be the (non-decreasing) word v = 1^{c(1)}2^{c(2)} … r^{c(r)}. We will denote by R(v) (or by R(c) if there is no ambiguity) the class of all rearrangements of the word v, i.e., the class of all words containing exactly c(i) occurences of the letter i for all i = 1, 2, …, r. Then MacMahon [11, 12] showed that maj and inv are equidistributed on each rearrangement class R(c) (see also [1, Cor. 3.8]). This motivates to pose the same question for the generalized major index and generalized number of inversions:

For which relations U on X are maj′_{U} and inv′_{U} equidistributed on each rearrangement class R(c)?

This question was answered in [5, Theorem 1] by giving a full characterization of all such relations U. More precisely, there it is shown that

Theorem A. The statistics maj′_{U} and inv′_{U} are equidistributed on each rearrangement class R(c) if and only if U is a “bipartitional” relation.

To make this understandable, we have to explain what a bipartitional relation is.

DEFINITION. A relation U on X is said to be bipartitional if there exists a partition (B_{1}, B_{2}, …, B_{k}) of the set X into blocks B_{l} together with a vector (β_{1}, β_{2}, …, β_{k}) of 0’s and 1’s such that x Uy if and only if either (1) x ∈ B_{l}, y ∈ B_{l′}, and l < l′, or (2) x, y ∈ B_{l}, and β_{l} = 1.

In words, there are two different types of blocks B_{l}, those with associated β_{l} = 0, let us call them U̸-blocks, and those with associated β_{l} = 1, let us call them U-blocks. Then x Uy if and only if x is in an “earlier” block than y, or if both x and y are in the same U-block. In particular, if x, y are elements of the same U̸-block then we have x U̸y and y U̸x.

For later use we record that Han [8] has given the following axiomatic characterization of bipartitional relations.

Proposition. A relation U on X is bipartitional if and only if (1) x Uy and y Uz imply x Uz, and (2) x Uy and z U̸y imply x Uz.

More general major indices and inversion numbers have been introduced when the underlying alphabet X is partitioned into two subsets. For signed permutations, for example, Reiner [14], [15], [16], while developing his theory of B_{n} P -partitions, was lead to define a major index by making a distinction between positive and negative integers. This idea was extended to words by Clarke and Foata [2], [3], [4] who considered small letters and large letters and could calculate the corresponding generating functions. Finally, Theorem 2 proved in [5] that involved another definition of the major index closely related to the definitions used by the previous three authors, suggested that a more general equidistribution result was to be discovered, if major index and inversion number for words with two kinds of letters could be adequately defined.

The purpose of this paper is to state and prove such a result. It is the content of Theorem B below. This theorem contains both Theorem A and Theorem 2 of [5] as special cases (see the Remark after Theorem B). It can even be considered as a merge of Theorem A and Theorem 2 of [5] into a single theorem.

Of course, the new major index maj_{U} and inversion number inv_{U} introduced in this paper will have to generalize the major index and inversion number of [5]. For their definitions we need to partition the underlying alphabet X into two disjoint subsets X = X_{n} ˙∪X_{d}. (The subscripts “n” and “d” stand for no descent and descent at the end of the word, as will be explained in section 1.) Now let U be a relation on X and given a word w = x_{1}x_{2} … x_{m} with letters from X define

maj_{U} w = ∑_{i=1}^{m−1} i · χ(x_{i+1}Ux_{i}) + m · χ(x_{m} ∈ X_{d});  (0.3a)
inv_{U} w = ∑_{1≤i<j≤m} χ(x_{j}Ux_{i}) + |{i : x_{i} ∈ X_{d}}|.  (0.3b)

Note that the difference between maj_{U} w and maj′_{U} w equals 0 if the last letter belongs to X_{n} and equals the length of the word w if the last letter of w belongs to X_{d}. The difference between inv_{U} w and inv′_{U} w is simply the number of letters of the word w that belong to X_{d}.

As done for the previous pairs of statistics we can ask the following question :

For which relations U on X are maj_{U} and inv_{U} equidistributed on each rearrangement class R(c)?

The main purpose of this paper is to answer this question by fully characterizing all such relations U.

Theorem B. Let X = X_{n} ˙∪X_{d} be a given partition. Then the statistics inv_{U} and maj_{U} are equidistributed on each rearrangement class R(c), if and only if U is bipartitional and “compatible with the partition X = X_{n} ˙∪X_{d}.”

To make this statement understandable, we have to explain what “compatible” means.

DEFINITION. A relation U is said to be compatible with the partition X = X_{n} ˙∪X_{d}, if for all x ∈ X_{n} and y ∈ X_{d} the relations x Uy and y U̸x hold.

Thus, a bipartitional relation U is compatible with the partition X = X_{n} ˙∪X_{d} if and only if U is bipartitional on each of the subalphabets X_{n}, X_{d}, and is such that for all x ∈ X_{n} and y ∈ X_{d} the relations x Uy and y U̸x hold. This can be made even more explicit. Let (B_{1}, B_{2}, …, B_{k}) be the partition of X and (β_{1}, β_{2}, …, β_{k}) the 0-1 vector associated with the bipartitional relation U. Then there is an integer h, 1 ≤ h ≤ k, such that X_{n} = B_{1} ˙∪B_{2} ˙∪ ⋯ ˙∪B_{h} and X_{d} = B_{h+1} ˙∪B_{h+2} ˙∪ ⋯ ˙∪B_{k}.

Recall [5] that a bipartitional relation U can also be visualized as follows: Again let U = (B_{1}, B_{2}, …, B_{k}), be the partition associated with U and let (β_{1}, β_{2}, …, β_{k}) be the associated 0-1 vector. Rearrange the elements of X in a row in such a way that the elements of B_{1} come first, in any order, then the elements of B_{2}, etc. Then U will consist of all the block products B_{l} × B_{l′} with l < l′, as well as the block product B_{l} × B_{l} whenever β_{l} = 1.

In Figure 1, for instance, the underlying relation consists of four blocks (B_{1}, B_{2}, B_{3}, B_{4}); the 0-1 vector is (1, 0, 0, 1).

U U U U U  U  U U B_{4} B_{3} B_{2} B_{1} B_{1} B_{2} B_{3} B_{4} Fig. 1

By the above considerations, this relation is compatible with each partition X = X_{n} ˙∪X_{d} provided X_{n} = B_{1} ∪ ⋯ ∪ B_{h} with 0 ≤ h ≤ 4.

REMARK. Notice that Theorem A is the particular case of Theorem B when X_{d} = ∅. Theorem 2 of [5] refers to bipartitional relations (B_{1}, …, B_{k}),

(β_{1}, …, β_{k}) such that X_{n} = ⋃_{l with β_{l}=0} B_{l} and X_{d} = ⋃_{l with β_{l}=1} B_{l}.

We shall give two different proofs of the ‘if’ part of Theorem B. The first proof is by means of generating function techniques and the so-called “MacMahon Verfahren” that essentially gives a general tool for building bijections between words and sets of non-increasing sequences that record the horizontal word statistics such as maj_{U} (see sections 2, 3). In an earlier version of the paper we have also described two P -partition proofs (not reproduced in the final version) inspired by Stanley’s work [19] and Reiner’s [14], [15], [16], [17]. However, we decided to give a direct proof instead, avoiding all the definitions that would be necessary to explain the P -partition proofs. The second proof is by means of an explicit bijection (section 4).

In section 5 we prove the ‘only if’ part of Theorem B. The proof relies on the ‘only if’ part of Theorem A. In addition, we start section 5 with a new proof for the ‘only if’ part of Theorem B that is much shorter than the original proof, thus also providing a new proof of the full Theorem A. (We remark that another proof of the ‘only if’ part of Theorem A, which is computer-assisted, was found by Han [7].) Our proof takes advantage of Han’s axiomatic characterization of bipartitional relations given in the Proposition above. All the notation that we are going to use throughout the paper is introduced in section 1.

Finally, in passing, we note that the exponential generating function for the number f_{r} of all bipartitional relations on X = {1, 2, …, r} that are compatible with some partition of X into two disjoint subsets equals

∑_{r=0}^{∞} f_{r} \frac{u^{r}}{r!} = \frac{1}{(3 − 2e^{u})^{2}} = 1 + 4u + 28\frac{u^{2}}{2!} + 268\frac{u^{3}}{3!}

+ 3244\frac{u^{4}}{4!} + 47404\frac{u^{5}}{5!} + 810988\frac{u^{6}}{6!} + · · · .

1. Notation and preliminaries

The q-notations that we use are

\begin{aligned}(a; q)_{k} & = ∏_{j=0}^{k−1}(1 − aq^{j}), with (a; q)_{0} = 1, \\ (a; q)_{∞} & = ∏_{j=0}^{∞}(1 − aq^{j}) \end{aligned}

for the finite and infinite q-factorials;

\left[{n \atop k}\right] = \frac{(q; q)_{n}}{(q; q)_{k} (q; q)_{n−k}}

for the q-binomial coefficient, and

\left[{n_{1} + n_{2} + ⋯ + n_{k} \atop n_{1}, n_{2}, …, n_{k}}\right] = \frac{(q; q)_{n_{1}+n_{2}+···+n_{k}}}{(q; q)_{n_{1}} (q; q)_{n_{2}} ⋯ (q; q)_{n_{k}}} ,

for the q-multinomial coefficient.

We shall use a number of special cases of the q-binomial theorem (cf. [1], Theorem 2.1 or [6], § 1.3),

∑_{n=0}^{∞} \frac{(a; q)_{n}}{(q; q)_{n}} u^{n} = \frac{(au; q)_{∞}}{(u; q)_{∞}} .  (1.1)

First, for a = 0,

∑_{n=0}^{∞} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}} ,  (1.2)

and for u → −u/a, a → ∞,

∑_{n=0}^{∞} \frac{q^{\binom{n}{2}}u^{n}}{(q; q)_{n}} = (−u; q)_{∞}.  (1.3)

Furthermore, with a = q^{s+1},

∑_{n=0}^{∞} \left[{s + n \atop n}\right]u^{n} = \frac{1}{(u; q)_{s+1}} ,  (1.4)

and with a = q^{−s}, u → −uq^{s},

∑_{n=0}^{∞} q^{\binom{n}{2}}\left[{s \atop n}\right]u^{n} = (−u; q)_{s}.  (1.5)

Finally, extraction of coefficients of u^{n} in (1.4) gives

\left[{s + n \atop n}\right] = ∑_{s≥a_{1}≥···≥a_{n}≥0} q^{a_{1}+···+a_{n}},  (1.6)

and in (1.5) gives

q^{\binom{n}{2}}\left[{s \atop n}\right] = ∑_{s−1≥a_{1}>···>a_{n}≥0} q^{a_{1}+···+a_{n}}.  (1.7)

Next we review our “U-notations” from the Introduction and add some new ones. Let w = x_{1}x_{2} … x_{m} be a word with letters from X. Classically we say that i, 1 ≤ i ≤ m − 1, is a descent of the word w, if x_{i+1} < x_{i}. The number of descents of w is usually denoted by des w. Furthermore, maj w is simply the sum of all descents of w.

Now let X be partitioned into two disjoint subsets, X = X_{n} ˙∪X_{d}, and let U be a relation on X. In analogy with the above terminology, we call i, 1 ≤ i ≤ m, a U-descent of w, if either x_{i+1}Ux_{i}, or if i = m and x_{i} ∈ X_{d}. (By the way, this makes the explanation for our notation X_{n} and X_{d} that was promised in the Introduction. X_{n} is the set of all letters that create “n”o descent at the end, X_{d} is the set of all letters that create a “d”escent at the end of a word.) Also, denote by des_{U} w the number of all U-descents of w (including a possible “descent at the end of w” when the last letter belongs to X_{d}). Then maj_{U} w is the sum of all U-descents of w.

Finally, we adopt the “bipartitional” notations from [5], section 2. Namely, given a partition (B_{1}, B_{2}, …, B_{k}) of X together with a 0-1 vector (β_{1}, β_{2}, …, β_{k}) we make the following conventions. Let c be the sequence c = (c(1), c(2), …, c(r)) of nonnegative integers. As before, let v = 1^{c(1)}2^{c(2)} … r^{c(r)} and denote by R(v) (or by R(c)) the class of rearrangements of the word v. If the block B_{l} consists of the integers i_{1}, i_{2}, …, i_{ℓ} and if u_{1}, u_{2}, …, u_{r} are r commuting variables, then we write

c ≥ 0 for c(1) ≥ 0, c(2) ≥ 0, …, c(r) ≥ 0;
|c| for the sum c(1) + c(2) + ⋯ + c(r);
u^{c} for the monomial u_{1}^{c(1)}u_{2}^{c(2)} ⋯ u_{r}^{c(r)};
c(B_{l}) for the sequence c(i_{1}), c(i_{2}), …, c(i_{ℓ});
c(B_{l}) ≥ 0 for c(i_{1}) ≥ 0, c(i_{2}) ≥ 0, …, c(i_{ℓ}) ≥ 0;
|c(B_{l})| for the sum c(i_{1}) + c(i_{2}) + ⋯ + c(i_{ℓ});
u(B_{l})^{c(B_{l})} for the monomial u_{i_{1}}^{c(i_{1})}u_{i_{2}}^{c(i_{2})} ⋯ u_{i_{ℓ}}^{c(i_{ℓ})};
∑ u(B_{l}) for the sum u_{i_{1}} + u_{i_{2}} + ⋯ + u_{i_{ℓ}}.

(1.8)

In particular, \binom{|c(B_{l})|}{c(B_{l})} will denote the multinomial coefficient

\binom{c(i_{1}) + c(i_{2}) + ⋯ + c(i_{ℓ})}{c(i_{1}), c(i_{2}), …, c(i_{ℓ})}.

2. The generating function by inv_{U}

Let U be a bipartitional relation on X supposed to be compatible with the partition X = X_{n} ˙∪X_{d}. Denote by (B_{1}, B_{2}, …, B_{k}) the partition of X and (β_{1}, β_{2}, …, β_{k}) the 0-1 vector associated with U. Furthermore, let h be the integer such that X_{n} = B_{1} ˙∪B_{2} ˙∪ ⋯ ˙∪B_{h} and X_{d} = B_{h+1} ˙∪B_{h+2} ˙∪ ⋯ ˙∪B_{k}. Finally, denote by

A^{inv^{U}} (q; c) := ∑_{w∈R(c)} q^{inv_{U} w}

the generating function for the class R(c) by inv_{U}. Under those assumptions we have the two identities:

A^{inv^{U}} (q; c) = \left[{|c| \atop |c(B_{1})|, |c(B_{2})|, …, |c(B_{k})|}\right] × ∏_{l=1}^{k} \binom{|c(B_{l})|}{c(B_{l})}

× ∏_{{1≤l≤h \atop β_{l}=1}} q^{\binom{|c(B_{l})|}{2}} × ∏_{{h+1≤l≤k \atop β_{l}=0}} q^{|c(B_{l})|} × ∏_{{h+1≤l≤k \atop β_{l}=1}} q^{|c(B_{l})|+\binom{|c(B_{l})|}{2}}, (2.1)

∑_{c≥0} \frac{A^{inv^{U}} (q; c)}{(q; q)_{c}}u^{c}

= \frac{∏_{{1≤l≤h \atop β_{l}=1}}(− ∑ u(B_{l}); q)_{∞} ∏_{{h+1≤l≤k \atop β_{l}=1}} (−q ∑ u(B_{l}); q)_{∞}}{∏_{{1≤l≤h \atop β_{l}=0}}(∑ u(B_{l}); q)_{∞} ∏_{{h+1≤l≤k \atop β_{l}=0}} (q ∑ u(B_{l}); q)_{∞}} . (2.2)

Call a pair (i, j) a U-inversion in the word w = x_{1}x_{2} … x_{m} if i < j and x_{j}Ux_{i}. Formula (2.1) follows from the well-known generating function in the ordinary “inv” case. The q-multinomial coefficient is the generating function for the class of words having exactly |c(B_{1})| letters equal to 1, …, |c(B_{k})| letters equal to k by “inv.” Such a word gives rise to exactly ∏_{l} \binom{|c(B_{l})|}{c(B_{l})} words in R(c). Now the letters belonging to each block B_{l}

such that 1 ≤ l ≤ h and β_{l} = 0 provide no further U-inversions and those belonging to each block B_{l} such that β_{l} = 1 bring \binom{|c(B_{l})|}{2} extra Uinversions when they are compared between themselves. Finally, the term |{i : x_{i} ∈ X_{d}}| that is to be added to the number of U-inversions can also be written as ∑_{h+1≤l≤k} |c(B_{l})|. This proves (2.1).

Finally, we go from (2.1) to (2.2) by a routine q-calculation, using the multinomial theorem.

3. The generating function by maj_{U}

We keep the same assumptions on U and the same notations as in the beginning of section 2. Let

A^{maj^{U}} (q; c) := ∑_{w∈R(c)} q^{maj_{U} w}

denote the generating function for the class R(c) by the statistics maj_{U}. Our purpose is to show that A^{maj^{U}} (q; c) is equal to the right-hand side of (2.1), so that inv_{U} and maj_{U} are equidistributed on each rearrangement class R(c). We first prove a stronger result, namely, we calculate the generating function for each class R(c) by the pair (des_{U}, maj_{U}) (remember the definition of the statistic des_{U} in section 1) and show by specialization that the generating polynomial by maj_{U} is equal to that right-hand side.

Proposition 3.1. Let

A^{des_{U} ,maj_{U}} (t, q; c) := ∑_{w∈R(c)} t^{des_{U} w}q^{maj_{U} w}

be the generating polynomial for R(c) by the pair (des_{U}, maj_{U}). Keeping the assumptions of the beginning of section 2 and the notations (1.8) we have the identities :

\frac{A^{des_{U} ,maj_{U}} (t, q; c)}{(t; q)_{|c|+1}}

= ∏_{l=1}^{k}\binom{|c(B_{l})|}{c(B_{l})}( ∑_{s≥0} t^{s} ∏_{{1≤l≤h \atop β_{l}=0}} \left[{|c(B_{l})| + s \atop |c(B_{l})|}\right] ∏_{{1≤l≤h \atop β_{l}=1}} q^{\binom{|c(B_{l})|}{2}}\left[{s + 1 \atop |c(B_{l})|}\right]

× ∏_{{h+1≤l≤k \atop β_{l}=0}} q^{|c(B_{l})|}\left[{|c(B_{l})| + s − 1 \atop |c(B_{l})|}\right] ∏_{{h+1≤l≤k \atop β_{l}=1}} q^{\binom{|c(B_{l})|+1}{2}}\left[{s \atop |c(B_{l})|}\right]) (3.2)

and

∑_{c≥0} \frac{A^{des_{U} ,maj_{U}} (t, q; c)}{(t; q)_{|c|+1}}u^{c}

= ∑_{s≥0} t^{s} \frac{∏_{{1≤l≤h \atop β_{l}=1}}(− ∑ u(B_{l}); q)_{s+1} ∏_{{h+1≤l≤k \atop β_{l}=1}} (−q ∑ u(B_{l}); q)_{s}}{∏_{{1≤l≤h \atop β_{l}=0}}(∑ u(B_{l}); q)_{s+1} ∏_{{h+1≤l≤k \atop β_{l}=0}} (q ∑ u(B_{l}); q)_{s}} . (3.3)

Suppose that (3.2) has been proved. Multiply both sides of that identity by (t; q)_{c+1} and let t tend to 1. It is straightforward to see that the righthand side tends to the right-hand side of (2.1), so that A^{maj^{U}} (q; c) = A^{inv^{U}} (q; c), i.e., maj_{U} and inv_{U} are equidistributed. Furthermore, it is again a routine q-calculation to derive (3.3) from (3.2). It then suffices to prove (3.2).

PROOF OF PROPOSITION 3.1. We could accomplish this by appealing to the P -partition theory developed by Stanley [19]; another possibility would be to make use of the B_{n} P -partition theory developed by Reiner [14]. Both theories can be considered as generalizations of the “MacMahon Verfahren” (see [9] or [1], chap. 3). Instead of going through the definitions of (B_{n}) P -partitions, we prefer to give a direct approach, modelled after the MacMahon Verfahren. As in [5] § 4, we proceed as follows:

Let w = x_{1}x_{2} … x_{m} be a word of the class R(c), so that m = |c|. Denote by w(B_{l}) the subword of w consisting of all the letters belonging to B_{l} (l = 1, …, k). Then replace each letter belonging to B_{l} by b_{l} = min B_{l} (with respect to the usual order). Call \overline{w} = \overline{x}_{1}\overline{x}_{2} … \overline{x}_{m} the resulting word. Clearly the mapping

w ↦ (\overline{w}, w(B_{1}), …, w(B_{l}))  (3.4)

is bijective. Moreover, des_{U} w = des_{U} \overline{w} and maj_{U} w = maj_{U} \overline{w}. Accordingly, the polynomial A^{des_{U} ,maj_{U}} (t, q; c) is divisible by ∏_{l} \binom{|c(B_{l})|}{c(B_{l})}.

In the sequel, for each l = 1, …, k let m_{l} = |c(B_{l})|. For each i = 1, 2, …, m let z_{i} denote the number of U-descents in the right factor \overline{x}_{i}\overline{x}_{i+1} … \overline{x}_{m} of \overline{w} (including one descent in m if x_{m} ∈ X_{d}). Clearly, z_{1} = des_{U} \overline{w} and z_{1} + ⋯ + z_{m} = maj_{U} \overline{w}.

Now let p = (p_{1}, …, p_{m}) be a sequence of m integers satisfying s′ ≥ p_{1} ≥ p_{2} ≥ ⋯ ≥ p_{m} ≥ 0, where s′ is a given integer. Form the nonincreasing word v = y_{1}y_{2} … y_{m} defined by y_{i} = p_{i} + z_{i} (1 ≤ i ≤ m) and consider the biword

( v ; \overline{w} ) = ( \begin{matrix}y_{1}y_{2} … y_{m} \\ \overline{x} & 1 & \overline{x} & 2 & … & \overline{x} & m \end{matrix} ).

Next rearrange the columns of the previous matrix in such a way that the mutual orders of the columns with the same bottom entries are preserved and the entire bottom row is of the form b_{1}^{m_{1}}b_{2}^{m_{2}} … b_{k}^{m_{k}}. We obtain the matrix

( \begin{matrix}a_{1,1} … a_{1,m_{1}} \\ b_{1} … b_{1} \end{matrix} \begin{matrix}… \\ … \end{matrix} \begin{matrix}a_{k,1} … a_{k,m_{k}} \\ b_{k} … b_{k} \end{matrix} ).

By construction each of the k words a_{1,1} … a_{1,m_{1}}, …, a_{k,1} … a_{k,m_{k}} is non-increasing.

Next, if i < i′, \overline{x}_{i} = \overline{x}_{i′} ∈ B_{l} and β_{l} = 1, there is necessarily a U-descent within \overline{x}_{i}\overline{x}_{i+1} … \overline{x}_{i′}. Hence z_{i} > z_{i′} and so y_{i} > y_{i′}. The word a_{l,1} … a_{l,m_{l}} corresponding to the block B_{l} will then be strictly decreasing.

On the other hand, z_{m} = 1 iff \overline{x}_{m} ∈ X_{d}. Let B_{l} be a block of X_{d}, so that h + 1 ≤ l and denote by \overline{x}_{i} the rightmost letter of \overline{w} that belongs to B_{l}. If i = m, then a_{l,m_{l}} = p_{m} + z_{m} ≥ 1; if i < m, then, either there is one letter of X_{n} in the factor \overline{x}_{i+1} … \overline{x}_{m} and necessarily one U-descent because U is supposed to be compatible with X_{n} ˙∪X_{d}, or all the letters in that factor are in X_{d} and in particular z_{m} = 1. In both cases, a_{l,m_{l}} ≥ 1. Also note that

a_{l,i} ≤ y_{1} = p_{1} + z_{1} ≤ s′ + des_{U} \overline{w}

for all l, i. Let then s = s′ + des_{U} \overline{w}. It follows that each of the words a_{l,1} … a_{l,m_{l}} satisfies

s ≥ a_{l,1} ≥ ⋯ ≥ a_{l,m_{l}} ≥ 0, if 1 ≤ l ≤ h and β_{l} = 0;
s ≥ a_{l,1} > ⋯ > a_{l,m_{l}} ≥ 0, if 1 ≤ l ≤ h and β_{l} = 1;
s ≥ a_{l,1} ≥ ⋯ ≥ a_{l,m_{l}} ≥ 1, if h + 1 ≤ l ≤ k and β_{l} = 0;
s ≥ a_{l,1} > ⋯ > a_{l,m_{l}} ≥ 1, if h + 1 ≤ l ≤ k and β_{l} = 1.

(3.5)

The mapping (s′, p, \overline{w}) ↦ (s, (a_{l,i})) is a bijection satisfying

\begin{matrix}s & = s′ + des_{U} \overline{w}; \\ ∑_{l,i} a_{l,i} = p_{1} + ⋯ + p_{m} & + z_{1} + ⋯ + z_{m} = ∑_{i} p_{i} + maj_{U} \overline{w}. \end{matrix}  (3.6)

Now it follows from (1.4) and (1.6) that

\frac{1}{(t; q)_{m+1}} = ∑_{s′≥0} t^{s′} ∑_{s′≥p_{1}≥···≥p_{m}≥0} q^{p_{1}+···+p_{m}},

so that by (3.4)

\frac{1}{∏_{l} \binom{m_{l}}{c(B_{l})}} \frac{A^{des_{U} ,maj_{U}} (t, q; c)}{(t; q)_{m+1}} = ∑_{s′≥0} t^{s′} ∑_{s′≥p_{1}≥···≥p_{m}≥0} q^{Σ p_{i}} ∑_{\overline{w}} t^{des^{U} \overline{w}}q^{maj^{U} \overline{w}}

= ∑_{(s′,p,\overline{w})} t^{s′+des_{U} \overline{w}}q^{Σ p_{i}+maj_{U} \overline{w}} = ∑_{(s,(a_{l,i}))} t^{s}q^{Σa_{l,i}} [by (3.6)]

= ∑_{s≥0} t^{s} ∏_{{1≤l≤h \atop β_{l}=0}} ∑_{s≥a_{l,1}≥···≥a_{l,m_{l}} ≥0} q^{a_{l,1}+···+a_{l,m_{l}}} ∏_{{1≤l≤h \atop β_{l}=1}} ∑_{s≥a_{l,1}>···>a_{l,m_{l}} ≥0} q^{a_{l,1}+···+a_{l,m_{l}}}

× ∏_{{h+1≤l≤k \atop β_{l}=0}} ∑_{s≥a_{l,1}≥···≥a_{l,m_{l}} ≥1} q^{a_{l,1}+···+a_{l,m_{l}}} ∏_{{h+1≤l≤k \atop β_{l}=1}} ∑_{s≥a_{l,1}>···>a_{l,m_{l}} ≥1} q^{a_{l,1}+···+a_{l,m_{l}}}

= ∑_{s≥0} t^{s} ∏_{{1≤l≤h \atop β_{l}=0}} \left[{m_{l} + s \atop m_{l}}\right] ∏_{{1≤l≤h \atop β_{l}=1}} q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right]

× ∏_{{h+1≤l≤k \atop β_{l}=0}} q^{m_{l}} \left[{m_{l} + s − 1 \atop m_{l}}\right] ∏_{{h+1≤l≤k \atop β_{l}=1}} q^{\binom{m_{l}+1}{2}}\left[{s \atop m_{l}}\right],

by (1.6) and (1.7). Hence (3.2) is established.

4. The bijective proof of the ‘if’ part of Theorem B

Again keep for the relation U on X the same assumptions as in the beginning of section 2. In this section we construct a bijection Ψ_{U} from each class R(c) onto itself, satisfying

maj_{U} w = inv_{U} Ψ_{U}(w)  (4.1)

for all words w ∈ R(c). The construction of the bijection Ψ_{U} parallels the bijective construction in [5], § 8.

As done in previous papers [20], [2], [3], [4], [5] we add a new letter ∗ to X. Then we extend U to the relation U^{∗} on X ∪ {∗} by adding the relations ∗ Uj, j ∈ X_{d}, to U. In other words, U^{∗} is the bipartitional relation on X ∪{∗} with blocks (B_{1}, …, B_{h}, {∗}, B_{h+1}, …, B_{k}) and vector (β_{1}, …, β_{h}, 0, β_{h+1}, …, β_{k}). Note that for any word w with letters from X we have

maj_{U} w = maj_{U^{∗}} w∗,  (4.2)
inv_{U} w = inv_{U^{∗}} w∗.  (4.3)

Now we make use of a map that was constructed in [5], § 5. There, given a bipartitional relation, B say, a bijection Φ_{B} from each rearrangement class R(c) onto itself was constructed that satisfies

maj′_{B} w = inv′_{B} Φ_{B}(w)  (4.4)

for any word w ∈ R(c). This map Φ_{B} had the additional property that it fixes the last letter. To be precise, we use the above construction with X replaced by X ∪ {∗} and with the bipartitional relation B = U^{∗}.

Let w be a word with letters from X. Form the concatenation w∗. Then we apply Φ_{U^{∗}} to w∗. Since Φ_{U^{∗}} fixes the last letter, we have Φ_{U^{∗}}(w∗) = w′∗ for some word w′ with letters from X. This given, we define Ψ_{U} by Ψ_{U}(w) := w′.

That Ψ_{U} is a bijection is immediate from the construction. Of course, we also have to check (4.1). Now, we have

maj_{U} w = maj′_{U^{∗}} w∗  [by (4.2)]
= inv′_{U^{∗}} Φ_{U^{∗}}(w∗)  [by (4.4)]
= inv′_{U^{∗}} w′∗  [by definition]
= inv_{U} w′  [by (4.3)]
= inv_{U} Ψ_{U}(w),  [by definition]

which is exactly (4.1).

5. The proof of the ‘only if’ part of Theorem B

We start this section by giving a new proof of the ‘only if’ part of Theorem A. This new proof is much shorter than the original one. We remark that this gives also a proof of the complete Theorem A, because the ‘if’ part of Theorem A is contained in the ‘if’ part of Theorem B. (To obtain the ‘if’ part of Theorem A, choose the trivial partition X = X_{n} ∪{} in the ‘if’ part of Theorem B.) In our new proof we take advantage of Han’s axiomatic characterization of bipartitional relations given in the Proposition in the Introduction.

PROOF OF THE ‘ONLY IF’ PART OF THEOREM A. Let U be a relation

on X such that maj′_{U} and inv′_{U} are equidistributed on each rearrangement class R(c). We want to show that U is bipartitional. In view of the Proposition in the Introduction, it suffices to show

(U1) x Uy and y Uz imply x Uz for all x, y, z ∈ X,

(U2) x Uy and z U̸y imply x Uz for all x, y, z ∈ X.

Proof of (U1). Let x, y, z be elements in X such that x Uy and y Uz. By way of contradiction, let us assume that x U̸z. We consider the rearrangement class R(xyz). By our assumptions, we have maj′_{U} zyx = 3. Since, also by assumption, maj′_{U} and inv′_{U} are equidistributed on R(xyz), there must be a word v ∈ R(xyz) with inv′_{U} v = 3. We observe that 3 is the maximum value that can be attained. So, since x and z occur in v, and since x U̸z, we must necessarily have z Ux, and x must occur before z in v. Thus there are the following possibilities for v:

v = xzy,  and in addition y Ux,
v = xyz,  and in addition y Ux and z Uy,
v = yxz,  and in addition z Uy.

There remain the following three cases for the relation U on {x, y, z},

Case I. x Uy Ux  Case II. x Uy Ux  Case III. x Uy U̸x
x U̸z Ux  x U̸z Ux  x U̸z Ux
y Uz U̸y  y Uz Uy  y Uz Uy

ad Case I. There holds maj′_{U} yzx = 0, but also inv′_{U} w ≥ 1 for any word w ∈ R(xyz), because of x Uy Ux. Thus maj′_{U} and inv′_{U} are not equidistributed on R(xyz), which is absurd.

ad Case II. There holds maj′_{U} yzx = 1, but also inv′_{U} w ≥ 2 for any word w ∈ R(xyz), because of x Uy Ux and y Uz Uy. Thus maj′_{U} and inv′_{U} are not equidistributed on R(xyz), which is absurd.

ad Case III. There holds maj′_{U} zxy = 0, but also inv′_{U} w ≥ 1 for any word w ∈ R(xyz), because of y Uz Uy. Thus maj′_{U} and inv′_{U} are not equidistributed on R(xyz), which is absurd.

Altogether this shows that we obtain a contradiction in any case. Hence we must have x Uz.

Proof of (U2). Let x, y, z be elements in X such that x Uy and z U̸y. By way of contradiction, let us assume that x U̸z. Now observe that (U1), which was already established, implies y U̸z. This is because in case y Uz we would have x Uy and y Uz, and thus x Uz, in contradiction with our assumption.

Now we consider again the rearrangement class R(xyz). By our assumptions, we have maj′_{U} yzx = 0. Since, also by assumption, maj′_{U} and inv′_{U} are equidistributed on R(xyz), there must be a word v ∈ R(xyz) with inv′_{U} v = 0. Since x and y occur in v, and since x Uy, we must necessarily have y U̸x (and x must occur before y in v).

There remain the following two cases for the relation U on {x, y, z},

Case I. x Uy U̸x  Case II. x Uy U̸x
x U̸z Ux  x U̸z U̸x
y U̸z U̸y  y U̸z U̸y

ad Case I. There holds maj′_{U} yxz = 3, but also inv′_{U} w ≤ 2 for any word w ∈ R(xyz), because of y U̸z U̸y. Thus maj′_{U} and inv′_{U} are not equidistributed on R(xyz), which is absurd.

ad Case II. There holds maj′_{U} zyx = 2, but also inv′_{U} w ≤ 1 for any word w ∈ R(xyz), because of x U̸z U̸x and y U̸z U̸y. Thus maj′_{U} and inv′_{U} are not equidistributed on R(xyz), which is absurd.

Altogether this shows that we obtain a contradiction in any case. Hence we must have x Uz.

REMARK. The argument above shows that it is even sufficient to require equidistribution of maj′_{U} and inv′_{U} only on rearrangement classes containing only three letters. Han [7] has given another proof of the ‘only if’ part of Theorem A based on his axiomatic characterization of bipartitional relations (the Proposition in the Introduction). In fact, our proof is directly inspired by his. Instead of letting the computer verify all possible relations U on the letters {x, y, z} (there are 2^{9} = 512 such relations!) and sorting out the “right” ones, as he did, we have just provided an argument to reduce the number of cases to consider.

PROOF OF THE ‘ONLY IF’ PART OF THEOREM B. Let U be a relation

on X = X_{n} ˙∪X_{d} such that maj_{U} and inv_{U} are equidistributed on each rearrangement class R(c). First choose c such that only letters from X_{n} are chosen. For these rearrangement classes, maj_{U} and inv_{U} reduce to maj′_{U} and inv′_{U}, respectively. Hence, by the ‘only if’ part of Theorem A, we infer that U is bipartitional on X_{n}. Secondly, choose c such that only letters from X_{d} are chosen. For these rearrangement classes, maj_{U} and inv_{U} reduce to maj′_{U} +|c| and inv′_{U} +|c|, respectively. Again, by the ‘only if’ part of Theorem A, we infer that U is bipartitional on X_{d}.

Thus it remains to see how letters from X_{n} are related to letters from X_{d}. Take a letter x ∈ X_{n} and a letter y ∈ X_{d}. We want to show that we must have x Uy and y U̸x. We establish this by excluding the other three cases.

Case I: x U̸y U̸x. Then maj_{U} xy = 2, maj_{U} yx = 0, but inv_{U} xy = inv_{U} yx = 1. Thus maj_{U} and inv_{U} are not equidistributed on R(xy), which is absurd.

Case II: x U̸y Ux. Then maj_{U} xy = 3, maj_{U} yx = 0, but inv_{U} xy = 2, inv_{U} yx = 1. Thus maj_{U} and inv_{U} are not equidistributed on R(xy), which is absurd.

Case III: x Uy Ux. Then maj_{U} xy = 3, maj_{U} yx = 1, but inv_{U} xy = inv_{U} yx = 2. Thus maj_{U} and inv_{U} are not equidistributed on R(xy), which is absurd.

This shows that the only legal possibility is x Uy U̸x. Hence, U is a bipartitional relation on X that is compatible with the partition X = X_{n} ˙∪X_{d}.

References

1. G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison–Wesley, Reading, 1976.

2. R. J. Clarke and D. Foata, Eulerian calculus I: Univariable statistics, Europ. J. Combin. 15 (1994), 345–362.

3. R. J. Clarke and D. Foata, Eulerian calculus II: An extension of Han’s fundamental transformation, Europ. J. Combin. 16 (1995), 345–362.

4. R. J. Clarke and D. Foata, Eulerian calculus III: The ubiquitous Cauchy formula, Europ. J. Combin. (1995) (to appear).

5. D. Foata and D. Zeilberger, Graphical major indices, J. of Computational and Applied Math. (1995) (to appear).

6. G. Gasper and M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, 1990.

7. G.-N. Han, Une démonstration “vérificative” d’un résultat de Foata–Zeilberger sur les relations bipartitionnaires, J. of Computational and Applied Math. (1995) (to appear).

8. G.-N. Han, Ordres bipartitionnaires et statistiques sur les mots, Electronic J. Combin. (1995) (to appear).

9. P. A. 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), 282–322.

10. P. A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

11. P. A. MacMahon, Two applications of general theorems in combinatory analysis, Proc. London Math. Soc., Ser. II 15 (1916), 314–321.

12. P. A. MacMahon, Collected Papers: Combinatorics, Vol. I, MIT Press, Cambridge, Massachusetts, 1978.

13. E. Netto, Lehrbuch der Combinatorik, Teubner–Verlag, Leipzig, Berlin, 1901; 2nd ed., 1927.

14. V. Reiner, Signed posets, J. Combin. Theory Ser. A 62 (1993), 324–360.

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

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

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

18. H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (K. F. Hindenburg, ed.), Leipzig, 1800, pp. 263–305.

19. R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119, American Mathematical Society, Providence, R. I., 1972.

20. E. Steingrìmsson, Permutation statistics of indexed permutations Europ. J. Combin. 15 (1994),

DÉPARTEMENT DE MATHÉMATIQUE, UNIVERSITÉ LOUIS PASTEUR, 7, RUE RENÉ DESCARTES, F-67084 STRASBOURG, FRANCE.

INSTITUT FÜR MATHEMATIK DER UNIVERSITÄT WIEN, STRUDLHOFGASSE 4, A-1090 WIEN, AUSTRIA.