GRAPHICAL MAJOR INDICES

Dominique FOATA^{1} and Doron ZEILBERGER^{2}

Abstract: A generalization of the classical statistics “maj” and “inv” (the major index and number of inversions) on words is introduced, parameterized by arbitrary graphs on the underlying alphabet. The question of characterizing those graphs that lead to equi-distributed “inv” and “maj” is posed and answered.

Résumé: On introduit une généralisation des statistiques classiques que sont “maj” et “inv” (l’indice majeur et le nombre d’inversions) sur les mots, qui est paramétrisée par des graphes arbitraires sur l’alphabet sousjacent. La question de caractériser ces graphes conduisant à des statistiques “inv” et “maj” qui soient équidistribuées est posée et résolue.

0. Introduction

Every mathematician knows what the the number of inversions of a permutation is, as it features in the definition of the determinant. The number of inversions of a permutation π = π(1)π(2) … π(n) of length n,

inv π = ∑_{1≤i≤j≤n} χ(π(i) > π(j)),

(using the classical notation χ(A) = 1 or 0, depending on whether the statement A is true of false) is a measure of how ‘scrambled’ it is compared to the identity permutation. Netto proved (and it is nowadays easy to see, e.g., [Kn73, p. 15]) that the generating function for “the number of inversions”

∑_{π∈S_{n}} q^{inv(π)},

equals the q-analog of n!, i.e., [n]! := 1(1+q)(1+q+q^{2}) … (1+q+…+q^{n−1}), that, can be also written as (q)_{n}/(1 − q)^{n}, where, as usual in q−theory, (q)_{n} = (1 − q)(1 − q^{2}) … (1 − q^{n}).

1 Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. (foata@math.u-strasbg.fr). Supported in part by the E.E.C. program on Algebraic Combinatorics. 2 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. (zeilberg@math.temple.edu). Supported in part by the NSF.

The number of inversions is an example of a permutation statistic, by which is meant a numerical attribute that permutations possess (just like height, weight, or number of children for humans). The utility of the generating function according to a given statistic “stat,”

F_{stat}(q) := ∑_{π∈S_{n}} q^{stat(π)},

is that it contains in it all the ‘statistical’ information regarding “stat.” Also its derivatives evaluated at q = 1 enable us to, successively, find the average, standard deviation, and higher moments of its distribution. Furthermore, when the generating function is ‘nice’ it hints at (combinatorial, algebraic and sometimes analytic) structures.

MacMahon [Mac15, p. 135] was the first to introduce another such statistic, that he called ‘the greater index’, but that is nowadays called the ‘major index’ and denoted by “maj.” In fact, he defined that statistic not only for permutations but for arbitrary words with possible repetitions of letters. He did also the same for “inv.” If X is a totally ordered alphabet, and if w = x_{1}x_{2} … x_{m} is a word with letters in X, those two statistics are defined by

\begin{aligned}maj w & = ∑_{i=1}^{m−1} i χ(x_{i} > x_{i+1}), \\ inv w & = ∑_{1≤i<j≤m} χ(x_{i} > x_{j}). \end{aligned}

To restate MacMahon’s result we will take the alphabet X as the linear set [ r] = {1, 2, …, r} (r ≥ 1). Let c = (c(1), c(2), …, c(r)) be a sequence of r non-negative 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) occurrences of the letter i for all i = 1, …, r. Then MacMahon [Mac13] (see also [Mac78]) proved that for each integer k there are as many words w ∈ R(c) such that maj w = k, as there are words w′ ∈ R(c) such that inv w′ = k. In other words, the statistics “maj” and “inv” are equidistributed on each rearrangement class.

It is well known, and easy to see, that the number of words in R(c) is the multinomial coefficient:

\binom{c(1) + c(2) + ⋯ + c(r)}{c(1), c(2), …, c(r)} = \frac{(c(1) + c(2) + ⋯ + c(r))!}{c(1)! c(2)! … c(r)!}.

MacMahon’s proof [Mac13, Mac78] (see also [Kn73, p. 17], [An76, chap. 3]) of the forementioned result was to show that the generating functions for “inv” and “maj”, over the class R(v), i.e., ∑_{w}q^{inv w} and ∑_{w}q^{maj w} (with

w runnning over the class R(c)), were both given by the q-analog of the multinomial coefficient:

\left[{c(1) + c(2) + ⋯ + c(r) \atop c(1), c(2), …, c(r)}\right] = \frac{(q)_{c(1)+c(2)+···+c(r)}}{(q)_{c(1)}(q)_{c(2)} … (q)_{c(r)}} .

The natural question of finding a bijection that sends each permutation to another one in such a way that the major index of the image equals the number of inversions of the original, has been answered by the first author [Fo68], and since ‘canonized’ in the book ([Kn73], ex. 5.1.1.19).

In this paper we introduce a natural generalization of both “inv” and “maj,” parameterized by a general directed graph. A directed graph on X is any subset U of the Cartesian product X × X = {(x, y) | 1 ≤ x ≤ r, 1 ≤ y ≤ r}. Of course there are altogether 2^{r^{2}} directed graphs.

For each such directed graph U let’s associate the following statistics defined on each word w = x_{1}x_{2} … x_{m} by

(0.1)  \begin{aligned}maj′_{U} w & = ∑_{i=1}^{m−1} i χ((x_{i}, x_{i+1}) ∈ U), \\ inv′_{U} w & = ∑_{1≤i<j≤m} χ((x_{i}, x_{i+1}) ∈ U). \end{aligned}

Further in the paper other statistics “maj_{U}” and “inv_{U}” (without any primes) will be introduced.

The purpose of this paper is to characterize the directed graphs U that posses the ‘Mahonian property’ of “inv” and “maj” having the same generating function. We first need the following definition.

Definition. An ordered bipartition of X is a sequence (B_{1}, B_{2}, …, B_{k}) of non-empty disjoint subsets of X, of union X, together with a sequence (β_{1}, β_{2}, …, β_{k}) of elements equal to 0 or 1. If β_{l} = 1 (resp. 0), we say that the subset B_{l} is underlined (resp. non-underlined). For the sake of convenience, we also say that the subscript l or each element of B_{l} is underlined (resp. non-underlined).

A relation U on X × X is said to be bipartitional, if there exists an ordered bipartition ((B_{1}, B_{2}, …, B_{k}), (β_{1}, β_{2}, …, β_{k})) such that (x, y) ∈ U iff either x ∈ B_{l}, y ∈ B_{l′} and l < l′, i.e., if the block containing x is to the left of the block containing y, or x and y belong to the same block B_{l} and B_{l} is underlined.

As proved by Han [Han95a, théorème 5], a bipartitional relation U can also be characterized by the following two relations

\begin{aligned}(x, y) ∈ U, (y, z) ∈ U & ⇒ (x, z) ∈ U ; \\ (x, y) ∉ U, (z, y) ∈ U & ⇒ (z, x) ∈ U. \end{aligned}

Some particular bipartitional relations are worth being noticed.

1) U = {(x, y) | x > y} that corresponds to the ordered bipartition ({r}, …, {2}, {1}) ; in this case inv′_{U} = inv and maj′_{U} = maj;

2) U = {(x, y) | x ≥ y} that is associated with the ordered bipartition (\underline{\{r\}}, …, \underline{\{2\}}, \underline{\{1\}}), where all the blocks are underlined; the inversions and descents involved in the statistics “inv′_{U}” and “maj′_{U}” also include all the pairs (x, x);

3) U = ∅ which is associated with the one-block ordered bipartition ({1, 2, …, r}); the statistics “inv′_{U}” and “maj′_{U}” are identically zero;

4) U = X×X which is associated with the one-underlined-block ordered bipartition (\underline{\{1, 2, …, r\}}); in this case inv′_{U} w = maj′_{U} w = m(m − 1)/2 for each word w of length m;

5) U which is associated with an ordered bipartition all the blocks of which are singletons; such relations have been considered by Clarke and Foata [ClFo94, ClFo95a, ClFo95b] who also introduced the statistic “maj_{k}” which is immediately related with the statistic “maj_{U}” further defined.

A bipartitional relation U = ((B_{1}, B_{2}, …, B_{k}), (β_{1}, β_{2}, …, β_{k})) can also be visualized as follows: 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 B_{l} is underlined.

In Figure 1, for instance, the underlying ordered bipartition consists of four blocks (B_{1}, B_{2}, B_{3}, B_{4}) with B_{1}, B_{4} underlined.

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

Our first result is the following.

Theorem 1. The statistics “inv′_{U}” and “maj′_{U}” are equidistributed on each rearrangement class, if and only if the relation U is bipartitional.

We first prove the ‘easy’ part, which as usual is the ‘if’ part. Three proofs will be given. The first manipulative, the second combinatorial à la MacMahon, the third bijective, as people say to-day. All this is derived in sections 3, 4 and 5, respectively. Section 6 contains the proof of the ‘only if’ part.

In a recent Note Han [Han95b] has been able to derive a computer-aided proof of the ‘only if’ part. By examining finitely many relations by means of an appropriate computer program he showed that the equidistribution only holds for bipartitional relations.

Now if U is a bipartitional relation on X, two other statistics “inv_{U}” and “maj_{U}” may be defined, that also reduce to “inv” and “maj” when U = ({r}, …, {2}, {1}). Let |w|_{−} denote the number of underlined letters in the word w = x_{1}x_{2} … x_{m}. Then define

(0.2)

maj_{U} w = maj′_{U} w + m χ(x_{m} is underlined),
inv_{U} w = inv′_{U} w + |w|_{−} .

We say that a bipartitional relation U is compatible, if all its underlined blocks are on the left of its non-underlined ones, or, with the above notations, if the sequence (β_{1}, β_{2}, …, β_{k}) is of the form (1, 1, …, 1, 0, 0, …, 0).

We next prove the theorem.

Theorem 2. Let U be a bipartitional relation on X. Then “maj_{U}” and “inv_{U}” are equidistributed on each rearrangement class, if and only if U is compatible.

As we shall see, the notion of compatibility is crucial. It relates with an analogous notion introduced in Clarke and Foata (op. cit.) for dealing with the number of excedances and the Denert statistic. If U is non-compatible, “maj_{U}” and “inv_{U}” are not even equidistributed on a class of two elements. For example, let X = {1, 2} and let U be the (non-compatible) bipartitional relation associated with the ordered bipartition (\{1\}, \underline{\{2\}}). Then inv_{U} 12 = 2, inv_{U} 21 = 1, while maj_{U} 12 = 3, maj_{U} 21 = 0. Actually, that simple example is the core of the proof of the ‘only if’ part of Theorem 2 (see section 7).

Let U be an ordered bipartition. Parallel to the definition of “maj′_{U}” and “maj_{U}” we can also introduce two kinds of U-descents. Let w = x_{1}x_{2} … x_{m} be a word; we say that there is a U-descent of the first kind at i in w, if 1 ≤ i ≤ m − 1 and (x, x_{i+1}) ∈ U, and a U-descent of the second kind at i in w, if 1 ≤ i ≤ m − 1 and (x, x_{i+1}) ∈ U or i = m and x_{m} is underlined. Denote by des′_{U} w (resp. des_{U} w) the number of those U-descents of the first kind (resp. of the second kind). In section 4 we derive an expression for the generating function for each rearrangement class R(c) by the pair of statistics (des′_{U}, maj′_{U}).

Section 7 contains the calculation of the generating function of R(c) by the pair (des_{U}, maj_{U}) and also the proof of Theorem 2. A bijective proof of the latter Theorem appears in section 8.

1. Enumerating bipartitional relations

For each r ≥ 1 let b′_{r} (resp. b_{r}) be the number of bipartitional relations (resp. compatible bipartitional relations) on a set of cardinality r. Also let b′_{0} = b_{0} = 1. The exponential generating functions for both sequences (b′_{r}) and (b_{r}) are easily derived and, using some computer algebra, their first values calculated. Denote by S(r, k) (1 ≤ r ≤ k) the sequence of the Stirling numbers of the second kind (see, e.g., [Co70, vol. 2, p. 40]).

Proposition 1.1. We have the formulas

(1.1)  b′_{r} = ∑_{k=1}^{r} S(r, k)k! 2^{k};

(1.2)  b_{r} = ∑_{k=1}^{r} S(r, k) (k + 1)! ;

(1.3) ∑_{r≥0} b′_{r} \frac{u^{r}}{r!} = \frac{1}{3 − 2e^{u}}

= 1 + 2u + 10\frac{u^{2}}{2!} + 74\frac{u^{3}}{3!} + 730\frac{u^{4}}{4!} + 9002\frac{u^{5}}{5!} + 133210\frac{u^{6}}{6!} + ⋯

(1.4) ∑_{r≥0} b_{r} \frac{u_{r}}{r!} = \frac{1}{(2 − e^{u})^{2}}

= 1 + 2u + 8\frac{u^{2}}{2!} + 66\frac{u^{3}}{3!} + 308\frac{u^{4}}{4!} + 2612\frac{u^{5}}{5!} + 25988\frac{u^{6}}{6!} + ⋯

Proof. Formulas (1.1) and (1.2) follow immediately from the combinatorial definition of the Stirling numbers. Accordingly, we can easily derive (1.3) and (1.4) from the “vertical” exponential generating function for the Stirling numbers. A more direct and conceptual proof consists of making use of the partitional complex approach [Fo74] (or invoking the theory of species dear to our Québécois friends [Be94]). This goes as follows.

Suppose that for each r ≥ 1 there are two blocks of size r, say, the underlined \underline{[ r]} and the non-underlined block [ r]. The exponential generating function for those two kinds of blocks is

G = 2\frac{u^{1}}{1!} + 2\frac{u^{2}}{2!} + ⋯ + 2\frac{u^{n}}{n!} + ⋯ = 2e^{u} − 2.

Hence the expansion of (1 − G)^{−1} will be the generating function for the ordered sequences of blocks, some of them being underlined and the others being non-underlined, i.e., for the ordered bipartitions. Furthermore, (1 − G)^{−1} = 1/(3 − 2e^{u}).

For the compatible bipartitional partitions there are again two kinds of blocks, but this time the underlined blocks must lie to the left of the nonunderlined ones. The exponential generating functions for the underlined blocks and for the non-underlined blocks are the same:

H = \frac{u^{1}}{1!} + \frac{u^{2}}{2!} + ⋯ + \frac{u^{n}}{n!} + ⋯ = (e^{u} − 1).

Hence the expansion of (1−H)^{−1}(1−H)^{−1} will be the generating function for the ordered sequences of blocks, the leftmost ones being underlined, the rightmost ones being non-underlined, so that

∑_{r≥0} b_{r} \frac{u^{r}}{r!} = (\frac{1}{(1 − (e^{u} − 1))})^{2} = \frac{1}{(2 − e^{u})^{2}} .

The sequences (b′_{r}) and (b_{r}) do not appear (yet?) in the Sloane integral sequence basis [Sl94]. However our young colleague Jiang Zeng drew our attention to the paper by Knuth [Kn92] who himself pointed out that the generating function (2 − e^{u})^{−1} already appeared in Cayley (Collected Math. Papers, vol. 4, p. 112-115) for enumerating a special class of trees. According to Knuth the coefficients of the Taylor expansion of (2 − e^{u})^{−1} count the preferential arrangements of n objects.

2. Notations and first analytic results

We make use of the usual notations: (a; q)_{n} and (a; q)_{∞} for the qascending factorials:

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

In particular, (q)_{n} = (q; q)_{n} and (q)_{∞} = (q; q)_{∞}.

Recall the q-binomial theorem (see [An76 p. 15] or [GaRa90, § 1.3]) that states

(2.1)  ∑_{n≥0} \frac{(a; q)_{n}}{(q; q)_{n}} u^{n} = \frac{(au; q)_{∞}}{(u; q)_{∞}} ,

together with the two q-exponential identities

(2.2)  e_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}};

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

The q-binomial theorem provides the five expansions (see [An76, p. 15])

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

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

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

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

(2.8) \frac{1}{(u; q)_{s+1}} = ∑_{n≥0} u^{n} ∑_{n≥a_{1}≥···≥a_{s}≥0} q^{a_{1}+···+a_{s}} ;

where the a_{i}’s are non-negative integers.

The ordered bipartition ((B_{1}, B_{2}, …, B_{k}), (β_{1}, β_{2}, …, β_{k})) will be kept fixed throughout this section. Let U be the bipartitional relation on X ×X associated with it. Next consider a sequence c = (c(1), c(2), …, c(r)) of non-negative 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 all rearrangements of the word v. If the block B_{l} consists of the integers i_{1}, i_{2}, …, i_{h} written in increasing order (with respect to the usual linear order of X = [ r]) and if u_{1}, u_{2}, …, u_{r} are r commuting variables, it will be convenient to write

(2.9) c(B_{l}) for the sequence c(i_{1}), c(i_{2}), …, c(i_{h}) ;
m_{l} = ∑ c(B_{l}) for the sum c(i_{1}) + c(i_{2}) + ⋯ + c(i_{h}) ;
|c| for the sum c(1) + ⋯ + c(r) also equal to m_{1} + ⋯ + m_{k};
c ± 1_{i} for (c(1), …, c(i − 1), c(i) ± 1, c(i + 1), …, c(r)) ;
u(B_{l})^{c(B_{l})} for the monomial u_{i_{1}}^{c(i_{1})}u_{i_{2}}^{c(i_{2})} … u_{i_{h}}^{c(i_{h})} ;
∑ u(B_{l}) for the sum u_{i_{1}} + u_{i_{2}} + ⋯ + u_{i_{h}}.
u^{c} for the monomial u_{1}^{c_{1}}u_{2}^{c_{2}} … u_{r}^{c_{r}}.

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

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

Finally we adopt the following notations for the generating polynomials for the class R(c) by the various statistics “inv′_{U},” “maj′_{U},” “inv_{U}” and “maj_{U}”:

inv{′ \atop U}A(q; c) = ∑_{w} q^{inv′_{U} w}; ^{maj{′ \atop U}}A(q; c) = ∑_{w} q^{maj′_{U} w};
inv_{U}A(q; c) = ∑_{w} q^{inv_{U} w}; ^{maj^{U}}A(q; c) = ∑_{w} q^{maj_{U} w};

where w runs over all R(c)). As “des” is the companion of “maj”, we will also denote by

maj{′ \atop U}A(t, q; c) = ∑_{w} t^{des′_{U} w}q^{maj′_{U} w}; ^{maj^{U}}A(t, q; c) = ∑_{w} t^{des_{U} w}q^{maj_{U} w};

the generating polynomials for the class R(c) by the pairs (des′_{U}, maj′_{U}) and (des_{U}, maj_{U}).

Proposition 2.1. With the above notations (2.9) the following formulas hold

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

(2.11)

∑_{c} \frac{^{inv{′ \atop U}}A(q; c)}{(q)_{|c|}}u^{c} = ∏_{l;β_{l}=0} e_{q}(∑ u(B_{l})) × ∏_{l;β_{l}=1} E_{q}(∑ u(B_{l}))

= \frac{∏_{l;β_{l}=1}(− ∑ u(B_{l}); q)_{∞}}{∏_{l;β_{l}=0}(∑ u(B_{l}); q)_{∞}} .

In the second formula c runs over all sequences (c(1), …, c(r)) with c(1) ≥ 0, …, c(r) ≥ 0.

Proof. Formula (2.10) 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 m_{1} letters equal to 1, …, m_{k} letters equal to k by “inv.” Such a word gives rise to exactly ∏_{l} \binom{m_{l}}{c(B_{l})}

words in R(c). Finally, the letters belonging to each non-underlined block provide no further U-inversions, while the letters in an underlined block B_{l} (β_{l} = 1) bring \binom{m_{l}}{2} extra U-inversions when they are compared between themselves.

To derive (2.11) we make use of the traditional q-calculus. First rewrite (2.10) as

(2.12)  \frac{^{inv{′ \atop U}}A(q; c)}{(q)_{|c|}} = ∏_{l=1}^{k} \frac{q^{β_{l}\binom{m_{l}}{2}}}{(q)_{m_{l}}} \binom{m_{l}}{c(B_{l})}.

Then the left-hand side of (2.10) is equal to

∑_{c(B_{1})}⋯∑_{c(B_{k})} \frac{^{inv{′ \atop U}}A(q; c)}{(q)_{|c|}}u(B_{1})^{c(B_{1})} … u(B_{k})^{c(B_{k})}

= ∏_{l=1}^{k} ∑_{c(B_{l})} \frac{q^{β_{l}\binom{m_{l}}{2}}}{(q)_{m_{l}}} \binom{m_{l}}{c(B_{l})}u(B_{l})^{c(B_{l})}

= ∏_{l=1}^{k} ∑_{d(l)≥0} \frac{q^{β_{l}\binom{d(l)}{2}}}{(q)_{d(l)}} ∑_{B_{l};m_{l}=d(l)} \binom{m_{l}}{c(B_{l})}u(B_{l})^{c(B_{l})}

= ∏_{l=1}^{k} ∑_{d(l)≥0} \frac{q^{β_{l}\binom{d(l)}{2}}}{(q)_{d(l)}} (∑ u(B_{l}))^{d(l)},

which is the right-hand side of (2.11) by using (2.2) and (2.3).

3. An ‘Essentially Verification’ Manipulative Proof of the ‘If’ Part of Theorem 1

The generating function according to “maj′_{U}” does not seem to be directly derivable from the classical MacMahon formula. Later, we will show that the combinatorial proofs easily carry over, but here we will show a manipulative proof. We will prove the stronger result that the subsets of words with a prescribed last letter have the Mahonian property.

Keep the same notations as in Proposition 2.1. In particular, let |c| = c(1)+⋯+c(r) = m_{1}+⋯+m_{l} be the length of the words in the class R(c). Also define, for each letter i ∈ X = [ r].

inv{′ \atop U}A(q; c; i) := ∑_{w} q^{inv′_{U} w}  (w ∈ R(c), w ends with i) ;
maj{′ \atop U}A(q; c; i) := ∑_{w} q^{maj′_{U} w}  (w ∈ R(c), w ends with i).

It is easy to derive a formula for ^{inv{′ \atop U}}A(q; c; i), in terms of ^{inv{′ \atop U}}A(q; c). Let i belong to the block B_{l} (1 ≤ l ≤ k). Then,

(3.1)  ^{inv{′ \atop U}}A(q; c; i) = ^{inv{′ \atop U}}A(q; c − 1_{i})q^{m_{1}+···+m_{l−1}},

if B_{l} is not underlined, and

(3.2)  ^{inv{′ \atop U}}A(q; c; i) = ^{inv{′ \atop U}}A(q; c − 1_{i})q^{m_{1}+···+m_{l−1}+m_{l}−1},

if B_{l} is underlined.

By considering what letter can be second-to-last, we get the following recurrence:

(3.3) ^{maj{′ \atop U}}A(q; c; i) = q^{|c|−1} ∑_{j∈B_{1}∪···∪B_{l−1}}^{maj{′ \atop U}}A(q; c − 1_{i}; j)

+ ∑_{j∈B_{l}∪···∪B_{k}}^{maj{′ \atop U}}A(q; c − 1_{i}; j)

when B_{l} is not underlined, and the recurrence

(3.4) ^{maj{′ \atop U}}A(q; c; i) = q^{|c|−1} ∑_{j∈B_{1}∪···∪B_{l}}^{maj{′ \atop U}}A(q; c − 1_{i}; j)

+ ∑_{j∈B_{l+1}∪···∪B_{k}}^{maj{′ \atop U}}A(q; c − 1_{i}; j)

when B_{l} is underlined.

It is a completely routine matter, that we leave to the readers (or rather to their computers) to verify that the expressions on the right sides of (3.1) and (3.2) (using (2.10)) also satisfy the same recurrence. It follows by induction that for all c and for all 1 ≤ i ≤ r, we have

(3.5)  ^{inv{′ \atop U}}A(q; c; i) = ^{maj{′ \atop U}}A(q; c; i).

By summing over i we get ^{inv{′ \atop U}}A(q; c) = ^{maj{′ \atop U}}A(q; c), so that for bipartitional graphs U the statistics “inv_{U}” and “maj_{U}” are equidistributed.

4. The MacMahon Verfahren

In this section we make use again of the same notations as in section 2. We calculate the factorial generating function for the polynomials

maj{′ \atop U}A(t, q; c) = ∑_{w} t^{des′_{U} w}q^{maj′_{U} w} (w ∈ R(c))

(where des′_{U} w is the number of U-descents of the first kind in w defined in the introduction) by first deriving (4.1)

\frac{^{maj{′ \atop U}}A(t, q; c)}{(t; q)_{|c|+1}} = ∏_{l=1}^{k} \binom{m_{l}}{c(B_{l})} × ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} \left[{m_{l} + s \atop m_{l}}\right] × ∏_{l;β_{l}=1} q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right].

By multiplying (4.1) by (1−t) and making t = 1, and then multiplying by (q)_{|c|} the right-hand side is transformed into the right-hand side of (2.11), so that ^{maj{′ \atop U}}A(q; c) = ^{inv{′ \atop U}}A(q; c) for each class c and each bipartitional relation U.

The factorial generating function for the polynomials ^{maj{′ \atop U}}A(t, q; c) reads

(4.2)  ∑_{c} \frac{^{maj{′ \atop U}}A(t, q; c)}{(t; q)_{|c|+1}}u^{c} = ∑_{s≥0} t^{s} \frac{∏_{l;β_{l}=1}(− ∑ u(B_{l}); q)_{s+1}}{∏_{l;β_{l}=0}(∑ u(B_{l}); q)_{s+1}} ,

and can be derived from (4.1) as follows which is the finite version of (2.11).

As done in Proposition 2.1 we can obtain (4.2) from (4.1) by a routine calculation as follows:

∑_{c} \frac{^{maj{′ \atop U}}A(t, q; c)}{(t; q)_{|c|+1}}u^{c} = ∑_{c(B_{1}),...,c(B_{k})} \frac{^{maj{′ \atop U}}A(t, q; c)}{(t; q)_{|c|+1}} ∏_{l=1}^{k} u(B_{l})^{c(B_{l})}

= ∑_{c(B_{1}),...,c(B_{k})} ∏_{l=1}^{k} u(B_{l})^{c(B_{l})}\binom{m_{l}}{c(B_{l})}

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

= ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} ∑_{c(B_{l})} u(B_{l})^{c(B_{l})}\binom{m_{l}}{c(B_{l})}\left[{m_{l} + s \atop m_{l}}\right]

× ∏_{l;β_{l}=1} ∑_{c(B_{l})} u(B_{l})^{c(B_{l})}\binom{m_{l}}{c(B_{l})}q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right]

= ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} ∑_{m_{l}} \left[{m_{l} + s \atop m_{l}}\right] ∑_{Σc(B_{l})=m_{l}} u(B_{l})^{c(B_{l})}\binom{m_{l}}{c(B_{l})}

× ∏_{l;β_{l}=1} ∑_{m_{l}} q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right] ∑_{Σc(B_{l})=m_{l}} u(B_{l})^{c(B_{l})}\binom{m_{l}}{c(B_{l})}

= ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} ∑_{m_{l}} \left[{m_{l} + s \atop m_{l}}\right](∑ u(B_{l}))^{m_{l}}

× ∏_{l;β_{l}=1} ∑_{m_{l}} q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right](∑ u(B_{l}))^{m_{l}}

= ∑_{s≥0} t^{s} \frac{∏_{l;β_{l}=1}(− ∑ u(B_{l}); q)_{s+1}}{∏_{l;β_{l}=0}(∑ u(B_{l}); q)_{s+1}} ,

by using the identities (2.4) and (2.5).

Now we can prove (4.1) using the so-called “MacMahon Verfahren.” As already noted in [Fo95, ClFo95a], the method introduced by MacMahon [Mac13] to derive the generating function for “maj” is to be updated to include a second statistic, but the principle remains the same.

Let ((B_{1}, …, B_{k})(β_{1}, …, β_{k})) be the ordered bipartition corresponding to the bipartitional relation U and 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}) be 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. Clear the mapping

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

is bijective. Moreover, des′_{U} w = des′_{U} \overline{w} and maj′_{U} w = maj′_{U} \overline{w}. Accordingly, the polynomial ^{maj{′ \atop U}}A(t, q; c) is divisible by ∏_{l} \binom{m_{l}}{c(B_{l})}.

For each i = 1, 2, …, m let z_{i} denote the number of U-descents (of the first kind) in the right factor \overline{x}_{i}\overline{x}_{i+1} … \overline{x}_{m} of \overline{w}. 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. Furthermore, if \overline{x}_{i} = \overline{x}_{i′} and \overline{x}_{i} ∈ B_{l} with l underlined, there is necessarily a U-descent within \overline{x}_{i}\overline{x}_{i+1} … \overline{x}_{i′}. Hence z_{i} > z_{i′} and and y_{i} > y_{i′}. The corresponding word a_{l,1} … a_{l,m_{l}} will then be strictly decreasing. 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

(4.4) s ≥ a_{l,1} ≥ ⋯ ≥ a_{l,m_{l}} ≥ 0, if l is not underlined; s ≥ a_{l,1} > ⋯ > a_{l,m_{l}} ≥ 0, if l is underlined.

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

(4.5)  \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}

Now rewrite (2.8) as

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

so that by (4.3) we have

\frac{1}{∏_{l} \binom{m_{l}}{c(B_{l})}} \frac{^{maj{′ \atop U}}A(t, q; c)}{(t; q)_{m+1}} = ∑_{s≥0} t^{s} ∑_{s≥p_{1}≥···≥p_{m}≥0} q^{Σ p_{i}} ∑_{\overline{w}} t^{des{′ \atop U} \overline{w}}q^{maj{′ \atop 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 (4.5)]

= ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} ∑_{s≥a_{l,1}≥···≥a_{l,m_{l}} ≥0} q^{a_{l,1}+···+a_{l,m_{l}}}

× ∏_{l;β_{l}=1} ∑_{s≥a_{l,1}>···>a_{l,m_{l}} ≥0} q^{a_{l,1}+···+a_{l,m_{l}}}

= ∑_{s≥0} t^{s} ∏_{l;β_{l}=0} \left[{m_{l} + s \atop m_{l}}\right] ∏_{l;β_{l}=1} q^{\binom{m_{l}}{2}}\left[{s + 1 \atop m_{l}}\right] [by (2.6) and (2.7).]

Hence (4.1) is established.

As (4.2) implies (2.11) and as the latter identity holds in the U-number-of-inversion version, we have another proof of the ‘if’ part of Theorem 1.

5. The bijective proof of the ‘if part’ of Theorem 1

Let U be a bipartitional relation. In this section we construct a bijection Φ_{U} of each class R(c) onto itself satisfying

(5.1)  maj′_{U} w = inv′_{U} Φ_{U}(w).

One of the main ingredients in the construction of Φ_{U} is the second fundamental transformation Φ (see, e.g., [Lo83, chap. 10]) that satisfies

(5.2)  maj w = inv Φ(w)

on each rearrangement class. The bijection Φ_{U} is the conjugate of Φ in the sense that we have

(5.3)  Φ_{U} = δ^{−1} ∘ Φ ∘ δ,

for a certain bijection δ.

Let us first recall the construction of Φ [Lo83, chap. 10]: let w be a word in the alphabet X and x ∈ X. Two cases are to be considered

(i) the last letter of w is greater than x; (ii) the last letter of w is at most equal to x.

In case (i) let (w_{1}x_{1}, w_{2}x_{2}, …, w_{h}x_{h}) be the factorization of w having the following properties: x_{1}, x_{2}, …, x_{h} are letters of X greater than x and w_{1}, w_{2}, …, w_{h} are words all letters of which are less than or equal to x.

In case (ii) x_{1}, x_{2}, …, x_{h} are letters of X at most equal to x, while w_{1}, w_{2}, …, w_{h} are words all letters of which are greater than x.

Call x-factorization the above factorization. In both cases we have

w = w_{1}x_{1}w_{2}x_{2} … w_{h}x_{h};

then define

γ_{x} w = x_{1}w_{1}x_{2}w_{2} … x_{h}w_{h}.

The construction of Φ goes as follows. If w is of length 0 or 1, let Φ(w) = w. For a word wx with x ∈ X and w of positive length, form Φ(w) (already defined by induction), apply γ_{x} to Φ(w) and add x at the end of the resulting words, i.e., define

Φ(wx) = (γ_{x} Φ(w))x.

Property (5.2) was proved in [Fo68] (see also [Lo83, chap. 10]). We shall make use of two further properties.

Proposition 5.1.

(i) Both w and Φ(w) end with the same letter.

(ii) Let y and y′ be two adjacent letters (with respect to the usual order) in the alphabet X and suppose that both occur exactly once in w. Then, if y occurs to the left of y′ in w, the same holds for Φ(w).

Property (i) is true by the very definition of Φ. Property (ii) requires a simple verification that will be left out.

Let ((B_{1}, …, B_{k})(β_{1}, …, β_{k})) be the ordered bipartition corresponding to the bipartitional relation U. We keep the notations given in § 2. If w is a word in R(c), let m_{l} = ∑ B_{l} be the number of letters in w belonging to B_{l} and let w(B_{l}) be the subword of w consisting of all the letters belonging to B_{l} (l = 1, …, k).

The conjugation δ is defined as follows.

(i) For every l = 1, …, k replace each letter belonging to B_{l} by b_{l} = min B_{l} (with respect to the usual order). Call \overline{w} the resulting word.

(ii) If l is non-underlined, read \overline{w} from left to right and replace the successive occurrences of b_{l} by (b_{l}, 1), (b_{l}, 2), …, (b_{l}, m_{l}); do this for each non-underlined l.

(iii) Do the operation described in (ii) for each underlined l, but this time read \overline{w} from right to left.

The word derived after all those operations will be denoted by w_{U}. It is actually a rearrangement of the word (b_{1}, 1) … (b_{1}, m_{1}) … (b_{k}, 1) … (b_{k}, m_{k}) (all letters distinct.) Furthermore, w_{U} contains the subword (b_{l}, 1) … (b_{l}, m_{l}) (resp. (b_{l}, m_{l}) … (b_{l}, 1)) if l is non-underlined (resp. underlined). To be able to define “maj” for w_{U} we need a linear order on those ordered pairs. We shall take:

(5.3)  (b_{l}, j) > (b_{l′}, j′) iff l < l′ or l = l′ and j > j′.

The conjugation δ is then defined by

(5.4)  δ : w ↦ (w_{U}, w(B_{1}), w(B_{2}), …, w(B_{r})).

The inverse map δ^{−1} simply consists of replacing each subword

(b_{l}, 1)(b_{l}, 2) … (b_{l}, m_{l}) (resp. (b_{l}, m_{l}) … (b_{l}, 2)(b_{l}, 1))

within w_{U} by the subword w(B_{l}).

Lemma 5.2. With “maj” defined by means of the total order (5.3) the following identity holds:

(5.5)  maj′_{U} w = maj w_{U}.

Proof. Let w = x_{1}x_{2} … x_{m} and w_{U} = z_{1}z_{2} … z_{m} (the letters z_{i} are ordered pairs (b_{l}, j)). If (x_{i}, x_{i+1}) ∈ U, then either x_{i} ∈ B_{l}, x_{i+1} ∈ B_{l′} with l < l′, or x_{i}, x_{i+1} are both in the same underlined block B_{l}.

In the first case, z_{i} = (b_{l}, j) and z_{i+1} = (b_{l′}, j′) for some j, j′. But as l < l′, we have z_{i} > z_{i+1} by (5.3). In the second case, z_{i} = (b_{l}, j) and z_{i+1} = (b_{l}, j′); but as l is underlined we have j > j′ = j − 1 and again z_{i} > z_{i+1}.

Now if (x, x_{i+1}) ∉ U, then either x_{i} ∈ B_{l}, x_{i+1} ∈ B_{l′} with l > l′, or x_{i}, x_{i+1} are both in the same non-underlined block B_{l}. In the first case the same argument as above shows that z_{i} < z_{i+1}. In the second case the labelling from left to right of the non-underlined letters of \overline{w} yields z_{i} = (b_{l}, j) < (b_{l}, j + 1) = z_{i+1}.

Next apply the second fundamental transformation to w_{U}. We obtain a rearrangement Φ(w_{U}) that statisfies

(5.6)  maj w_{U} = inv Φ(w_{U}).

Lemma 5.3. For each l = 1, 2, …, k both words w_{U} and Φ(w_{U}) contain the subword

(b_{l}, 1)(b_{l}, 2) … (b_{l}, m_{l}) (resp. (b_{l}, m_{l}) … (b_{l}, 2)(b_{l}, 1))

depending on whether l is non-underlined or underlined.

Proof. This is a consequence of Proposition 5.1 (ii).

Finally, if we apply the conjugation δ^{−1} to Φ(w_{U}) using the subwords w(B_{1}), …, w(B_{k}), we obtain a rearrangement δ^{−1} Φ(w_{U}) which is a rearrangement of the original word w and satisfies

(5.7)  inv Φ(w_{U}) = inv_{U} δ^{−1} Φ(w_{U}).

We shall denote it by Φ_{U}(w). All the above transformations are reversible. The product Φ_{U} = δ^{−1} ∘ Φ ∘ δ is a well-defined bijection of R(c) onto itself satisfying (5.1).

6. A proof of the ‘only if’ part of Theorem 1

The proof of that “only if” part will be the consequence of the following sequence of lemmas.

Lemma 6.1. If there exists an element x ∈ X such that U ⊂ (X \ {x}) × (X \ {x}) and U ≠ ∅, then the equidistribution of inv_{U} and maj_{U} does not hold.

Proof. Let w be a word having no letter equal to x and let v be a word in the class R(x^{m}w) (m ≥ 1). Denote by \overline{v} the word derived from a word v by deleting all its letters equal to x. Then inv_{U} v = inv_{U} \overline{v}. On the other hand, maj_{U} x^{m}\overline{v} = m × des_{U} \overline{v} + maj_{U} \overline{v}. As U is non-empty, there exists a rearrangement class R(w) and a word w′ ∈ R(w) such that des_{U} w′ ≥ 1. Thus there is a bound b such that for every m ≥ 1 and for every v ∈ R(x^{m}w) we have inv_{U} v ≤ b, while

max_{v∈R(x^{m}w)} maj_{U} v ≥ maj_{U} x^{m}\overline{v} ≥ m.

Lemma 6.2. If (x, y) ∈ U, (y, x) ∈ U and x ≠ y, and if the equidistribution of inv_{U} and maj_{U} holds, then

(x, x) ∈ U and (y, y) ∈ U.

Proof. Suppose (x, x) ∉ U. In the class R(x^{2}y) we have inv_{U} w = 2 for all w, while maj_{U} xyx = 3 and the equidistribution does not hold for R(x^{2}y).

Let X = {x, y, z}; at this stage it would be useful to have a thorough table of the relations U on X × X for which the equidistribution of inv_{U} and maj_{U} holds. As there are six elements in X × X \ diag X × X, there would be only sixty-four cases to consider. As there are many symmetries, the table could be rapidly set up. A verification by computer could also be used. We have preferred to verify the property in each case.

Lemma 6.3. If (x, y), (y, x), (x, z) and (z, x) belong to U, if x, y and z are different and if the equidistribution of inv_{U} and maj_{U} holds, then U contains the product {x, y, z} × {x, y, z}.

Proof. In other words, besides (x, x), (y, y) and (z, z) (as shown in Lemma 6.2), the relation U must also contain (y, z) and (z, y).

If the conclusion does not hold, there are three cases to be studied. The distributions of inv_{U} and maj_{U} on the rearrangement class R(xyz) are shown in the next table and are never identical.

(y, z) ∉ U, (z, y) ∈ U (y, z) ∈ U, (z, y) ∉ U (y, z) ∉ U, (z, y) ∉ U
w  inv_{U}  maj_{U}  inv_{U}  maj_{U}  inv_{U}  maj_{U}
xyz  2  1  3  3  2  1
xzy  3  3  2  1  2  1
yxz  2  3  3  3  2  3
yzx  2  2  3  3  2  3
zxy  3  3  2  3  2  3
zyx  3  3  2  2  2  2

If U is a relation on X × X, its symmetric part, i.e., the set of all ordered pairs (x, y) such that both (x, y) and (y, x) belong to U, is denoted by S(U). Also let A(U) = U \ S(U) be its asymmetric part. Finally, let X_{U} be the subset of X of all the x’s such that (x, y) ∈ S(U) (and so (y, x) ∈ S(U)) for some y ∈ X.

Lemma 6.4. If the equidistribution holds for U, then S(U) is an equivalence relation on X_{U} × X_{U}.

Proof. Let x ∈ X_{U} and let y ∈ X such that (x, y) ∈ S(U). If y = x, then (x, x) ∈ U. If y ≠ x, Lemma 6.2 also implies that (x, x) ∈ U. Thus S(U) is reflexive. By definition, S(U) is symmetric. Now let x, y, z ∈ X_{U} and suppose (x, y) ∈ S(U) and (y, z) ∈ S(U). Then Lemma 6.3 implies that (x, y) ∈ S(U). The relation is then transitive.

Thus, if the equidistribution holds for U, there is a partition {B_{1}, …, B_{l}} of X_{U} such that S(U) = B_{1} × B_{1} ∪ ⋯ ∪ B_{l} × B_{l}. The subsets B_{1}, …, B_{l} will be called the blocks of X_{U}.

Lemma 6.5. Suppose that the equidistribution holds for U and let x, y be two distinct elements belonging to the same block, say, B_{i} of X_{U} and let z be an element of X. Then

(z, x) ∈ U ⇔ (z, y) ∈ U ;
(x, z) ∈ U ⇔ (y, z) ∈ U.

Proof. If z ∈ B_{i}, then (x, z) ∈ S(U) and (y, z) ∈ S(U) and there is nothing to prove. If z belongs to another block B_{j} of X_{U} and if (z, x) ∈ U, then (x, z) ∉ U. Otherwise, we would have B_{i} = B_{j}. If z ∉ X_{u} and (z, x) ∈ U, again (x, z) ∉ U. Otherwise, (x, z) ∈ S(U) and this would contradict z ∉ X_{U}.

Suppose that conditions (z, x) ∈ U and (z, y) ∉ U hold. Two cases are to be considered : (a) (y, z) ∉ U ; (b) (y, z) ∈ U.

In case (a) we have (x, y), (y, x), (z, x) ∈ U, (x, z), (z, y), (y, z) ∉ U. But for each word w in the class R(xyz) we have inv_{U} w ≤ 2, while maj_{U} zxy = 3, so that the equidistribution would not hold.

In case (b) we have (x, y), (y, x), (z, x), (y, z) ∈ U, (x, z), (z, y) ∉ U. Let V = X × X \ U. Then inv_{V} w ≤ 2 for all w, while maj_{V} xzy = 3. Thus, the equidistribution would not hold for V and also for U.

Thus cases (a) and (b) cannot occur and consequently if (z, y) ∈ U holds, we must have (z, y) ∈ U. The elements x and y play a symmetric role, so that the first equivalence is proved.

The proof of the second equivalence is quite analogous. If (x, z) ∈ U, we have seen that (z, x) ∉ U. Suppose (y, z) ∉ U and consider the two cases : (a) (z, y) ∉ U ; (b) (z, y) ∈ U.

In case (a) we have (x, y), (y, x), (x, z) ∈ U, (z, x), (y, z), (z, y) ∉ U. Again for each w ∈ R(xyz) we have inv_{U} w ≤ 2, while maj_{U} yxz = 3, so that the equidistribution does not hold.

In case (b) we have (x, y), (y, x), (x, z), (z, y) ∈ U, (z, x), (y, z) ∉ U. Let V = X × X \ U. Then inv_{V} w ≤ 2, while maj_{V} yzx = 3, so that the equidistribution does not hold for V, and then for U.

As x and y play a symmetric role, the second equivalence is also established.

Notation. It will be convenient to write x → y for (x, y) ∈ U, x ↛ y or y ↚ x for (x, y) ∉ U, x ⇀ ↽ y for (x, y) ∈ S(U).

Lemma 6.6. Suppose that the equidistribution holds for U. Then, either there is a block B_{1} of X_{U} with the property

∀ x ∈ B_{1}, ∀ y ∈ X \ B_{1}, then (x, y) ∉ U ; or there exists an x ∈ X \ X_{U} such that

∀ y ∈ X, then (x, y) ∉ U.

The foregoing property means that by rearranging the elements of X, either the top left corner B_{1} × (X \ B_{1}) of X × X, or a left block C × X has no intersection with U.

Proof. Suppose that the conclusion is false. This means that for every block B_{i} of X_{U} there is x ∈ B_{i}, y ∈ X \ B_{i} such that (x, y) ∈ U and also that for all x ∈ X \ X_{U} there is y ∈ X \ {x} such that (x, y) ∈ U.

Let x_{0} ∈ X. If x_{0} belongs to a block B_{i_{0}}, there is x_{1} ∈ B_{i_{0}} and x_{2} ∉ B_{i_{0}} such that x_{0} ⇀ ↽ x_{1} → x_{2}. But the previous lemma says that :

X × B_{1} B_{1}  X \ B_{1} B_{1}×(X \B_{1})  _{(X \ C) × C C  X \ C C×X}

Fig. 2

if x_{0} ⇀ ↽ x_{1} and x_{1} → x_{2}, then x_{0} → x_{2}. Also x_{2} ↛ x_{0}. Now, either x_{2} ∈ B_{i_{2}} with i_{2} ≠ i_{1} or x_{2} ∉ X_{U}. In the first case there is x_{3} ∈ B_{i_{2}} and x_{4} ∉ B_{i_{2}} such that x_{2} ⇀ ↽ x_{3} → x_{4}. Using the same lemma we also have x_{2} → x_{4} and x_{4} ↛ x_{2}. If x_{2} ∉ X_{U}, there is x_{4} ≠ x_{2} such that x_{2} → x_{4} and also x_{4} ↛ x_{2}, because x_{2} ∉ X_{U}.

We can then build a sequence (x_{0}, x_{2}, x_{4}, …) with the property

x_{0} → x_{2} → x_{4} → x_{6} → ⋯
x_{0} ↚ x_{2} ↚ x_{4} ↚ x_{6} ↚ ⋯

and such that x_{2i} ≠ x_{2i+2} at each step. If we had started with an element x_{0} ∉ X_{U}, the conclusion would have been the same.

The above sequence cannot be infinite and have all its elements distinct, so that, after relabelling, there is a finite sequence (y_{1}, y_{2}, …, y_{n+1}) of elements of X with the following properties :

(a) n ≥ 2 ;

(b) all terms y_{1}, y_{2}, …, y_{n} are different ;

(c) y_{1} → y_{2} → y_{3} → ⋯ → y_{n} → y_{n+1} = y_{1} ;

(d) y_{1} ↚ y_{2} ↚ y_{3} ↚ ⋯ ↚ y_{n} ↚ y_{n+1} = y_{1} ; If n = 2, we have y_{1} → y_{2} → y_{1} and y_{1} ↚ y_{2} ↚ y_{1}, a contradiction, so that n ≥ 3.

Consider the class R(y_{1}y_{2} … y_{n}). Then maj_{U} y_{1}y_{2} … y_{n} = 1 + 2 + ⋯ + (n − 1) = n(n − 1)/2. If there is a word v = z_{1}z_{2} … z_{n} ∈ R(y_{1}y_{2} … y_{n}) such that inv_{U} v = n(n − 1)/2, this means that

\begin{aligned}z_{1} → z_{2}, z_{1} → z_{3}, …, z_{1} & → z_{n} \\ z_{2} → z_{3}, …, z_{2} & → z_{n} \\ … \\ z_{n−1} & → z_{n} \end{aligned}  (⋆)

If z_{1} = y_{i} with 2 ≤ i ≤ n+1, let j be the unique integer such that z_{j} = y_{i−1}. Relation (e) above says that z_{j} = y_{i−1} ↚ y_{i} = z_{1}. This contradicts (⋆).

Let C = {x ∈ X \ X_{U} : ∀ y ∈ X, x ↛ y }. From Lemma 6.6 it follows that, if the equidistribution hods and C is empty, there is a unique block B_{1} of X_{U} such that

(⋆ ⋆)  ∀ x ∈ B_{1}, ∀ y ∈ X \ B_{1}, then x ↛ y.

Lemma 6.7. Suppose that the equidistribution holds for U. If C is non-empty, then

(⋆ ⋆ ⋆)  (X \ C) × C ⊂ U.

In other words, ∀ y ∈ X \ C, ∀ x ∈ C, then y → x.

If C is empty and if B_{1} is the block defined in (⋆ ⋆), then

(iv)  (X \ B) × B ⊂ U.

In other words, ∀ y ∈ X \ B, ∀ x ∈ B, then y → x.

See Fig. 1 : in each case the bottom rectangle to the right is entirely contained in U.

Proof. Assume that C is non-empty and suppose that (⋆ ⋆ ⋆) does not hold. Then there is y ∈ X \ C and also x ∈ C such that y ↛ x and y ≠ x. As y ∉ C, there is z ∈ X such that y → z. Notice that z may be equal to y, if y ∈ X_{U}, but z ≠ x, as we have assumed y ↛ x.

Consider the class R(xyz). By assumption, y ↛ x, y → z and also x ↛ y, x ↛ z, since x ∈ C. Four cases are to be considered :

(a) z → x, z → y ; (b) z → x, z ↛ y ; (c) z ↛ x, z → y ; (d) z ↛ x, z ↛ y.

In both cases (a) and (b) inv_{U} w ≤ 2 for all w, while maj_{U} yzx = 3. In both cases (c) and (d) inv_{U} w ≤ 1 for all w, while maj_{U} xyz = 2. Thus there is never equidistribution on R(xyz).

Suppose that C is empty. Let B_{1} be the block defined in (⋆ ⋆). If (iv) does not hold, there is y ∈ X \ B_{1} and also x ∈ B_{1} such that y ↛ z. As y ∉ B_{1} and since C is supposed to be empty, there exists z such that y → z. Again we have y ↛ x, y → z, x ↛ y, x ↛ z. The same analysis as above shows that there is no equidistribution on R(xyz).

x  y z x C or B_{1}

Fig. 3

It follows from Lemma 6.6 and Lemma 6.7 that, if the equidistribution holds for U, then, either C is non-empty and then

C × X is empty and (X \ C) × C ⊂ U, or C is empty and then there is a unique block B_{1} of X_{U} such that

B_{1} × (X \ B_{1}) is empty and (X \ B_{1})× ⊂ U.

The theorem is now easily proved by induction on card X. If the equidistribution holds for U defined on X × X and if C is non-empty, then the equidistribution also holds for the relation V = U ∩ (X \ C) × (X \ C) defined on (X \ C) × (X \ C). By induction V is bipartitional. Hence, U is also bipartitional (see Fig. 1).

In the same manner, if C is empty, then the equidistribution holds for the relation V = U ∩ (X \ B_{1}) × (X \ B_{1}). By induction V is bipartitional. Hence, U is also bipartitional.

7. Compatible bipartitional relations

The statistics “maj_{U}” and “inv_{U}” have been defined in (0.2); also remember that “des_{U}” counts the U-descents of the second kind, as defined at the end of the introduction. The calculation of the generating function for (des_{U}, maj_{U}) and the construction of the bijection that carries “maj_{U}” onto “inv_{U}” will be very similar to their equivalent derivations for (des′_{U}, maj′_{U}), “maj′_{U}” and “inv′_{U}.” Let

(7.1)  A_{U}(q; c) = ∑_{w} q^{inv_{U} w}  (w ∈ R(c)) ;

(7.2)  A_{U}(t, q; c) = ∑_{w} t^{des_{U} w}q^{maj_{U} w}  (w ∈ R(c)).

The identity

(7.3) A_{U}(q; c) = \left[{|c| \atop m_{1}, …, m_{k}}\right] ∏_{l=1}^{k} \binom{m_{l}}{c(B_{l})}q^{β_{l}\binom{m_{l}+1}{2}};

follows from (2.10), as we have to add the total number of underlined letters, i.e., ∑_{l} β_{l}m_{l} to the power of q.

The proof of the formula

(7.4) \begin{aligned}∑_{c} \frac{A_{U}(q; c)}{(q)_{|c|}}u^{c} & = ∏_{l;β_{l}=0} e_{q}(∑ u(B_{l})) × ∏_{l;β_{l}=1} E_{q}(q ∑ u(B_{l})) \\ & = \frac{∏_{l;β_{l}=1}(−q ∑ u(B_{l}); q)_{∞}}{∏_{l;β_{l}=0}(∑ u(B_{l}); q)_{∞}} ; \end{aligned}

follows the same pattern as the proof of (2.11).

Let A_{U}^{maj}(q; c) = ∑_{w} q^{maj_{U} w} (w ∈ R(c)). Again, we don’t prove that

A_{U}^{maj}(q; c) is equal to the right-hand side of (7.3). We’d rather derive the formulas for A_{U}(t, q; c), defined in (7.2), in the spirit of section 4.

Proposition 7.1. Let U be a compatible bipartitional relation. Then

(7.5) \frac{A_{U}(t, q; c)}{(t; q)_{|c|+1}}

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

(7.6)  ∑_{c} \frac{A_{U}(t, q; c)}{(t; q)_{|c|+1}}u^{c} = ∑_{s≥0} t^{s} \frac{∏_{l;β_{l}=1}(−q ∑ u(B_{l}); q)_{s}}{∏_{l;β_{l}=0}(∑ u(B_{l}); q)_{s+1}} .

Proof. Let w ↦ (\overline{w}, w(B_{1}), …, w(B_{l})) and (s′, p, \overline{w}) ↦ (s, (a_{l,i})) be the two bijections defined in section 4. We keep the same notations as in that section. In particular, let \overline{w} = \overline{x}_{1}\overline{x}_{2} … \overline{x}_{m}. The only difference to be brought to the constructions of those bijections is to notice that z_{m} = 1 iff \overline{x}_{m} belongs to an underlined block. Consequently, the sequences a_{l,1} … a_{l,m_{l}} associated with the underlined blocks are still strictly decreasing, but also a_{l,m_{l}} ≥ 1.

The reason is the following: let l be underlined and let \overline{x}_{i} be the rightmost letter of \overline{w} that belongs to the block B_{l}. If i = m, then a_{l,m_{l}} = p_{m} + z_{m} ≥ 1; if i < m, then, either there is one non-underlined letter in the factor \overline{x}_{i+1} … \overline{x}_{m} and necessarily one U-descent because U is supposed to be compatible, or all the letters in that factors are underlined and in particular z_{m} = 1. In both cases, a_{l,m_{l}} ≥ 1.

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

s ≥ a_{l,1} ≥ ⋯ ≥ a_{l,m_{l}} ≥ 0, if l is not underlined;
s ≥ a_{l,1} > ⋯ > a_{l,m_{l}} ≥ 1, if l is underlined.;
s = s′ + des_{U} \overline{w};

∑_{l,i} a_{l,i} = ∑_{i} p_{i} + maj_{U} \overline{w}.

In the same manner as in section 4 we have

\frac{1}{∏_{l} \binom{m_{l}}{c(B_{l})}} \frac{A_{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≥0} t^{s} ∏_{l;β_{l}=0} ∑_{s≥a_{l,1}≥···≥a_{l,m_{l}} ≥0} q^{a_{l,1}+···+a_{l,m_{l}}}

× ∏_{l;β_{l}=1} ∑_{s≥a_{l,1}>···>a_{l,m_{l}} ≥1} q^{a_{l,1}+···+a_{l,m_{l}}}

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

by (2.6) and (2.7).

As (7.4) holds (in the U-number-of-inversion version) and since (7.6) implies (7.4), we then have a proof of the ‘if’ part of Theorem 2.

The proof of the ‘only if’ part is straightforward. Suppose that U is non-compatible, so that there is an underlined block B_{l} to the left of a nonunderlined one B_{l′}, i.e., l < l′. Take two integers x ∈ B_{l} and x′_{l} ∈ B_{l′} and consider the class R(xx′) of the two words xx′ and x′x. Then inv_{U} xx′ = 2, inv_{U} x′x = 1, while maj_{U} xx′ = 3, maj_{U} x′x = 0.

8. A bijective Proof of Theorem 2

Let π = (\underline{B_{1}}, …, \underline{B_{n}}, B_{n+1}, …, B_{r}) be a compatible ordered bipartition having exactly n underlined blocks lying in the beginning and let U be the corresponding compatible bipartitional relation. As done in the papers by Steingrìmsson [St93] and Clarke and Foata (op. cit.), let us introduce an extra letter ⋆ and form the new compatible ordered bipartition

(8.1)  π^{⋆} = (\underline{B_{1}}, …, \underline{B_{n}}, \{⋆\}, \{B_{n+1}\}, …, \{B_{r}\}).

Denote by U^{⋆} the bipartitional relation associated with π^{⋆}. Notice that U^{⋆} is a relation on (X ∪ {⋆}) × (X ∪ {⋆}). We now make use of the transformation Φ_{U^{⋆}} (constructed in section 5) on the words in the alphabet X ∪ {⋆}.

If the word w = x_{1}x_{2} … x_{m} belongs to the class R(c), form the word w⋆. Its image under Φ_{U^{⋆}} will yield a word of the form w′⋆, by Proposition 5.1. There is a U^{⋆}-descent at position m, if and only if x_{m} is underlined. Hence

(8.2)  maj′_{U^{⋆}} w⋆ = maj′_{U} w + m χ(x_{m} is underlined).

Also adding ⋆ at the end of w′ will increase the number of U^{⋆}-inversions by exactly the number of underlined letters in w′, i.e., |w′|_{−}. Hence

(8.3)  inv′_{U^{⋆}} w′⋆ = inv′_{U} w′ + |w′|_{−}.

Hence

maj_{U} w = maj′_{U} w + m χ(x_{m} is underlined)  [by (0.2)]
= maj′_{U^{⋆}} w⋆  [by (8.2)]
= inv′_{U^{⋆}} w′⋆  [by (5.1)]
= inv′_{U} w′ + |w′|_{−}  [by (0.2)]
= inv_{U} w′.  [by (8.3)]

As Φ_{U^{⋆}} maps the set of all words in each rearrangement class ending with ⋆ onto the same set, the mapping w ↦ w′ is a bijection of R(c) onto itself. Moreover, it satisfies

(8.4)  maj_{U} w = inv_{U} w′.

Remark: Formulas (4.2) and (7.6) are the factorial generating functions for the pairs (des′_{U}, maj′_{U}) and (des_{U}, maj_{U}), respectively. On the other hand, the bijection Φ_{U} (defined in § 5) and the bijection w ↦ w′ just defined (that we shall denote by Ψ_{U}) satisfy (4.1) and (8.4). Let ?′_{U} = des′_{U} ∘Φ_{U}^{−1} and ?_{U} = des_{U} ∘Ψ_{U}^{−1}, so that

(des′_{U}, maj′_{U}) w = (?′_{U}, inv′_{U}) Φ_{U}(w) ;
(des_{U}, maj_{U}) w = (?_{U}, inv_{U}) Ψ_{U}(w).

Th natural question arises: can we find suitable predicates to define “?′_{U}” and “?_{U}” without any references to the bijections Φ_{U} and Ψ_{U}?

References

[An76] George E. Andrews, “The Theory of Partitions.” London, Addison-Wesley, 1976 (Encyclopedia of Math. and Its Appl., 2).

[Be94] François Bergeron, Gilbert Labelle, Pierre Leroux, “Théorie des espèces et combinatoire des structures arborescentes.” Montréal, Université du Québec à Montréal, Publ. du LACIM, no. 19, 1994.

[ClFo94] Robert J. Clarke and Dominique Foata, “Eulerian Calculus, I: univariable statistics,” Europ. J. Combinatorics, 15, 1994, p. 345–362.

[ClFo95a] Robert J. Clarke and Dominique Foata, Eulerian Calculus, II: an extension of Han’s fundamental transformation, to appear in Europ. J. Combinatorics, 1995.

[ClFo95b] Robert J. Clarke and Dominique Foata, Eulerian Calculus, III: the ubiquitous Cauchy formula, to appear in Europ. J. Combinatorics, 1995.

[Co70] Louis Comtet, “Analyse Combinatoire, vol. 1 and 2.” Paris, Presses Universitaires de Frances, 1970. (English edition Advanced Combinatorics, D. Reidel, Dordrecht, 1974).

[Fo68] Dominique Foata, “On the Netto inversion number of a sequence,” Proc. Amer. Math. Soc., 19, 1968, p. 236–240.

[Fo74] Dominique Foata, “La série génératrice exponentielle dans les problèmes d’énumération.” Montréal, Presses Universitaires de Montréal, 1974.

[Fo95] Dominique Foata, Les distributions Euler-Mahoniennes sur les mots,

to appear in Discrete Math., 1995.

[GaRa90] George Gasper and Mizan Rahman, “Basic Hypergeometric Series.” London, Cambridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[Han95] Guo-Niu Han, Ordres bipartitionnaires et statistiques sur les mots, to appear in Electronic J. Combinatorics, 1995.

[Kn73] Donald E. Knuth, “The Art of Computer Programming, vol. 3, Sorting and Searching.” Addison-Wesley, Reading, 1973.

[Kn92] Donald E. Knuth, “Convolutional Polynomials,” Mathematica J., 2, 1992, p. 67–78.

[Lo83] M. Lothaire, “Combinatorics on words.” Reading, Addison-Wesley, 1983 (Encyclopedia of Math. and its Appl., 17).

[Mac13] 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, p. 314–321.

[Mac15] P.A. MacMahon, “Combinatory Analysis, vol. 1.” Cambridge, Cambridge Univ. Press, 1915 (Reprinted by Chelsea, New York, 1955).

[Mac78] P.A. MacMahon, Collected Papers, vol. 1 [G.E. Andrews, ed.]. Cam-

bridge, Mass., The M.I.T. Press, 1978.

[Sl94] N.J.A. Sloane, “A Handbook of Integer Sequences.” New York, Academic Press, 1973.

[St93] Einar Steingrìmsson, “Permutation Statistics of Indexed Permutations,” Europ. J. Combinatorics, 15, 1994, p. xxx–xxx.