Mahonian STAT on rearrangement class of words
Shishuo Fu Ting Hua Vincent Vajnovszki


STAT on words]Mahonian STAT on rearrangement class of words

S. Fu]Shishuo Fu
College of Mathematics and Statistics, Chongqing University, Huxi Campus LD 506, Chongqing 401331, P.R. China.
fsshuo@cqu.edu.cn

T. Hua]Ting Hua
College of Mathematics and Statistics, Chongqing University, Huxi Campus, Chongqing 401331, P.R. China.
htingzl@sina.com

V. Vajnovszki]Vincent Vajnovszki
LE2I, Université de Bourgogne Franche-Comté, BP 47870, 21078 Dijon Cedex, France
vvajnov@u-bourgogne.fr





In 2000, Babson and Steingrímsson generalized the notion of permutation patterns to the so-called vincular patterns, and they showed that many Mahonian statistics can be expressed as sums of vincular pattern occurrence statistics. STAT is one of such Mahonian statistics discoverd by them. In 2016, Kitaev and the third author introduced a words analogue of STAT and proved a joint equidistribution result involving two sextuple statistics on the whole set of words with fixed length and alphabet. Moreover, their computer experiments hinted at a finer involution on R(w),  the rearrangement class of a given word w. We construct such an involution in this paper, which yields a comparable joint equidistribution between two sextuple statistics over R(w). Our involution builds on Burstein's involution and Foata-Schützenberger's involution that utilizes the celebrated RSK algorithm. 





[
    [
    December 30, 2023
=====================








§ INTRODUCTION


An occurrence of a classical pattern p in a permutation π is a subsequence of π that is order-isomorphic to p, i.e., that has the same pairwise comparisons as p. For example, 41253 has two occurrences of the pattern 3142 in its subsequences 4153 and 4253. The study of (classical) permutation patterns have mostly been with respect to avoidance, i.e., on the enumeration of permutations in the symmetric group _n that have no occurrences of the pattern(s) in question. The tone is generally believed to be set in 1968, when Knuth published Volume one of The Art of Computer Programming <cit.>. It was observed in <cit.> that the number of 231-avoiding permutations are enumerated by the Catalan numbers. See <cit.> and the references therein for a comprehensive introduction to patterns in permutations.

In 2000, Babson and Steingrímsson <cit.> traced out a new line of research by generalizing classical patterns to what are now known as vincular patterns. In an occurrence of a vincular pattern, some letters of that order-isomorphic subsequence may be required to be adjacent in the permutation, and this is done by underscoring the adjacent letters in the expression for the pattern. For our previous example, only 4153 represents an occurrence of the vincular pattern 3142 in 41253. As was investigated thoroughly in <cit.>, these vincular patterns turned out to be the “building blocks” in their classification of Mahonian statistics. Recall that a permutation statistic is called Mahonian precisely when it has the same distribution, on _n, as , the number of inversions. Given a vincular pattern τ and a permutation π, we denote by (τ)π the number of occurrences of the pattern τ in π. When it causes no confusion, we will even drop the parentheses. For instance, it was observed/defined in <cit.>:

    =21=21+312+321+231,
       =21+132+231+321,
       =21+132+231+321,
       =21+132+213+321.

Note that the first three Mahonian statistics are well-known ones putting on a new look, while the last one  was one of those introduced in <cit.> and shown to be Mahonian.

Now we state the joint equidistribution results involving STAT obtained by Burstein <cit.> on _n and by Kitaev and the third author <cit.> on [m]^n, the set of length n words over the alphabet [m]:={1,2,…,m}. These two results largely motivated this work. All undefined statistics will be introduced in the next section. For the spelling of the statistics, we follow the convention of <cit.>, i.e., all Mahonian statistics are spelled with uppercase letters, all Eulerian statistics are spelled with lowercase letters, while all the remaining ones are merely capitalized. Moreover, the italic letters are used for set-valued statistics, such as Id in Theorem <ref> and Corollary <ref>.


Statistics (, , , , ) and
(, , , , ) have the same joint distribution on _n for all n.



Statistics (, , , , , ) and
(, , , , , ) have the same joint distribution on [m]^n for all m and n.


A quick look at Table <ref> reveals that when one wants to extend the above results to the rearrangement class R(w), the statistic  must be dropped. In the meantime, the involution we are going to construct actually preserves the inverse descent set Id (see Definition <ref>). The following are the main results of this paper.



Statistics (, Id, , , ) and
(, Id, , , ) have the same joint distribution on _n for all n.


It is worth mentioning that in <cit.> it has been shown that (Id, , ) and
(Id, , ) are equidistributed on _n for all n.


In view of this theorem and the standard “coding/decoding” between words and permutations <cit.>, we derive the following version for words, where the statistics have to be redefined on words accordingly. We defer the details to the next section.


Statistics (, Id, , , ) and
(, Id, , , ) have the same joint distribution on R(w) for any word w.


Since Id uniquely determinates both  and  (see Definition <ref>), the next corollary is a consequence of the previous one, and it is similar to Theorem <ref>, except
 is replaced by  and the equidistribution
is stated on the rearrangement classes.


Statistics (, , , , , ) and
(, , , , , ) have the same joint distribution on R(w) for any word w.



In the next section, we will first present the formal definitions of all the statistics that concern us here, and then explain the transition from Theorem <ref> to Corollary <ref>. Theorem <ref> will be proved in Section <ref>, where Foata-Schützenberger's involution via RSK correspondence will be recalled. We conclude with some further questions suggested by this work.







§ PRELIMINARIES


Since all the statistics that concern us here can be defined on both permutations and words, and that we have two versions of joint equidistribution results, some care needs to be taken to avoid unnecessary repetitions. We decide to define all the statistics on the rearrangement class R(w) for a word w of length n, making sure that when w is composed of distinct letters, and thus R(w) becomes essentially _n, all the statistics reduce to the original ones defined on _n. On the other hand, for the two equidistribution results we first explain how to derive Corollary <ref> from Theorem <ref> and then construct, in the next section, the key involution on _n.

We consider words w=w_1w_2⋯ w_n on a totally ordered alphabet 𝒜. Without loss of generality, we can always take 𝒜 to be the interval [m]={1,2,…,m}. By rearrangement class R(w), we mean the set of all words that can be obtained by permuting the letters of w. Within each class R(w), there is a unique non-decreasing word that we denote by w. If the letters of w are distinct, then R(w) is in bijection with the symmetric group _n via the following “coding” map <cit.>.

Given a word w=w_1w_2⋯ w_n, we code it by the permutation c(w)=c(w)_1c(w)_2⋯ c(w)_n∈_n uniquely defined by

    c(w)_i < c(w)_j     if and only if  w_i<w_j,    or
     w_i=w_j,    for i<j.

This gives rise to a map c:[m]^n→_n, which we call the coding map, and clearly c is a 
surjection if and only if m≥ n.

For example, the word w=2 1 2 2 3 1 is coded by c(w)=3 1 4 5 6 2. Now we are ready to define all seven statistics encountered in the introduction. The true or false function χ is used in the definition of  for our 
convenience: χ(S)=1 (resp. χ(S)=0) if the statement S is true (resp. false).


Let w=w_1w_2⋯ w_n be a word. The descent set of w, D(w), the inverse descent set of w, Id(w), and a peculiar index set (needed in Section <ref>) that we call the shuffle set of w, Sh(w) are set-valued statistics defined as follows:

    D(w)   ={i: w_i>w_i+1, 1≤ i<n},
    
    Id(w)   ={c(w)_i: ∃ j<i,  s.t.  c(w)_j=c(w)_i+1},
    
    Sh(w)   ={i: w_i≥ w_1>w_i+1 or w_i< w_1≤ w_i+1, 1≤ i<n}.

We define the following seven statistics on w:

    w    = w_1,   w = ∑_j∈ D(w)1,   w = ∑_j∈ Id(w)1,
     w    = ∑_j=1^nχ(c(w)_j=c(w)_j+1+1),  take c(w)_n+1=0,
     w    =∑_j∈ D(w)j=(132+121+231+221+321+21)w,
     w    = ∑_j∈ Id(w)j,
     w    = (213+212+132+121+321+21)w.


We note that , , , all have been extended to words in <cit.>. Some of the definitions given here may look different but essentially are equivalent to those used in <cit.>, and our formulation of  makes it more convenient to define  on words.


When the word w happens to be a permutation in _n, then c(w)=w and all the above statistics agree with their original counterparts defined on permutations. This hopefully justifies our abuse of notation, i.e., we use the same name for these statistics, both on words and permutations. Moreover, it should be routine to verify that the coding map c preserves six statistics defined above, with  being the only exception.

    (, , Id, , )w    =(, , Id, , )c(w).

For the previous example with w=2 1 2 2 3 1 and c(w)=3 1 4 5 6 2, we see w=2= c(w), Id w={2}=Id c(w), w=6= c(w), etc.


In order to deduce Corollary <ref> from Theorem <ref>, we need to pay some attention to the “decoding” map from _n back to [m]^n. In general, the preimage of a given permutation under the coding map c is not unique and therefore this decoding is not well defined. For instance, for both w=2 1 2 2 3 1 and v=2 1 2 3 3 1, we see c(w)=c(v)=3 1 4 5 6 2, with R(w)≠ R(v). This should be somewhat expected since when w contains repeated letters, we have |R(w)|<|_n|. To deal with this, we introduce the notion of compatible permutations.




Given the rearrangement class R(w) for a word w of length n, we denote _R(w) the subset of _n that is the image of R(w) under the coding map c, and we call it the set of compatible permutations with respect to R(w). More precisely,

    _R(w)={π∈_n: π=c(v),  for some v∈ R(w)}.


It is clear from Definition <ref> that if we restrict c on a rearrangement class R(w), it is injective, hence it induces a bijection between R(w) and _R(w), with a unique inverse c^-1 defined on _R(w):

    c=c|_R(w):      R(w)→_R(w),
    
    c^-1:     _R(w)→ R(w),
    c^-1∘ c(v)   =v,   ∀ v∈ R(w),
    c∘ c^-1(π)   =π,   ∀π∈_R(w).


The next proposition characterizes _R(w) using w and the inverse descent set.


Given R(w) and suppose w=u_1⋯ u_b_1u_b_1+1⋯ u_b_2⋯ u_b_k+1⋯ u_n, where 1≤ b_1<b_2<⋯<b_k≤ n and

    u_1=⋯=u_b_1<u_b_1+1=⋯=u_b_2<⋯<u_b_k+1=⋯=u_n.

Then π∈_R(w) if and only if Id(π)⊆{b_1, b_2,…, b_k}.


Take a permutation π∈_R(w), then π=c(v) for some v∈ R(w), and consequently Id(π)⊆{b_1, b_2,…, b_k}, this takes care of the “only if” part. We finish the proof by simply noting that both _R(w) and {π∈_n:Id(π)⊆{b_1, b_2,…, b_k}} are enumerated by |R(w)|=nb_1,b_2-b_1,…,n-b_k.














In the next section, we are going to construct an involution ϕ on _n such that for any π∈_n,

    (, Id, , , )π   =(, Id, , , )ϕ(π).

This proves Theorem <ref>. Now consider the function composition

    ϕ_R(w)   =c^-1∘ϕ∘ c.

Note that for any v∈ R(w), c(v)∈_R(w), and since Id(ϕ(c(v)))=Id(c(v)), we have ϕ(c(v))∈_R(w) thanks to Proposition <ref>, thus ϕ_R(w): R(w)→ R(w) is well-defined. Now we show that ϕ_R(w) is an involution on R(w) that proves Corollary <ref>.

We first prove that ϕ_R(w) is indeed an involution. Let v∈ R(w), we have

    ϕ_R(w)^2(v)   =(c^-1∘ϕ∘ c)∘(c^-1∘ϕ∘ c)v
       =(c^-1∘ϕ)∘(c∘ c^-1)∘(ϕ∘ c)v
    (<ref>)             =(c^-1∘ϕ)∘(ϕ∘ c)v
       =(c^-1∘(ϕ∘ϕ)∘ c)v
    ϕ is an involution        =(c^-1∘ c)v
    (<ref>)             =v.

Next we apply (<ref>) (twice) and (<ref>) to get

    (, Id, , )v    =(, Id, , )ϕ_R(w)(v).

Finally it is straightforward to check that v= ϕ_R(w)(v) since π= ϕ(π) by relation (<ref>). This immediately establishes Corollary <ref> and ends the proof.







§ INVOLUTION Φ


In this section we aim to construct the aforementioned map ϕ from _n into itself, and we show that i) it is an involution and ii) it satisfies (<ref>). First off, we recall an involution  defined on _n that was first considered by Schützenberger <cit.> and further explored by Foata-Schützenberger <cit.>. It builds on two permutation symmetries, namely reversal r and complement c, as well as the famous Robinson-Schensted-Knuth (RSK) algorithm <cit.>. We collect the relevant definitions and notations below. Given a permutation π=π_1π_2⋯π_n∈_n,

    π^r=π_1^rπ_2^r⋯π_n^r,  with π^r_i=π_n+1-i,  for 1≤ i≤ n,
       π^c=π_1^cπ_2^c⋯π_n^c,  with π^c_i=n+1-π_i,  for 1≤ i≤ n,
       π^rc=π_1^rcπ_2^rc⋯π_n^rc,  with π^rc_i=n+1-π_n+1-i,  for 1≤ i≤ n,
       πRSK⟶ (P_π,Q_π) RSK^-1⟶π,

where RSK is a bijection between _n and the set of ordered pairs of n-cell standard Young tableaux (SYT) with the same shape. Note that π↦π^r, π↦π^c and π↦π^rc=π^cr are involutions on _n.

We usually call P_π the insertion tableau and Q_π the recording tableau of π. In general, for two unrelated permutations π,σ∈_n, P_π and Q_σ are unlikely to be of the same shape. However, it was noted in <cit.> that P_π and Q_π^rc are indeed of the same shape, so the following map  is a well-defined involution on _n.

    :    _n→_n
       π↦ RSK^-1(P_π,Q_π^rc)

The next property of  is of great importance for our later use and is the main reason that urged us to involve  in our construction of ϕ.

For any π∈_n, the map  as defined above preserves the inverse descent set Id(π) and exchanges the descent set D(π) with its complement to n. In other words one has simultaneously:

    Id((π))   =Id(π),  and
    D((π))   ={n-k: k∈ D(π)}.






Now given a permutation π∈_n with π=k, let us denote as π^t=π_t_1⋯π_t_n-k (resp. π^b=π_b_1⋯π_b_k-1) the top (resp. bottom) subword that is composed of all the letters larger (resp. smaller) than k. We also need the shuffle set Sh(π) defined in Definition <ref>. For example, let π=5 4 6 7 3 1 9 8 2, then π^t=6 7 9 8, π^b=4 3 1 2 and Sh(π)={1,2,4,6,8}. Conversely, it should be clear how to recover the unique permutation π that corresponds to an appropriate triple (π^t,π^b,Sh(π)), so we omit the details. We are ready to describe our key map ϕ using this defining triple: (top subword, bottom subword, shuffle set).

Given π∈_n, let ϕ(π) be the unique permutation that corresponds to (ϕ(π)^t,ϕ(π)^b,Sh(ϕ(π))), where

    ϕ(π)^t    := c^-1∘∘ c(π^t),
    ϕ(π)^b    := (π^b),
    Sh(ϕ(π))    := {1}∪{n+1-k:k≥ 2, k∈ Sh(π)}    if |Sh(π)| is odd,
    {n+1-k:k≥ 2, k∈ Sh(π)}    if |Sh(π)| is even.



It should be noted that the idea to associate π with the triple (π^t,π^b,Sh(π)) is motivated by Burstein's involution p introduced in <cit.> to prove Theorem <ref>. Actually in our setting, Burstern's p can be defined using the same (<ref>), together with (<ref>) and (<ref>) replaced by

    p(π)^t    = c^-1((c(π^t))^rc),  and 
    
    p(π)^b    = (π^b)^rc.

Moreover, in view of (<ref>) and Proposition <ref>, (<ref>) is well-defined. Thirdly, by the above definition, it follows that ϕ(π)= π. Lastly, using the fact that  is an involution, it is routine (using the associated triple) to check that ϕ^2(π)=π for any π∈_n, i.e., ϕ is an involution on _n as claimed.


All remained to be done is to prove (<ref>). Namely, we need to show for every π∈_n:

    ϕ(π)   = π,
    
    Id(ϕ(π))   =Id(π),
     ϕ(π)   = π,
     ϕ(π)   = π,
     ϕ(π)   = π.

We break it up into the following three lemmas and one corollary.

Id(ϕ(π))=Id(π).


First note that when the first letter π is fixed, Id(π) only depends on Id(π^t) and Id(π^b), and is not affected by Sh(π) at all. Then we simply use (<ref>) to finish the proof.



π+ π=(n+1) π-( π-1).


This is precisely Lemma 2.7 in <cit.>, hence we omit the proof.



π+ ϕ(π)=(n+1) π-( π-1).


The basic idea is to pair the descents of π with the descents of ϕ(π). We discuss by two cases.


  * If i∈ D(π)\ Sh(π), then either π_i>π_i+1>π_1 or π_1>π_i>π_i+1. Using (<ref>) and (<ref>) we see that either ϕ(π)_n+1-i>ϕ(π)_n+2-i>ϕ(π)_1 or ϕ(π)_1>ϕ(π)_n+1-i>ϕ(π)_n+2-i, both of which lead to (n+1-i)∈ D(ϕ(π))\ Sh(ϕ(π)). So this pair contributes 
    i+(n+1-i)=n+1
 to the sum π+ ϕ(π).

  * If i∈ D(π)∩ Sh(π), then π_i≥π_1>π_i+1, and according to (<ref>), ϕ(π)_n+1-i-s_i≥ϕ(π)_1>ϕ(π)_n+2-i-s_i, where s_i is the length of the maximal block of consecutive entries of ϕ(π) that ends with ϕ(π)_n+1-i and is contained in ϕ(π)^b. Therefore this pair contributes 
    i+(n+1-i-s_i)=n+1-s_i
 to the sum π+ ϕ(π).

All such s_i as defined above clearly sum up to the total length of ϕ(π)^b:

    ∑_i∈ D(π)∩ Sh(π)s_i=|ϕ(π)^b|=|π^b|= π-1.

We add the contributions from both cases to arrive at the desired identity.



ϕ(π)= π,  ϕ(π)= π,   ϕ(π)= π.


It immediately follows from Lemma <ref> and <ref> that ϕ(π)= π, and since ϕ is an involution we also get ϕ(π)= π. Finally we have:

    (n+1) ϕ(π)-( ϕ(π)-1)     Lemma <ref>= ϕ(π)+ ϕ^2(π)
       aaaϕ^2=1aa= π+ π
        Lemma <ref>= (n+1) π-( π-1).

This directly leads to ϕ(π)= π since we already noted that ϕ(π)= π.

This involution ϕ is admittedly a bit involved, so we include one complete example here to illustrate it.

Given w=1 1 2 3 4 4 4 5 6, take v=4 3 4 4 2 1 6 5 1 ∈ R(w). We first compute the statistics on v:

    (, Id, , , )v=(5, {2,3,4,8}, 4, 25, 21).

Now let π=c(v)=5 4 6 7 3 1 9 8 2∈_9, we proceed to find ϕ(π). First we get the defining triple associated with π:

    (π^t,π^b,Sh(π))=(6 7 9 8,  4 3 1 2, {1,2,4,6,8}).

Applying ϕ and according to (<ref>), we get immediately Sh(ϕ(π))={1,2,4,6,8}. But for ϕ(π)^t and ϕ(π)^b, which involve the map , we need to invoke the RSK algorithm. We first apply RSK on c(π^t)=1 2 4 3 and c(π^t)^rc=2 1 3 4 to get the following four SYT.

3+1
111
122
133
214
0.8-1.6P_c(π^t)
3+1
111
122
133
214
0.8-1.6Q_c(π^t)
3+1
111
123
134
212
0.8-1.6P_c(π^t)^rc
3+1
111
123
134
212
0.8-1.6Q_c(π^t)^rc

Then we apply inverse RSK on the pair (P_c(π^t), Q_c(π^t)^rc) to get (c(π^t))=4 1 2 3, hence 
ϕ(π)^t=c^-1∘∘ c(π^t)=9 6 7 8. Similarly for ϕ(π)^b, we apply RSK on π^b=4 3 1 2 and (π^b)^rc=3 4 2 1 to get the following four SYT.

2+1+1
111
122
213
314
0.6-2P_π^b
2+1+1
111
124
212
313
0.6-2Q_π^b
2+1+1
111
124
212
313
0.6-2P_(π^b)^rc
2+1+1
111
122
213
314
0.6-2Q_(π^b)^rc

Reversing RSK on (P_π^b, Q_(π^b)^rc) then produces ϕ(π)^b=(π^b)=1 4 3 2. Together we have

    (ϕ(π)^t,ϕ(π)^b,Sh(ϕ(π)))=(9 6 7 8,  1 4 3 2, {1,2,4,6,8}),

which corresponds uniquely to ϕ(π)=5 1 9 6 4 3 7 8 2∈_R(w). Therefore ϕ_R(w)(v)=c^-1(ϕ(π))=4 1 6 4 3 2 4 5 1. Finally we check the statistics match up indeed (with  and  switched).

    (, Id, , , )ϕ_R(w)(v)=(5, {2,3,4,8}, 4, 25, 21).







§ FURTHER QUESTIONS


Seeing our equidistribution result in Corollary <ref>, a natural next step is to consider the so-called “k-extension” (see <cit.>). Namely, for our prototype of the alphabet, [m]={1,2,…,m}, we take two non-negative integers l and k such that l+k=m. Then we call the letters 1,2,…,l small and the letters l+1,l+2,…,l+k=m large. Now consider any total ordering, say Ø, on [m] that is compatible with k, in the sense that for any small letter x and any large letter y, we have (x,y)∈Ø. Both  and  have their k-extensions defined with respect to Ø, so one may ask if there exists a k-extension for , such that the joint distribution of (, , ) are still the same as that of (, , ).
 
Finally, Corollary <ref> justifies (, ) as a new Euler-Mahonian (over rearrangement class of words) pair in the family consisting of (, ), (, ) and (, ) (see <cit.> for undefined statistics and further details). It would be interesting to pair other Mahonian statistics discovered in <cit.> with either  or , and then pigeonhole the resulting pairs into the existing (or even new) families of Euler-Mahonian statistics. Another possible direction for furthering the study on  is to consider the equidistribution problems on pattern avoiding permutations, see the recent work in <cit.>.






§ ACKNOWLEDGEMENT

The first two authors were supported by the Fundamental Research Funds for the Central Universities (No. CQDXWL-2014-Z004) and the National Natural Science Foundation of China (No. 11501061).








99
AmN. Amini, Equidistributions of Mahonian statistics over pattern avoiding permutations, https://arxiv.org/abs/1705.05298arXiv:1705.05298.

BSE. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin, B44b (2000): 18 pp.

BurA. Burstein, On joint distribution of adjacencies, descents and some Mahonian statistics, in: Proc. AN, in: Discrete Math. Theor. Comp. Sci, 2010, pp. 601-612 (also in FPSAC 2010, San Francisco, USA).



ChJ. N. Chen, Equidistributions of MAJ and STAT over pattern avoiding permutations, https://arxiv.org/abs/1707.07195arXiv:1707.07195.

CFR. J. Clarke and D. Foata, Eulerian calculus, II: an extension of Han's fundamental transformation, European Journal of Combinatorics, 16(3) (1995): 221-252.

CSZR. J. Clarke, E. Steingrímsson and J. Zeng, New Euler-Mahonian statistics on permutations and words, Advances in Applied Mathematics, 18(3) (1997): 237-270.


FSD. Foata and M. P. Schützenberger, Major index and inversion number of permutations, Mathematische Nachrichten, 83(1) (1978): 143-159.


Han1G. N. Han, Une transformation fondamentale sur les réarrangements de mots, Advances in Mathematics, 105(1) (1994): 26-41.

Han2G. N. Han, The k-extension of a Mahonian statistic, Advances in Applied Mathematics, 16(3) (1995): 297-305.

KitS. Kitaev, Patterns in permutations and words, Springer Science & Business Media, 2011.

KVS. Kitaev and V. Vajnovszki, Mahonian STAT on words, Information Processing Letters, 116(2) (2016): 157-162.

KnuD. E. Knuth, The Art of Computer Programming. Volume 1. Addison-Wesley Publishing Co., Reading, Mass., 1968.

SchuM. P. Schützenberger, Quelques remarques sur une construction de Schensted, Séminaire Dubreil. Algèbre et théorie des nombres, 16(2) (1963): 1–12.



StanR. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, Cambridge, United Kingdom, 1999.


















