A minimaj-preserving crystal on ordered multiset partitions
Georgia Benkart Laura Colmenarejo Pamela E. Harris Rosa Orellana Greta Panova Anne Schilling Martha Yip
math.CO 05A19 (Primary), 05A18, 05E05, 05E10, 20G42, 17B37 (Secondary)




Benkart]Georgia Benkart
[G. Benkart]Department of Mathematics, University of Wisconsin-Madison, 480 Lincoln Dr.
Madison, WI 53706, U.S.A.
benkart@math.wisc.edu

Colmenarejo]Laura Colmenarejo
[L. Colmenarejo]Department of Mathematics and Statistics,  York University, 4700 Keele Street, Toronto, 
Ontario M3J 1P3, Canada
lcolme@yorku.ca
http://www.yorku.ca/ lcolme/

Harris]Pamela E. Harris
[P. E. Harris]Mathematics and Statistics, Williams College, Bascom House, Rm 106C
Bascom House, 33 Stetson Court, Williamstown, MA 01267, U.S.A. 
peh2@williams.edu
https://math.williams.edu/profile/peh2/

Orellana]Rosa Orellana
[R. Orellana]Mathematics Department, Dartmouth College, 6188 Kemeny Hall,
Hanover, NH 03755, U.S.A.
Rosa.C.Orellana@dartmouth.edu
https://math.dartmouth.edu/ orellana/

Panova]Greta Panova
[G. Panova]Mathematics Department, University of Pennsylvania, 
209 South 33rd St, Philadelphia, PA 19104, U.S.A
panova@math.upenn.edu
https://www.math.upenn.edu/ panova/

Schilling]Anne Schilling
[A. Schilling]Department of Mathematics, University of California, One Shields
Avenue, Davis, CA 95616-8633, U.S.A.
anne@math.ucdavis.edu
http://www.math.ucdavis.edu/anne

Yip]Martha Yip
[M. Yip]Department of Mathematics, University of Kentucky, 715 Patterson Office Tower,
Lexington, KY 40506-0027, U.S.A.
martha.yip@uky.edu
http://www.ms.uky.edu/ myip/



[2000]Primary 05A19; Secondary 05A18, 05E05, 05E10, 20G42, 17B37



We provide a crystal structure on the set of ordered multiset partitions, which recently arose in
the pursuit of the Delta Conjecture.  This conjecture was stated by Haglund, Remmel and Wilson as a generalization 
of the Shuffle Conjecture. Various statistics on ordered multiset partitions arise in the combinatorial
analysis of the Delta Conjecture, one of them being the minimaj statistic, which is a variant of the
major index statistic on words. Our crystal has the property that the minimaj statistic is constant on connected 
components of the crystal. In particular, this yields another proof of the Schur positivity of the graded Frobenius 
series of the generalization R_n,k due to Haglund, Rhoades and Shimozono of the coinvariant algebra R_n.
The crystal structure also enables us to demonstrate the equidistributivity of the minimaj statistic with the major index 
statistic on ordered multiset partitions.


A minimaj-preserving crystal on ordered multiset partitions
    [
    December 30, 2023
===========================================================






§ INTRODUCTION



The Shuffle Conjecture <cit.>, now a theorem due to Carlsson and Mellit <cit.>,
provides an explicit combinatorial description of the bigraded Frobenius characteristic of the S_n-module of 
diagonal harmonic polynomials. It is stated in terms of parking functions and involves two statistics, 𝖺𝗋𝖾𝖺 
and 𝖽𝗂𝗇𝗏.

Recently, Haglund, Remmel and Wilson <cit.> introduced a generalization of the Shuffle Theorem,
coined the Delta Conjecture. The Delta Conjecture involves two quasisymmetric functions
𝖱𝗂𝗌𝖾_n,k(𝐱;q,t) and 𝖵𝖺𝗅_n,k(𝐱;q,t), which have 
combinatorial expressions in terms of labelled Dyck paths. In this paper, we are only concerned with the specializations 
q=0 or t=0, in which case <cit.> and <cit.> show

    𝖱𝗂𝗌𝖾_n,k(𝐱;0,t) = 𝖱𝗂𝗌𝖾_n,k(𝐱;t,0) = 
    	𝖵𝖺𝗅_n,k(𝐱;0,t) = 𝖵𝖺𝗅_n,k(𝐱;t,0).

It was proven in <cit.> that

    𝖵𝖺𝗅_n,k(𝐱;0,t) = ∑_π∈𝒪𝒫_n,k+1  t^(π)𝐱^(π),

where 𝒪𝒫_n,k+1 is the set of ordered multiset partitions of the multiset {1^ν_1,2^ν_2,…} 
into k+1 nonempty blocks and ν=(ν_1,ν_2,…) ranges over all weak compositions of n.
The weak composition ν is also called the weight of π, denoted (π)=ν. 
In addition, (π) is the minimum value of the major index of the set partition π over all possible ways to 
order the elements in each block of π. The symmetric function 𝖵𝖺𝗅_n,k(𝐱;0,t) is 
known <cit.> to be Schur positive, meaning that the coefficients are polynomials in t 
with nonnegative coefficients.

In this paper, we provide a crystal structure on the set of ordered multiset partitions 𝒪𝒫_n,k.
Crystal bases are q→ 0 shadows of representations for quantum groups U_q(𝔤) <cit.>, though they can also be understood from a purely combinatorial 
perspective <cit.>. In type A, the character of a connected crystal
component with highest weight element of highest weight λ is the Schur function 𝗌_λ.
Hence, having a type A crystal structure on a combinatorial set (in our case on 𝒪𝒫_n,k)
naturally yields the Schur expansion of the associated symmetric function. Furthermore, if the statistic
(in our case ) is constant on connected components, then the graded character can also be naturally
computed using the crystal.

Haglund, Rhoades and Shimozono <cit.> introduced a generalization R_n,k for k⩽ n 
of the coinvariant algebra R_n, with R_n,n=R_n. Just as the combinatorics of R_n is governed by permutations 
in S_n, the combinatorics of R_n,k is controlled by ordered set partitions of {1,2…,n} with k blocks.
The graded Frobenius series of R_n,k is (up to a minor twist) equal to 𝖵𝖺𝗅_n,k(𝐱;0,t).
It is still an open problem to find a bigraded S_n-module whose Frobenius image is  
𝖵𝖺𝗅_n,k(𝐱;q,t). Our crystal provides another representation-theoretic interpretation of
𝖵𝖺𝗅_n,k(𝐱;0,t) as a crystal character.

Wilson <cit.> analyzed various statistics on ordered multiset partitions, including 𝗂𝗇𝗏,
𝖽𝗂𝗇𝗏, , and . In particular, he gave a Carlitz type bijection, which
proves equidistributivity of 𝗂𝗇𝗏, 𝖽𝗂𝗇𝗏,  on 𝒪𝒫_n,k.
Rhoades <cit.> provided a non-bijective proof that these statistics are also equidistributed with
. Using our new crystal, we can give a bijective proof of the equidistributivity of the 
 statistic and the  statistic on ordered multiset partitions.

The paper is organized as follows. In Section <ref> we define ordered multiset partitions and 
the  and  statistics on them. In Section <ref> we provide a bijection 
φ from ordered multiset partitions to tuples of semistandard Young tableaux that will be used in 
Section <ref> to define a crystal structure, which preserves . We conclude in 
Section <ref> with a proof that the  and  statistics are equidistributed using 
the same bijection φ.




 §.§ Acknowledgments

Our work on this group project began at the workshop Algebraic Combinatorixx 2 at  the Banff International 
Research Station (BIRS) in May 2017.  “Team Schilling,”  as our group of authors is known, would like to extend thanks 
to the organizers of ACxx2,  to BIRS for hosting this workshop, and to the Mathematical Sciences Research Institute (MSRI) 
for sponsoring a follow-up meeting of some of the group members at MSRI in July 2017 supported by the National Science
Foundation under Grant No. DMS-1440140.
We would like to thank Meesue Yoo for early collaboration and Jim Haglund, Brendon Rhoades and Andrew Wilson for 
fruitful discussions. This work benefited from computations and experimentations in Sage <cit.>.

P. E. Harris was partially supported by NSF grant DMS–1620202. 
R. Orellana was partially supported by NSF grant DMS–1700058. 
G. Panova was partially supported by NSF grant DMS–1500834.
A. Schilling was partially supported by NSF grant  DMS–1500050. 
M. Yip was partially supported by Simons Collaboration grant 429920.




§ ORDERED MULTISET PARTITIONS AND THE MINIMAJ AND MAJ STATISTICS




We consider ordered multiset partitions of order n with k blocks.  
Given a weak composition ν = (ν_1, ν_2, …) of n into nonnegative integer parts,  
which we denote ν n,  let 𝒪𝒫_ν,k be the set of partitions of the multiset 
{i^ν_i| i ⩾ 1}  into k nonempty ordered blocks, such that the elements within each block are distinct.  
For each i⩾ 1, the notation i^ν_i should be interpreted as saying that the integer i occurs ν_i times 
in such a partition.  The weak composition ν is also called the weight (π) of 
π∈𝒪𝒫_ν,k. Let

    𝒪𝒫_n,k  =  ⋃_ν n𝒪𝒫_ν,k.

It should be noted that in the literature 𝒪𝒫_n,k is sometimes used for ordered set partitions rather
than ordered multiset partitions (that is, without letter multiplicities).

We now specify a particular reading order for an ordered multiset partition π = (π_1|π_2 |…|π_k)  
∈𝒪𝒫_n,k with blocks π_i. Start by writing π_k in increasing order. Assume π_i+1 has been ordered, 
and  let r_i be the largest integer in π_i that is less than or equal to the leftmost element of π_i+1.   If no such r_i 
exists, arrange π_i in increasing order.  When such an r_i exists, arrange the elements of π_i in increasing order, 
and then cycle them so that r_i is the rightmost number. Continue with π_i-1, …, π_2, π_1 until all blocks have 
been ordered. This ordering of the numbers in π is defined in <cit.> and is called the minimaj order.  



lf π = (157 | 24 | 56 | 468 | 13 | 123) ∈𝒪𝒫_15,6,  then the minimaj order of π is  
π = (571 | 24 | 56 | 468 | 31 | 123).


For two sequences α,β of integers,  we write α < β to mean that each element of α is less
than every element of β.  Suppose π∈𝒪𝒫_n,k is in minimaj order. Then each block π_i of π 
is nonempty and 
can be written in the form π_i = b_i α_i β_i, where b_i ∈_>0, and α_i,β_i are sequences 
(possibly empty) of distinct increasing integers such that either β_i < b_i  < α_i or α_i=∅. 
Inequalities with empty sets should be ignored. 



With the above notation, π∈𝒪𝒫_n,k is in minimaj order if the following hold:


  (1)   π_k = b_kα_k with b_k<α_k and β_k = ∅;

  (2)    for 1 ⩽ i < k,    either
 
  (a)  α_i = ∅,  π_i = b_i β_i,  and  
b_i < β_i ⩽ b_i+1,    or
 
  (b)    β_i ⩽ b_i+1 < b_i < α_i.  
 
 

 
A sequence or word w_1 w_2 ⋯ w_n has a descent in position 1⩽ i<n if w_i>w_i+1.
Let π∈𝒪𝒫_n,k be in minimaj order. Observe that a descent occurs in π_i only in Case 2 (b)
of Lemma <ref>, and such a descent is either between the largest and smallest elements of π_i
or between the last element of π_i and the first element of π_i+1.   
 

Continuing Example <ref> with π = (571 | 24 | 56 | 468 | 31 | 123), we have

    [      b_1 = 5, α_1 =7, β_1 = 1      b_2 = 2, α_2 = ∅, β_2 =4      b_3 = 5, α_3 = 6, β_3 =∅;  b_4 = 4,  α_4 = 68, β_4 =  ∅    b_5 = 3,  α_5 = ∅, β_5 = 1 b_6 = 1,  α_6 = 23,  β_6 = ∅. ]


 
Suppose that π in minimaj order has descents in positions

    (π) = {d_1, d_1+d_2, …, d_1+d_2 + ⋯ + d_ℓ}

for some ℓ∈ [0,k-1]  (ℓ= 0 indicates no descents). Furthermore assume that these descents occur in the blocks  
π_i_1, π_i_1+i_2, …,π_i_1+i_2+⋯ + i_ℓ, where  i_j >0 for 1⩽ j ⩽ℓ and 
i_1+i_2+⋯+i_ℓ <k.  Assume d_ℓ+1 and i_ℓ+1 are the distances to the end, that is,  
d_1+d_2 + ⋯+d_ℓ + d_ℓ+1 = n and i_1+i_2+⋯+ i_ℓ + i_ℓ+1 = k.  

The minimaj statistic (π) of π∈𝒪𝒫_n,k as given by <cit.> is

    (π) = ∑_d ∈(π) d  =  ∑_j=1^ℓ (ℓ+1-j) d_j.



The descents for the multiset partition  π = (57.1 | 24 | 56. | 468. | 3.1 | 123)  occur at positions 
(π)={2,7,10,11} and are designated with periods. Hence ℓ=4, d_1 = 2, d_2 = 5, d_3 = 3, d_4 = 1 
and d_5 = 4, and  (π) = 2 + 7 + 10 + 11 = 30.  The descents occur in blocks   π_1, π_3, π_4, and
π_5,  so that i_1 = 1, i_2 = 2, i_3 = 1, i_4 = 1, and i_5 = 1.  


To define the major index of π∈𝒪𝒫_n,k, we consider the word w obtained by ordering each 
block π_i in decreasing order, called the major index order <cit.>.
Recursively construct a word v by setting v_0=0 and v_j = v_j-1+ χ(j  is the last position in its block)
for each 1⩽ j ⩽ n. Here χ(True)=1 and χ(False)=0. Then

    (π) = ∑_j  w_j>w_j+1 v_j.



Continuing Example <ref>, note that the major index order of π = (157 | 24 | 56 | 468 | 13 
| 123) ∈𝒪𝒫_15,6 is π = (751 | 42 | 65 | 864 | 31 | 321). Writing the word v 
underneath w (omitting v_0=0), we obtain

    w    = 751 | 42 | 65 | 864| 31 | 321
    
    	v    = 001 | 12 | 23 | 334 | 45 | 556,

so that (π) = 0+0+1+2+3+3+4+4+5+5=27.


Note that throughout this section, we could have also restricted ourselves to ordered multiset partitions with 
letters in {1,2,…, r} instead of _>0. That is, let ν=(ν_1,…,ν_r) be a weak composition of n and let
𝒪𝒫^(r)_ν,k be the set of partitions of the multiset {i^ν_i| 1⩽ i ⩽ r} into
k nonempty ordered blocks, such that the elements within each block are distinct.  Let

    𝒪𝒫^(r)_n,k  =  ⋃_ν n𝒪𝒫^(r)_ν,k.

This restriction will be important when we discuss the crystal structure on ordered multiset partitions.




§ BIJECTION WITH TUPLES OF SEMISTANDARD YOUNG TABLEAUX




In this section, we describe a bijection from ordered multiset partitions to tuples of semistandard Young tableaux
that allows us to impose a crystal structure on the set of ordered multiset partitions in Section <ref>.

Recall that a semistandard Young tableau T is a filling of a (skew) Young diagram (also called the shape of T)
with positive integers that weakly increase across rows and strictly increase down columns. The weight of T is 
the tuple (T)=(a_1,a_2,…), where a_i records the number of letters i in T. The set of semistandard Young 
tableaux of shape λ, where λ is a (skew) partition, is denoted by 𝖲𝖲𝖸𝖳(λ). If we want to 
restrict the entries in the semistandard Young tableau from _>0 to a finite alphabet {1,2,…,r}, we denote the set by 𝖲𝖲𝖸𝖳^(r)(λ).  

The tableaux relevant for us here are of two types: a single column of boxes with entries that increase from top to bottom,  
or a skew ribbon tableau.  If γ =(γ_1,γ_2, …, γ_m) is a skew ribbon shape with 
γ_j boxes in the j-th row starting from the bottom, the ribbon condition requires that row j+1 starts in the 
last column of row j. This condition is equivalent to saying that γ is connected and contains no 2 × 2 
block of squares.  For example
boxsize=1.1em

    ,,

corresponds to γ = (2,1,3).
Let 𝖲𝖲𝖸𝖳(1^c) be the set of semistandard Young tableaux obtained by filling a column of 
length c and 𝖲𝖲𝖸𝖳(γ) be the set of semistandard Young tableaux obtained by filling the skew ribbon
shape γ.

To state our bijection, we need the following notation. For fixed positive integers n and k, assume 
D= {d_1,d_1+d_2,…,d_1+d_2+⋯+d_ℓ}⊆{1,2,…,n-1} and 
I = {i_1,i_1+i_2,…,i_1+i_2+⋯+i_ℓ}⊆{1,2,…, k-1} are sets of ℓ distinct elements 
each. Define d_ℓ+1 := n-(d_1+⋯ +d_ℓ) and i_ℓ+1 := k - (i_1+⋯ +i_ℓ).


  
For fixed positive integers n and k and sets D and I as above, let

    M(D,I) = {π∈𝒪𝒫_n,k|(π) = D,  and the descents occur in π_i for i ∈I}.

Then the following map is a weight-preserving bijection:

    φM(D,I)   →𝖲𝖲𝖸𝖳(1^c_1) ×⋯×𝖲𝖲𝖸𝖳(1^c_ℓ) ×𝖲𝖲𝖸𝖳(γ)
    π   ↦ T_1 ×⋯× T_ℓ× T_ℓ+1

where
  

  (i)  γ = (1^d_1-i_1, i_1, i_2, …, i_ℓ+1) and c_j = d_ℓ+2-j - i_ℓ+2-j for 
1⩽ j ⩽ℓ.

  (ii)  The skew ribbon tableau T_ℓ+1 of shape γ is constructed as follows:
  

  ∙ The entries in the first column of the skew ribbon tableau T_ℓ+1 beneath the first box are the first 
d_1-i_1 elements of π in increasing order from top to bottom, excluding any b_j in that range.

  ∙ The remaining rows d_1-i_1+j of T_ℓ+1 for 1⩽ j ⩽ℓ+1 are filled withb_i_1+… + i_j-1 + 1, b_i_1+… + i_j-1 + 2, …, b_i_1+… + i_j.
 

  (iii) The tableau T_j for 1⩽ j ⩽ℓ is the column filled with the elements of π from the positions 
d_1+d_2+⋯ + d_ℓ-j+1+1 through and including position d_1+d_2+⋯ + d_ℓ-j+2, but excluding any 
b_i in that range.

 

 Note that in item (ii), the rows of γ are assumed to be numbered from bottom 
 to top and are filled starting with row  d_1-i_1+1 and ending with row d_1-i_1+ℓ+1
at the top.
  
Also observe that since the bijection stated in Proposition <ref> preserves the weight, it can be restricted to a 
bijection
 
    φM(D,I)^(r)→𝖲𝖲𝖸𝖳^(r)(1^c_1) ×⋯×𝖲𝖲𝖸𝖳^(r)(1^c_ℓ) ×𝖲𝖲𝖸𝖳^(r)(γ),

where M(D,I)^(r) = M(D,I)∩𝒪𝒫^(r)_n,k.

Before giving the proof, it is helpful to consider two examples to illustrate the map φ.  
 
  
 When the entries of π∈𝒪𝒫_n,k in minimaj order are increasing, then ℓ = 0.   
 In this case, d_1 = n and i_1 = k.   The mapping φ takes π to the semistandard tableau T =T_1 
 that is of ribbon-shape γ = (1^n-k,k). The  entries of the boxes in the first column of the tableau T are  
 b_1, followed by the n-k numbers in the sequences β_1,β_2,…, β_k-1,α_k
from top to bottom. (The fact that π has no descents means that all the α_i = ∅ for 1⩽ i <k
and we are in Case 2 (a) of Lemma <ref> for 1⩽ i<k and Case 1 for i=k.)  Columns 2 
through k of T_1 are filled with the numbers b_2,…,b_k respectively, and b_2 ⩽ b_3 ⩽⋯⩽ b_k.  The result is a semistandard tableau T_1 of hook shape. 

For example, consider π = (12 | 2 | 234) ∈𝒪𝒫_6,3. Then γ=(1^3,3) and

    T_1 = 122,2,3,4 .


Now suppose that T is such a hook-shape tableau with entries b_1,b_2,…,b_k from left to right in its top row, 
and entries b_1, t_1, …, t_n-k down its first column. The inverse φ^-1  maps T to the set partition π 
that has as its first block π_1= b_1β_1, where β_1=t_1, …, t_m_1, and t_1 < … < t_m_1⩽ b_2,
but t_m_1+1 > b_2 so that β_1 is in the interval (b_1,b_2]. The second block of π is given by 
π_2 = b_2 β_2, where β_2 = t_m_1+1,…,t_m_2, and t_m_1+1< t_m_1+2< … <t_m_2⩽
b_3,  but t_m_2+1 > b_3 and β_2  ⊆ (b_2,b_3].  
Continuing in this fashion, we set π_k = b_k α_k, where α_k = t_m_k-1+1,…, t_n-k and
α_k ⊆ (b_k,+∞).   Then  φ^-1(T) = π = (π_1|π_2 |⋯|π_k),
where the ordered multiset partition π has no descents.  
 
 


The ordered multiset partition π = (124 | 45. | 3 | 46.1| 23.1| 1 | 25) ∈𝒪𝒫_15,7 
has the following data:
 
    [   b_1 = 1,  α_1 =∅, β_1 = 24     b_2 = 4,α_2 = 5,
    	β_2 =∅     b_3 = 3, α_3 = ∅, β_3 =∅;   b_4 = 4, α_4 = 6, β_4 =  1   b_5 = 2, α_5 = 3,  β_5 = 1 b_6 = 1,
     	α_6 = ∅,  β_6 = ∅;      b_7=2, α_7 = 5, β_7 = ∅                             ;                              ]

and ℓ=3, d_1=5, d_2=d_3=3, d_4=4 and i_1=i_2=2, i_3=1, i_4=2. Then 
boxsize=1.1em

    π = (124|45. |3|46.1|23.1|1|25) ↦1,5×1,3×6×12,2,34,14,2,4,5 .



It is helpful to keep the following picture in mind during the proof of Proposition <ref>, where the map φ 
is taking the ordered multiset partition π to the collection of tableaux T_i  as illustrated below. We adopt the shorthand 
notation η_j :=  i_1+⋯+i_j for 1⩽ j ⩽ℓ, where we also set η_0=0 and η_ℓ+1=k:

    π = (b_1 β_1 | b_2 β_2 | ⋯ |b_η_1α_η_1. β_η_1|b_η_1+1β_η_1+1 
    	|⋯  |b_η_jα_η_j.β_η_j| b_η_j+1β_η_j+1 | ⋯ | b_k α_k)

boxsize=2.9em

    T_ℓ+1-j = β_η_j,β_η_j+1,⋮,β_η_j+1-1,α_η_j+1  for 1⩽ j⩽ℓ,   
    	T_ℓ+1 =  b_η_ℓ+1⋯b_η_ℓ+1,
    	⋮,
    	b_η_j-1+1⋯b_η_j, ⋮,b_1⋯b_η_1,β_1,⋮,β_η_1-1,α_η_1 .



Since the entries of π are mapped bijectively to the entries of T_1 × T_2 ×⋯× T_ℓ+1,  
the map φ preserves the total weight (π)=(p_1,p_2,…) ↦ (T), where p_i is the number of 
entries i in π for i ∈ℤ_>0. We need to show that φ is well defined and 
exhibit its inverse. For this, we can assume that ℓ⩾ 1, as the case ℓ = 0 was treated in
Example <ref>. 

Observe first that there are d_j entries in π which are between two consecutive descents, 
and among these entries there are exactly i_j entries that are first elements of a block, since descents happen i_j
blocks apart. This implies that the tableaux have the shapes claimed. 

To see that the tableaux are semistandard, consider first  T_ℓ+1, and let η_j = i_1+⋯+i_j as above. 
A row numbered d_1-i_1+j for 1 ⩽ j ⩽ℓ+1 is weakly increasing, because the lack of a descent in 
a block π_i means b_i ⩽ b_i+1, and this holds for i in the interval  η_j-1 +1, …, η_j between 
two consecutive descents.  The leftmost column is strictly increasing because it consists of the elements b_1 < β_1 
< β_2 < ⋯ <β_η_1-1 <α_η_1 (the lack of a descent before π_η_1 implies that 
α_i=∅ for i<η_1 and b_i <β_i ⩽ b_i+1< β_i+1 by  Case 2 (a)
of Lemma <ref>).

The rest of the columns of T_ℓ+1 contain elements b_i, where b_η_j-1+1 is the first element in row 
d_1-i_1+j and b_η_j is the last, and b_η_j+1 is the first element in the row immediately above it.  We have 
b_η_j > b_η_j+1,  since there is a descent in block π_i_j which implies this inequality by the ordering 
condition in Case 2 (b) of Lemma <ref>.

The strict inequalities for the column tableaux T_1,…,T_ℓ hold for the same reason that they hold for the first 
column in T_ℓ+1. That is,  the columns consist of the elements β_η_j < β_η_j+1 <⋯ <
β_η_j+1-1 <α_η_j+1, where all the α_i for η_j⩽ i<η_j+1 are in fact 
∅, since we are in Case 2 (a) of Lemma <ref> here. 

Next, to show that φ is a bijection, we describe the inverse map of φ.
For D = {d_1,d_1+d_2, …, d_1+d_2+⋯+d_ℓ}⊆{1,2,…,n-1} and I
= {i_1,i_1+i_2,…,i_1+i_2+⋯+i_ℓ} = {η_1,η_2,…,η_ℓ}⊆{1,2,…,k-1} with ℓ distinct
elements each, suppose d_ℓ+1 and i_ℓ+1 are such that d_1+d_2+⋯+d_ℓ+1 = n and 
η_ℓ+1=i_1+i_2+⋯+i_ℓ+1=k.  Assume
T_1 ×⋯× T_ℓ× T_ℓ+1∈𝖲𝖲𝖸𝖳(1^c_1) ×⋯×𝖲𝖲𝖸𝖳(1^c_ℓ) 
×𝖲𝖲𝖸𝖳(γ), where γ = (1^d_1-i_1,i_2,…,i_ℓ+1) and c_j = d_ℓ+2-j - i_ℓ+2-j 
for 1⩽ j ⩽ℓ. We construct π by applying the following algorithm.

Read off the bottom d_1-i_1 entries of the first column of T_ℓ+1. Let b_1 be the element immediately above 
these entries in the first column of T_ℓ+1, and note that b_1 is less than all of them. Let b_2,…, b_i_1 be the 
elements in the same row of T_ℓ+1 as b_1, reading from left to right.  Assign  b_η_1+1,…, b_η_2 to the 
elements in the next higher row, and so forth, until reaching row d_1-i_1+ℓ+1 (the top row) of T_ℓ+1 
and assigning b_η_ℓ+1,…, b_η_ℓ+1=b_k to its entries.
The elements in β_1,…,β_η_1-1,α_η_1 are obtained by cutting the entries in 
the first column of T_ℓ+1 above b_1, so that β_i lies in the interval (b_i, b_i+1], and  α_η_1 
lies in the interval  (b_η_1,∞).

Now for 1⩽ j⩽ℓ, we obtain β_η_j,β_η_j+1,…,β_η_j+1-1,α_η_j+1 by 
cutting the elements in T_ℓ+1-j into sequences as follows: β_η_j = T_ℓ+1-j∩ ( -∞, b_η_j+1 ], 
β_η_j+m = T_ℓ+1-j∩ (b_η_j+m+1, b_η_j+m+2] and α_η_j+1 = T_ℓ+1-j∩ 
(b_η_j+1,+∞). 

The inequalities are naturally forced from the inequalities in the semistandard tableaux, and the descents at the 
given positions are also forced,  because by construction α_η_j > b_η_j > b_η_j+1⩾β_η_j. 
This process constructs the b_i, α_i, and β_i for each i=1,…,k, where we assume that sequences that 
have not been defined by the process are empty.    Then φ^-1(T_1 × T_2 ×⋯× T_ℓ+1)
= π = (π_1 |π_2 |⋯|π_k), where π_i = b_i α_i β_i.  

 
For a (skew) partition λ, the Schur function 𝗌_λ(𝐱) is defined as

    𝗌_λ(𝐱) = ∑_T ∈𝖲𝖲𝖸𝖳(λ)𝐱^(T).

Similarly for m ⩾ 1, the m-th elementary symmetric function 𝖾_m(𝐱) is given by

    𝖾_m(𝐱) = ∑_1 ⩽ j_1 < j_2 < ⋯ < j_m x_j_1 x_j_2⋯ x_j_m.

As an immediate consequence of Proposition <ref>, we have the following symmetric function identity.
 

   
Assume D⊆{1,2,…,n-1} and I⊆{1,2,…, k-1} are sets of ℓ 
distinct elements each and let M(D,I), γ and c_j for 1⩽ j ⩽ℓ be as in 
Proposition <ref>. Then 

    ∑_π∈M(D,I)𝐱^(π) 
    	= 𝗌_γ(𝐱)  ∏_j=1^ℓ𝖾_c_j(𝐱).






§ CRYSTAL ON ORDERED MULTISET PARTITIONS







 §.§ Crystal structure


Denote the set of words of length n over the alphabet {1,2,…,r} by 𝒲^(r)_n.
The set 𝒲_n^(r) can be endowed with an 𝔰𝔩_r-crystal structure as follows.
The weight (w) of w∈𝒲_n^(r) is the tuple (a_1,…,a_r), where a_i is the number
of letters i in w. The Kashiwara raising and lowering operators

    e_i, f_i 𝒲_n^(r)→𝒲_n^(r)∪{0}        for 1⩽ i <r

are defined as follows. Associate to each letter i in w an open bracket “)” and to each letter i+1 in w
a closed bracket “(”. Then e_i changes the i+1 associated to the leftmost unmatched “(” to an i; if there 
is no such letter, e_i(w)=0. Similarly, f_i changes the i associated to the rightmost unmatched “)” to an i+1;
if there is no such letter, f_i(w)=0.

For λ a (skew) partition, the 𝔰𝔩_r-crystal action on 𝖲𝖲𝖸𝖳^(r)(λ) is induced
by the crystal on 𝒲_|λ|^(r), where |λ| is the number of boxes in λ. Consider the 
row-reading word 𝗋𝗈𝗐(T) of T∈𝖲𝖲𝖸𝖳^(r)(λ), which is the word obtained from T by 
reading the rows from bottom to top, left to right. Then f_i(T) (resp. e_i(T)) is the RSK insertion tableau of
f_i(𝗋𝗈𝗐(T)) (resp. e_i(𝗋𝗈𝗐(T))). It is well known that f_i(T) is a tableau in
𝖲𝖲𝖸𝖳^(r)(λ) with weight  equal to (T)-ϵ_i+ϵ_i+1, where ϵ_i is i-th 
standard vector in ^r.
Similarly, e_i(T) ∈𝖲𝖲𝖸𝖳^(r)(λ), and e_i(T) has weight (T)+ϵ_i-ϵ_i+1. See for 
example <cit.>.

In the same spirit, an 𝔰𝔩_r-crystal structure can be imposed on 

    𝖲𝖲𝖸𝖳^(r)(1^c_1,…,1^c_ℓ,γ)
    	:= 𝖲𝖲𝖸𝖳^(r)(1^c_1) ×⋯×𝖲𝖲𝖸𝖳^(r)(1^c_ℓ) ×𝖲𝖲𝖸𝖳^(r)(γ)

by concatenating the reading words of the tableaux in the tuple. This yields crystal operators

    e_i,f_i 𝖲𝖲𝖸𝖳^(r)(1^c_1,…,1^c_ℓ,γ) →𝖲𝖲𝖸𝖳^(r)(1^c_1,…,1^c_ℓ,γ) ∪{0}.

Via the bijection φ of Proposition <ref>, this also imposes crystal operators on ordered
multiset partitions

    ẽ_i,f̃_i 𝒪𝒫_n,k^(r)→𝒪𝒫_n,k^(r)∪{0}

as ẽ_i = φ^-1∘ e_i ∘φ and f̃_i = φ^-1∘ f_i ∘φ.

An example of a crystal structure on 𝒪𝒫_n,k^(r) is given in Figure <ref>.





The operators ẽ_i, f̃_i, and  impose an 𝔰𝔩_r-crystal structure on
𝒪𝒫_n,k^(r). In addition, ẽ_i and f̃_i preserve the  statistic.



The operators ẽ_i, f̃_i, and  impose an 𝔰𝔩_r-crystal structure by construction
since φ is a weight-preserving bijection. The Kashiwara operators ẽ_i and f̃_i preserve
the  statistic, since by Proposition <ref>, the bijection φ restricts to M(D,I)^(r) 
which fixes the descents of the ordered multiset partitions in minimaj order.





 §.§ Explicit crystal operators


Let us now write down the crystal operator f̃_i 𝒪𝒫_n,k→𝒪𝒫_n,k 
of Theorem <ref> explicitly on π∈𝒪𝒫_n,k in minimaj order.

Start by creating a word w from right to left by reading the first element in each block of π from right to left, 
followed by the remaining elements of π from left to right. Note that this agrees with 𝗋𝗈𝗐(φ(π)).
For example, w=513165421434212 for π in Example <ref>.
Use the crystal operator f_i on words to determine 
which i in w to change to an i+1. Circle the corresponding letter i in π. The crystal operator f̃_i 
on π changes the circled i to i+1 unless we are in one of the following two cases:



    ⋯i| i      f̃_i⟶  ⋯| i  i+1 , 
    |i  i+1      f̃_i⟶   i+1 |i+1 .


Here “⋯” indicates that the block is not empty in this region.


In Figure <ref>, f̃_2(31 2| 2) = (31 | 2  3) is an example
of (<ref>). Similarly, f̃_1(31 |1 2) = (312 |2) is an example
of (<ref>).



The above explicit description for f̃_i is well defined and agrees with the definition of
Theorem <ref>.



The word w described above is precisely 𝗋𝗈𝗐(φ(π)) on which f_i acts.
Hence the circled letter i is indeed the letter changed to i+1. It remains to check how φ^-1
changes the blocks. We will demonstrate this for the cases in (<ref>) as the other cases are similar.

In case (<ref>) the circled letter i in block π_j does not correspond to b_j in π_j as it is not at
the beginning of its block. Hence, it belongs to α_j or β_j. The circled letter is not a descent.
Changing it to i+1 would create a descent. The map φ^-1 distributes the letters in α_j
and β_j to preserve descents, hence the circled i moves over to the next block on the right and becomes a 
circled i+1. Note also that i+1 ∉π_j+1, since otherwise the circled i would have been bracketed in w, 
contradicting the fact that f_i is acting on it.

In case (<ref>) the circled letter i in block π_j corresponds to b_j in π_j. Again,
φ^-1 now associates the i+1 ∈π_j to the previous block after applying f_i. Note that 
i+1 ∉π_j-1 since it would necessarily be b_j-1. But then the circled i would have been bracketed
in w, contradicting the fact that f_i is acting on it.






 §.§ Schur expansion


The character of an 𝔰𝔩_r-crystal B is defined as

    ch B = ∑_b∈ B𝐱^(b).

Denote by B(λ) the 𝔰𝔩_∞-crystal on 𝖲𝖲𝖸𝖳(λ) defined above.
This is a connected highest weight crystal with highest weight λ, and the character is the Schur 
function 𝗌_λ(𝐱) defined in (<ref>)

    chB(λ) = 𝗌_λ(𝐱).

Similarly, denoting by B^(r)(λ) the 𝔰𝔩_r-crystal on 𝖲𝖲𝖸𝖳^(r)(λ),
its character is the Schur polynomial

    chB^(r)(λ) = 𝗌_λ(x_1,…,x_r).

Let us define

    𝖵𝖺𝗅^(r)_n,k(𝐱;0,t) = ∑_π∈𝒪𝒫^(r)_n,k+1  t^(π)𝐱^(π),

which satisfies 𝖵𝖺𝗅_n,k(𝐱;0,t) = 𝖵𝖺𝗅_n,k^(r)(𝐱;0,t) for r⩾ n,
where 𝖵𝖺𝗅_n,k(𝐱;0,t) is as in (<ref>).

As a consequence of Theorem <ref>, we now obtain the Schur expansion of 
𝖵𝖺𝗅_n,k^(r)(𝐱;0,t).


We have

    𝖵𝖺𝗅_n,k-1^(r)(𝐱;0,t) 
    	= ∑_π∈𝒪𝒫^(r)_n,k
    ẽ_i(π) = 0   ∀ 1⩽ i <r t^(π)𝗌_(π).


When r⩾ n, then by <cit.> and <cit.> this is also equal to

    𝖵𝖺𝗅_n,k-1(𝐱;0,t) = ∑_λ⊢ n  ∑_T ∈𝖲𝖸𝖳(λ)
    	t^(T) + n-k2 -(n-k) 𝖽𝖾𝗌(T)[ [ 𝖽𝖾𝗌(T);    n-k ]]
    	𝗌_λ(𝐱),

where 𝖲𝖸𝖳(λ) is the set of standard Young tableaux of shape λ (that is, the elements in
𝖲𝖲𝖸𝖳(λ) of weight (1^|λ|)), 𝖽𝖾𝗌(T) is the number of descents of T,
(T) is the major index of T (or the sum of descents of T), and the t-binomial coefficients in the sum
are defined using the rule

    [ [ m; p ]] = [m]!/[p]! [m-p]!  where [p]! = [p][p-1] ⋯ [2][1]
    	and  [p] = 1 + t + ⋯ + t^p-1.



The crystal 𝒪𝒫_4,2^(3), displayed in Figure <ref>, has four highest weight elements
with weights (2,1,1), (2,1,1), (2,1,1), (2,2) from left to right. Hence, we obtain the Schur expansion

    𝖵𝖺𝗅^(3)_4,1(𝐱;0,t) = (1+t+t^2) 𝗌_(2,1,1)(𝐱) + t  𝗌_(2,2)(𝐱).







§ EQUIDISTRIBUTIVITY OF THE MINIMAJ AND MAJ STATISTICS




In this section, we describe a bijection ψ_n,k→_n,k in Theorem <ref>
with the property that (π) = (ψ(π)) for π∈_n,k. This proves the link between
 and  that was missing in <cit.>.
We can interpret ψ as a crystal isomorphism, where _n,k on the left is the  crystal of
Section <ref> and _n,k on the right is viewed as a crystal of k columns with elements
written in major index order.

The bijection ψ is the composition of φ of Proposition <ref> with a certain shift operator.
When applying φ to π∈_n,k, we obtain the tuple T^∙=T_1 ×⋯× T_ℓ+1 
in (<ref>).
We would like to view each column in the tuple of tableaux as a block of a new ordered multiset partition. However, note
that some columns could be empty, namely if c_j=d_ℓ+2-j-i_ℓ+2-j in Proposition <ref> is zero for some 
1⩽ j ⩽ℓ. For this reason, let us introduce the set of weak ordered multiset partitions 
𝒲𝒪𝒫_n,k, where we relax the condition that all blocks need to be nonempty sets.

Let T^∙ = T_1 ×⋯× T_ℓ+1 be a tuple of skew tableaux. Define (T^∙) to be the 
weak ordered multiset partition whose blocks are obtained from T^∙ by reading the columns from the 
left to the right and from the bottom to the top; each column constitutes one of the blocks in (T^∙).
Note that given π= (π_1 | π_2| ⋯ | π_k) ∈_n,k in minimaj order, (φ(π)) is a weak
ordered multiset partition in major index order.

 

Let π = (1| 56.| 4.| 37.12| 2.1| 1| 34) ∈_13,7, written in minimaj order. 
We have (π)=22. Then 
boxsize=1.1em

    T^∙ = φ(π) =  
    	1,4×1,2×7×∅× 13, 2, 3, 4,15,6

and π'=(T^∙) = (4.1| 2.1| 7.|∅| 6.1| 5.4.3.2.1 | 3).




Let ℐ={(φ(π)) |π∈_n,k}⊆𝒲𝒪𝒫_n,k,
π' = (φ(π)) ∈ℐ, and b_i the first elements in each block of π in minimaj order as
in Lemma <ref>. Then π' has the following properties:  


  * The last k elements of π' are b_1,…,b_k, and b_i and b_i+1 are in different blocks if and only 
if b_i ⩽ b_i+1.

  * If b_1,…,b_k are contained in precisely k-j blocks, then there are at least j descents in the blocks 
containing the b_i's. 




Let π∈_n,k, written in minimaj order. Then by (<ref>), 
π'=(φ(π)) is of the form

    π'=
    	(α^rev_η_ℓ+1β^rev_η_ℓ+1-1⋯β^rev_η_ℓ|
    	⋯|
    	α^rev_η_1β^rev_η_1-1⋯β^rev_1b_1 ⋯|⋯| 
    	b_η_1b_η_1-1⋯|⋯|⋯ b_k),

where the superscript rev indicates that the elements are listed in decreasing order (rather than increasing order).
Since the rows of a semistandard tableau are weakly increasing and the columns are strictly increasing, the blocks 
of π'=(φ(π)) are empty or in strictly decreasing order. This implies that b_i and b_i+1 are in different 
blocks of π' precisely when b_i⩽ b_i+1, so a block of π' that contains a b_i cannot have a descent 
at its end. This proves (1).

In a weak ordered multiset partition written in major index order, any block of size r⩾ 2 has r-1 descents. 
So if b_1,…, b_k are contained in precisely k-j blocks, then at least j of these elements are contained in blocks 
of size at least two, so there are at least j descents in the blocks containing the b_i's. This proves (2).



Let π'∈𝒲𝒪𝒫_n,k be in major index order such that 
there are at least k elements after the rightmost occurrence of a block that is either empty or has a descent at its end.  
In this case, there exists a skew tableau T^∙ such that π'=(T^∙). In fact, this characterizes 
ℐ := im (∘φ).




The map  is invertible.



Suppose π' ∈𝒲𝒪𝒫_n,k is in major index order such that there are at least k elements after the 
rightmost occurrence of a block that is either empty or has a descent at its end. Since there are no occurrences of an 
empty block or a descent at the end of a block amongst the last k elements of π', the blocks of π' containing 
the last k elements form the columns of a skew ribbon tableau T∈𝖲𝖲𝖸𝖳(γ), and the remaining blocks 
of π' form the column tableaux to the left of the skew ribbon tableau, so  is invertible.


We are now ready to introduce the shift operators.



We define the left shift operation Ł on π'∈ℐ = {(φ(π)) |π∈𝒪𝒫_n,k} 
as follows. Suppose π' has m ⩾ 0 blocks π_p_m',…, π_p_1' that are either empty or have 
a descent at the end, and 1 ⩽ p_m < ⋯ <  p_2 < p_1<k. Set

    Ł(π') = Ł^(m)(π'),

where Ł^(i) for 0⩽ i⩽ m are defined as follows:


  * Set Ł^(0)(π')=π'.

  * Suppose Ł^(i-1)(π') for 1⩽ i ⩽ m is defined. By induction, the p_i-th block of Ł^(i-1)(π') is
π'_p_i. Let S_i be the sequence of elements starting immediately to the right of block π'_p_i in Ł^(i-1)(π') 
up to and including the p_i-th descent after the block π_p_i'. Let Ł^(i)(π') be the weak ordered multiset 
partition obtained by moving each element in S_i one block to its left. Note that all blocks with index smaller than
p_i in Ł^(i)(π') are the same as in π'.





Continuing Example <ref>, we have 
π'=(4.1| 2.1| 7.|∅|6.1|5.4.3
.2.1 | 3),
which is in major index order. We have m=2 with p_2=3<4=p_1, S_1=61543, 
S_2=6154 and

    Ł^(1)(π')    = (4.1| 2.1| 7. |6.1|5.4.3.| 2.1| 3),
    Ł(π') = Ł^(2)(π')    = (4.1| 2.1| 7.6.1 | 5.4.| 3.| 2.1| 3).

Note that (π')=28, (Ł^(1)(π'))=25, and (Ł(π')) = 22 = (π).




The left shift operation Łℐ→𝒪𝒫_n,k is well defined.



Suppose π'∈ℐ has m ⩾ 0 blocks π_p_1',…, π_p_m' that are either empty or have a 
descent at the end, and 1⩽ p_m < ⋯ < p_2 < p_1 < k.
If m=0, then Ł(π')=π' ∈𝒪𝒫_n,k and we are done.

We proceed by induction on m. Note that Ł^(1) acts on the rightmost block π_p_1'.  
Notice that π_p_1' cannot contain any of the b_i's by Lemma <ref> (1).
Hence, since there are at least k elements in the k-p_1 blocks following π_p_1', 
by Lemma <ref> (2), there are at least p_1 descents after π_p_1', so Ł^(1) can be applied 
to π'.

Observe that applying Ł^(1) to π' does not create any new empty blocks to the right of π_p_1', because 
creating a new empty block means that the last element of S_1, which is a descent, is at the end of a block. 
This cannot happen, since the rightmost occurrence of an empty block or a descent at the end of its block was assumed 
to be in π_p_1'.  However, note that applying Ł^(1) to π' does create a new block with a descent at its end, 
and this descent is given by the p_1-th descent after the block π_p_1' (which is the last element of S_1).

Now suppose Ł^(i-1)(π') is defined for i ⩾ 2. By induction, there are at least p_1>p_i descents following 
the block π_p_i', so the set S_i of Definition <ref> exists and we can move the elements in S_i
left one block to construct Ł^(i)(π') from Ł^(i-1)(π'). Furthermore, Ł^(i)(π') does not have any 
new empty blocks to the right of π_p_i'. To see this, note that the number of descents in S_i is p_i, so the 
number of descents in S_i is strictly decreasing as i increases. This implies that the i-1 newly created descents 
at the end of a block of Ł^(i-1)(π') occurs strictly to the right of S_i, and so the last element of S_i cannot 
be a descent at the end of a block of Ł^(i-1)(π').

Lastly, Ł(π') = Ł^(m)(π')∈_n,k, since it does not have any empty blocks, and every block of 
Ł(π') is in decreasing order because either we moved every element of a block into an empty block or we moved 
elements into a block with a descent at the end.




We define the right shift operation  on μ∈𝒪𝒫_n,k in major index order as follows.  
Suppose μ has m⩾ 0 blocks  μ_q_1, …, μ_q_m that have a descent at the end and 
q_1 < q_2 < ⋯ < q_m. Set

    (μ) = ^(m)(μ),

where ^(i) for 0⩽ i ⩽ m are defined as follows:


  * Set ^(0)(μ)=μ.

  * Suppose ^(i-1)(μ) for 1⩽ i ⩽ m is defined. Let U_i be the sequence of q_i elements 
to the left of, and including, the last element in the q_i-th block of ^(i-1)(μ).  Let ^(i)(μ) be the 
weak ordered multiset partition obtained by moving each element in U_i one block to its right.
Note that all blocks to the right of the (q_i+1)-th block are the same in μ and ^(i)(μ).



Note that  can potentially create empty blocks.


Continuing Example <ref>, let μ = Ł(π') = (4.1| 2.1| 7.6.1 | 5.4.| 3.| 2.1| 3).  
We have m=2 with q_1=4<5=q_2, U_1=6154, U_2=61543 and

    ^(1)(μ)    = (4.1| 2.1| 7. | 6.1 | 5.4.3.| 2.1| 3),
    (μ) = ^(2)(μ)    = (4.1| 2.1| 7. |∅| 6.1 | 5.4.3.2.1| 3),

which is the same as π' in Example <ref>.




The right shift operation  is well defined and is the inverse of Ł.



Suppose μ∈𝒪𝒫_n,k in major index order has descents at the end of the blocks 
μ_q_1,…, μ_q_m. If m=0, then (μ) = μ∈𝒪𝒫_n,k⊆𝒲𝒪𝒫_n,k 
and there is nothing to show.

We proceed by induction on m. The ordered multiset partition μ does not have empty blocks, so there are at 
least q_1 elements in the first q_1 blocks of μ, and ^(1) can be applied to μ.

Now suppose ^(i-1)(μ) is defined for i⩾2. By induction, there are at least q_i-1+1 elements in 
the first q_i-1+1 blocks of ^(i-1)(μ).  Since the blocks μ_q_i-1+2,…, μ_q_i in μ 
are all nonempty, there are at least q_i-1+1+(q_i-(q_i-1+1)) = q_i elements in the first q_i blocks of ^(i-1)(μ), 
so the set U_i of Definition <ref> exists and we can move the elements in U_i one block to the 
right to construct ^(i)(μ) from ^(i-1)(μ).  

Furthermore, every nonempty block of (μ) is in decreasing order because the rightmost element of each U_i is 
a descent. So (μ)∈𝒪𝒫_n,k remains in major index order. This completes the proof that 
is well defined.

Next we show that  is the inverse of Ł. Observe that if π' ∈ℐ has m occurrences of either an 
empty block or a block with a descent at its end, then μ=Ł(π') has m blocks with a descent at its end.  
Hence it suffices to show that ^(m+1-i) is the inverse operation to Ł^(i) for each 1⩽ i ⩽ m.

The property that the last element of S_i cannot be a descent at the end of a block of Ł^(i-1)(π') in the proof of
Proposition <ref> similarly holds for every element in S_i. Therefore, if the last element of S_i is in the 
r_i-th block of Ł^(i-1)(π'), then |S_i| = p_i + (r_i-1-p_i) = r_i-1 because the blocks are decreasing and none of the 
elements in S_i can be descents at the end of a block.
Since the last element of S_i becomes a descent at the end of the (r_i-1)-th block of Ł^(i)(π), this implies 
r_i-1 = q_m-i+1, so U_m-i+1 = S_i for every 1⩽ i ⩽ m. As the operation Ł^(i) is a left shift 
of the elements of S_i by one block and the operation ^(m+1-i) is a right shift of the same set of elements 
by one block, they are inverse operations of each other.


For what follows, we need to extend the definition of the major index to the set 𝒲𝒪𝒫_n,k of weak ordered 
multiset partitions of length n and k blocks, in which some of the blocks may be empty. Given 
π' ∈𝒲𝒪𝒫_n,k whose nonempty blocks are in major index order, if the block π_j'≠∅, then 
the last element in π_j' is assigned the index j, and the remaining elements in π_j' are assigned the index j-1
for j=1,…, k. Then (π') is the sum of the indices where a descent occurs. This agrees 
with (<ref>) in the case when all blocks are nonempty.



Let π'∈ℐ. With the same notation as in Definition <ref>,
we have for 1⩽ i ⩽ m

    (Ł^(i)(π')) = (Ł^(i-1)(π'))-p_i+1,    if π_p_i'=∅,
    (Ł^(i-1)(π'))-p_i,    if π_p_i' has a descent at the end of its block.



 
Assume π_p_i'=∅. In the transformation from Ł^(i-1)(π') to Ł^(i)(π'), the index of each of the first 
p_i-1 descents in S_i decreases by one, while the index of the last descent remains the same, since it is not at the 
end of a block in Ł^(i-1)(π'), but it becomes the last element of a block in Ł^(i)(π'). The indices of elements 
not in S_i remain the same, so (Ł^(i)(π'))=(Ł^(i-1)(π'))-p_i+1 in this case.

Next assume that π_p_i' has a descent at the end of the block. In the transformation from Ł^(i-1)(π') to Ł^(i)(π'), 
the indices of the descents in S_i change in the same way as in the previous case, but in addition, the index of the last 
descent in π_p_i' decreases by one, so (Ł^(i)(π'))=(Ł^(i-1)(π'))-p_i in this case.


 

Let ψ_n,k→_n,k be the map defined by

    ψ(π) = Ł((φ(π)))     for π∈_n,k in minimaj order.

Then ψ is a bijection that maps ordered multiset partitions in minimaj order to ordered multiset partitions in 
major index order. Furthermore, (π) = (ψ(π)).


 
By Proposition <ref>, φ is a bijection. By Lemma <ref>, the map  is invertible, and
by Proposition <ref> the shift operation Ł has an inverse. This implies that ψ is a bijection.

It remains to show that (π) = (ψ(π)) for π∈𝒪𝒫_n,k in minimaj order.

First suppose that π' = (φ(π)) has no empty blocks and no descents at the end of any block.
In this case Ł(π')=π', so that in fact π' = ψ(π). Using the definition of major index (<ref>) and 
the representation (<ref>) (where the columns in the ribbon are viewed as separate columns due 
to ), we obtain

    (π') = ∑_j=1^ℓ (ℓ+1-j) ( d_j - i_j -1) + ℓ + ∑_j=1^ℓ ( ℓ+η_j-j),

where d_j,i_j,η_j = i_1 + ⋯ + i_j are defined in Proposition <ref> for π.
Here, the first sum in the formula arises from the contributions of the first ℓ blocks and the summand ℓ 
compensates for the fact that b_1 is in the ℓ-th block. The second sum in the formula comes from the 
contributions of the b_i's. Comparing with (<ref>), we find

    (π') = (π) - ℓ+12 - ∑_j=1^ℓ (ℓ+1-j) i_j + ℓ+12 
    	+ ∑_j=1^ℓη_j = (π),

proving the claim.

Now suppose that π' = (φ(π)) has a descent at the end of block π'_p. This will contribute an extra
p compared to the major index in (<ref>). If π'_p=∅, then
c_p = d_ℓ+2-p - i_ℓ+2-p = 0 and the term j=ℓ+2-p in (<ref>) should be
(ℓ+1-j)(d_j-i_j) instead of (ℓ+1-j)(d_j-i_j-1) yielding a correction term of ℓ+1-j = ℓ+1-ℓ-2+p=p-1.
Hence, with the notation of Definition <ref>, we have

    (π') = (π) + ∑_i=1^m p_i - e,

where e is the number of empty blocks in π'. Since ψ(π) = Ł(π'), the claim follows by 
Lemma <ref>.



alpha


