%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Final Version: January 20, 1999 AMS-TeX version %%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \input amstex \magnification=\magstep1 \documentstyle{amsppt} \pagewidth{11.6cm}%11.66=14/12 \pageheight{19.1cm}%19.16=23/12 \define\qtri#1#2#3#4#5{\left[\matrix #1\\ #2,\,#3,\,#4\endmatrix \right]_{#5}} \define\qbin#1#2#3{\left[\matrix #1\\ #2\endmatrix \right]_{#3}} \documentstyle{amsppt} \NoBlackBoxes \nologo \topmatter \title Simultaneous maj statistics \endtitle \author{Dongsu Kim and Dennis Stanton} \endauthor \thanks The first author is partially supported by KOSEF: 971--0106--038--2. \endthanks \address Department of Mathematics, KAIST, Taejon 305--701, Korea \newline\indent School of Mathematics, University of Minnesota, Minneapolis, MN 55455 \endaddress \email dskim\@math.kaist.ac.kr stanton\@math.umn.edu \endemail \abstract{The generating function for words with several simultaneous $maj$ weights is given. New $maj$-like Mahonian statistics result. Some applications to integer partitions are given.} \endabstract \endtopmatter \document {\subheading{1. Introduction}} The usual $maj$ statistic \cite{2} on words $w$ is defined by adding the location of the descents of the word $w$, $$ maj(w)=\sum_{i: w_i>w_{i+1}} i. $$ This definition presumes that the alphabet for the letters of $w$ have been linearly ordered, for example $2>1>0$, $$ maj(1102201)=2+5=7=maj_{210}(1102201). $$ However a similar definition can be made assuming any linear ordering $\sigma$; here we take $1>2>0$, $\sigma=120$, and $2>0>1$, $\sigma=201$ $$ maj_{120}(1102201)=2+5=7, \quad maj_{201}(1102201)=5+6=11. $$ In this paper we consider the generating function for several such simultaneous $maj$ statistics (see Corollary 1). A more general generating function is given (Theorem 3), and some applications to Mahonian statistics (Corollary 2) and integer partitions (Theorem 4) are stated. We first give a 3 letter theorem, which motivates the general result (Theorem~3). Let $W(m,n,k)$ be the set of words of length $m+n+k$ with $m$~0's, $n$~1's and $k$~2's. \proclaim{Theorem 1} For any non-negative integers $m$, $n$, and $k$ we have $$ \align \sum_{w\in W(m,n,k)} &x^{maj_{120}(w)}y^{maj_{201}(w)}z^{maj_{012}(w)} =x^{n+k}y^k\qtri{m+n+k-1}{m-1}{n}{k}{xyz}+\\ & y^{k+m}z^m\qtri{m+n+k-1}{m}{n-1}{k}{xyz}+ z^{m+n}x^n\qtri{m+n+k-1}{m}{n}{k-1}{xyz}. \endalign $$ \endproclaim \demo{Proof} We prove a stronger statement, that the three terms in Theorem~1 are the generating functions for the words in $W(m,n,k)$ ending in 0, 1, and 2 respectively. We proceed by induction on $m+n+k$. If $w$ ends in a $0$, the penultimate letter must be either $0$, $1$ or $2$. Using induction we must verify that $$ \align x^{n+k}y^k&\qtri{m+n+k-1}{m-1}{n}{k}{xyz} =x^{n+k}y^k\qtri{m+n+k-2}{m-2}{n}{k}{xyz}+\\ &x^{m+n+k-1}y^{m+k-1}z^{m-1}\qtri{m+n+k-2}{m-1}{n-1}{k}{xyz}+\\ &(xy)^{m+n+k-1}z^{m+n-1}x^n\qtri{m+n+k-2}{m-1}{n}{k-1}{xyz}, \endalign $$ which is the well-known recurrence formula \cite{1} for the $xyz$-trinomial coefficient. The other two cases are verified similarly. \qed\enddemo It should be noted that if any two of $x,y,z$ are set equal to $1$, then the usual $maj$ generating function as a $q$-trinomial coefficient results. {\subheading{2. A 7-variable theorem}} Theorem 1 contains three free variables, $x,y$ and $z$. In this section we generalize Theorem 1 to Theorem 2, which contains seven free variables. Then we indicate how to specialize Theorem 2 to obtain new explicit classes of Mahonian statistics on words of $0$'s, $1$'s, and $2$'s. Suppose that the weights of the various possible ascents and descents in position $m+n+k-1$ of a word $w$ of $m$ 0's, $n$ 1's, and $k$ 2's are given by \roster \item"(wt10)" $a_0^{m-1}a_1^{n}a_2^k$ for a descent $10$, \item"(wt21)" $b_0^mb_1^{n-1}b_2^{k}$ for a descent $21$, \item"(wt20)" $c_0^{m-1}c_1^{n}c_2^k$ for a descent $20$, \item"(wt01)" $d_0^md_1^{n-1}d_2^{k}$ for an ascent $01$, \item"(wt12)" $e_0^{m}e_1^ne_2^{k-1}$ for an ascent $12$, \item"(wt02)" $f_0^{m}f_1^nf_2^{k-1}$ for an ascent $02$. \endroster Also suppose that the generating function for all such words $w$ has the form $$ \align p_0(n,k)\!\qtri{\!m+n+k-1\!}{m-1}{n}{k}{B}\!\!+ &p_1(k,m)\!\qtri{\!m+n+k-1\!}{m}{n-1}{k}{B}\!\!\\ &+p_2(m,n)\!\qtri{\!m+n+k-1\!}{m}{n}{k-1}{B} \tag2.1 \endalign $$ for some base $B$, and $p_0(n,k)=p_{01}^np_{02}^k$, $p_1(k,m)=p_{11}^kp_{12}^m$, $p_2(m,n)=p_{21}^mp_{22}^n$. We also assume that the three terms in (2.1) correspond to the $w$ which end in $0$, $1$, and $2$ respectively. Thus we have 25 free variables $$ \cup_{i=0}^2\{a_i,b_i,c_i,d_i,e_i,f_i,p_{i1},p_{i2}\}\cup\{B\}. $$ These 25 variables are related by the three equations which we require by induction $$ \align p_0(n,k)\qtri{m+n+k-1}{m-1}{n}{k}{B}=p_0(n,k)&\qtri{m+n+k-2}{m-2}{n}{k}{B}\\ +a_0^{m-1}a_1^{n}a_2^k\ p_1(k,m-1)&\qtri{m+n+k-2}{m-1}{n-1}{k}{B}\\ +c_0^{m-1}c_1^{n}c_2^k\ p_2(m-1,n)&\qtri{m+n+k-2}{m-1}{n}{k-1}{B}, \tag2.2a \endalign $$ $$ \align p_1(k,m)\qtri{m+n+k-1}{m}{n-1}{k}{B}=p_1(k,m)&\qtri{m+n+k-2}{m}{n-2}{k}{B}\\ +b_0^{m}b_1^{n-1}b_2^k\ p_2(m,n-1)&\qtri{m+n+k-2}{m}{n-1}{k-1}{B} \\ +d_0^{m}d_1^{n-1}d_2^k\ p_0(n-1,k)&\qtri{m+n+k-2}{m-1}{n-1}{k}{B}, \tag2.2b \endalign $$ $$ \align p_2(m,n)\qtri{m+n+k-1}{m}{n}{k-1}{B}=p_2(m,n)&\qtri{m+n+k-2}{m}{n}{k-2}{B}\\ +f_0^{m}f_1^{n}f_2^{k-1}\ p_0(n,k-1)&\qtri{m+n+k-2}{m-1}{n}{k-1}{B}\\ +e_0^{m}e_1^{n}e_2^{k-1}\ p_1(k-1,m)&\qtri{m+n+k-2}{m}{n-1}{k-1}{B}. \tag2.2c \endalign $$ We do not know the general solution to the equations (2.2a-c). However, we will give the general solution to (2.2a-c) if we make another assumption. If we specify that the coefficient of the second term on the the right side of (2.2a) is $B^{m-1}$ times the coefficient of the first term, and the coefficient of the third term is $B^{m+n-1}$ times the coefficient of the first term, then the $B$-trinomial recurrence relation verifies (2.2a). These two equations are $$ \aligned a_0^{m-1}a_1^na_2^kp_{11}^kp_{12}^{m-1}=&B^{m-1}p_{01}^n p_{02}^k,\\ c_0^{m-1}c_1^nc_2^kp_{21}^{m-1}p_{22}^{n}=&B^{m+n-1}p_{01}^n p_{02}^k. \endaligned \tag2.3a $$ Similarly, we assume the $B$-trinomial recurrence for (2.2b) and (2.2c), which become $$ \aligned b_0^{m}b_1^{n-1}b_2^kp_{21}^mp_{22}^{n-1}=&B^{n-1}p_{11}^k p_{12}^m,\\ d_0^{m}d_1^{n-1}d_2^kp_{01}^{n-1}p_{02}^{k}=&B^{n+k-1}p_{11}^k p_{12}^m. \endaligned \tag2.3b $$ and $$ \aligned f_0^{m}f_1^{n}f_2^{k-1}p_{01}^np_{02}^{k-1}=&B^{k-1}p_{21}^m p_{22}^n,\\ e_0^{m}e_1^{n}e_2^{k-1}p_{11}^{k-1}p_{12}^{m}=&B^{k+m-1}p_{21}^m p_{22}^n. \endaligned \tag2.3c $$ Since these equations should hold for all $m$, $n$ and $k$, each of these 6 equations contains 3 equations (one each in $m$, $n$, and $k$). Thus we have 18 equations in the 25 free variables, which are written in a matrix form, where the first column comes from the equations in (2.3a): $$ \pmatrix p_{12}a_0 &p_{21}b_0 &f_0 \\ a_1 &p_{22}b_1 &p_{01}f_1 \\ p_{11}a_2 &b_2 &p_{02}f_2 \\ p_{21}c_0 &d_0 &p_{12}e_0 \\ p_{22}c_1 &p_{01}d_1 &e_1 \\ c_2 &p_{02}d_2 &p_{11}e_2 \endpmatrix = \pmatrix B &p_{12} &p_{21} \\ p_{01} &B &p_{22} \\ p_{02} &p_{11} &B \\ B &p_{12} &p_{21}B\\ p_{01}B&B &p_{22} \\ p_{02} &p_{11}B&B \endpmatrix . $$ One may find the general solution to these 18 equations, leaving 7 free variables $$ \{a_0,a_1,a_2,b_0,b_1,b_2,B\}. $$ The explicit solutions for the remaining 18 variables are given below. The weights (wt) become (W): \roster \item"(W10)" $a_0^{m-1}a_1^{n}a_2^k$ \quad for a descent $10$, \item"(W21)" $b_0^mb_1^{n-1}b_2^k$ \quad for a descent $21$, \item"(W20)" $(a_0b_0)^{m-1}(a_1b_1)^{n}(a_2b_2)^{k}$ \quad for a descent $20$, \item"(W01)" $(B/a_0)^{m}(B/a_1)^{n-1}(B/a_2)^{k}$ \quad for an ascent $01$, \item"(W12)" $(B/b_0)^{m}(B/b_1)^n(B/b_2)^{k-1}$ \quad for an ascent $12$, \item"(W02)" $(B/a_0b_0)^{m}(B/a_1b_1)^n(B/a_2b_2)^{k-1}$ \quad for an ascent $02$, \endroster and $$ \align p_0(n,k)&=a_1^n(a_2b_2)^k, \quad p_1(k,m)=b_2^k(B/a_0)^m,\\ p_2(m,n)&=(B/a_0b_0)^m(B/b_1)^n. \endalign $$ \proclaim{Theorem 2} The generating function of all words $w\in W(m,n,k)$ with weights given by (W) is $$ \align a_1^n(a_2b_2)^k &\qtri{m+n+k-1}{m-1}{n}{k}{B}+ b_2^k(B/a_0)^m \qtri{m+n+k-1}{m}{n-1}{k}{B}+\\ &(B/a_0b_0)^m(B/b_1)^n \qtri{m+n+k-1}{m}{n}{k-1}{B}. \endalign $$ \endproclaim Theorem 1 is the special case of Theorem 2 for which $B=xyz$, \newline $a_0=a_1=a_2=x$, and $b_0=b_1=b_2=y$ hold. There are 7 other versions of Theorem 2. These 8 theorems arise by independently replacing the pair of factors $(B^{m-1}, B^{m+n-1})$ by $(B^{m+k-1}, B^{m-1})$ in equation (2.3a), $(B^{n-1}, B^{n+k-1})$ by $(B^{n+m-1}, B^{n-1})$ in equation (2.3b), and $(B^{k-1}, B^{k+m-1})$ by $(B^{k+n-1}, B^{k-1})$ in (2.3c). The $B$-trinomial recurrence still holds. For instance if we make a replacement in (2.3a), $$ \aligned a_0^{m-1}a_1^na_2^kp_{11}^kp_{12}^{m-1}=&B^{m+k-1}p_{01}^n p_{02}^k,\\ c_0^{m-1}c_1^nc_2^kp_{21}^{m-1}p_{22}^{n}=&B^{m-1}p_{01}^n p_{02}^k, \endaligned \tag2.3a$'$ $$ then the explicit solutions to (2.3a$'$) and (2.3b-c) give the weight (W$'$): \roster \item"(W$'$10)" $a_0^{m-1}a_1^{n}a_2^k$ \quad for a descent $10$, \item"(W$'$21)" $b_0^mb_1^{n-1}b_2^k$ \quad for a descent $21$, \item"(W$'$20)" $(a_0b_0)^{m-1}(a_1b_1/B)^{n}(a_2b_2/B)^{k}$ \quad for a descent $20$, \item"(W$'$01)" $(B/a_0)^{m}(B/a_1)^{n-1}(B^2/a_2)^{k}$ \quad for an ascent $01$, \item"(W$'$12)" $(B/b_0)^{m}(B/b_1)^n(B/b_2)^{k-1}$ \quad for an ascent $12$, \item"(W$'$02)" $(B/a_0b_0)^{m}(B/a_1b_1)^n(B^2/a_2b_2)^{k-1}$ \quad for an ascent $02$, \endroster and the corresponding theorem is the following: \proclaim{Theorem 2$'$} The generating function of all words $w\in W(m,n,k)$ with weights given by (W$'$) is $$ \align a_1^n(a_2b_2/B)^k &\qtri{m+n+k-1}{m-1}{n}{k}{B}+ b_2^k(B/a_0)^m \qtri{m+n+k-1}{m}{n-1}{k}{B}+\\ &(B/a_0b_0)^m(B/b_1)^n \qtri{m+n+k-1}{m}{n}{k-1}{B}. \endalign $$ \endproclaim We do not state the remaining 6 variations here. We can find Mahonian statistics by requiring that the generating function in Theorem~2 is the $B$-trinomial via the $B$-trinomial recurrence. There are six choices for this recurrence, one for each ordering of the 3 terms. So Theorem~2 gives a total of $6$ possible Mahonian statistics, one of which ($maj_{012}$), is found by setting $a_0=a_1=a_2=b_0=b_1=b_2=1$. Theorem~2$'$ also gives a total of $6$ possible Mahonian statistics, one of which is found by setting $a_0=a_1=b_0=b_1=b_2=1,\ a_2=B$. Similarly there are $6$ possible Mahonian statistics for each of other 6 versions of Theorem~2, for a total of $6\!\times8=48$. Six of them are the six possible $maj_{\sigma}$ statistics, the remaining 42 come in 7 classes of six each, and they are all variations on $maj$. Each class of size 6 consists of a $maj$ variation, and 5 others which correspond to 5 non-trivial reorderings of $\{0,1,2\}$ of that $maj$ variation. We give below one member of each class, eight in total. We start with an example from Theorem~2$'$. If we set $a_0=a_1=b_0=b_1=b_2=1,\ a_2=B$ in Theorem~2$'$, the weight (W$'$) reduces to \roster \item"(W$'$10)" $B^k$ \quad for a descent $10$, \item"(W$'$21)" 1 \quad for a descent $21$, \item"(W$'$20)" $B^{-n}$ \quad for a descent $20$, \item"(W$'$01)" $B^{m+n+k-1}$ \quad for an ascent $01$, \item"(W$'$12)" $B^{m+n+k-1}$ \quad for an ascent $12$, \item"(W$'$02)" $B^{m+n+k-1}$ \quad for an ascent $02$. \endroster Note that the above weight (W$'$) is a perturbation of $maj_{012}$ involving the descents $10$ and $20$. We write it as $maj_{012}+s_0$, where $s_0$ is defined in the following way. We define $s_0$ by giving the non-zero values at adjacent letters. One then adds these values to find $s_0$. It is assumed that if $w$ is truncated after the adjacent letters, $w$ has $m$ 0's, $n$ 1's, and~$k$~2's. \flushpar $s_0(w)$: \roster \item ${k}$ \quad for an adjacent $10$, \item ${-n}$ \quad for an adjacent $20$. \endroster For example, $$ s_0(22012110201)=-0+3-3=0. $$ It turns out (we do not write down the details here) that the eight statistics (including $maj_{012}$) can be defined by three independent perturbations of $maj_{012}$: $s_0$, $s_1$, and $s_2$. For any subset $A\subset\{0,1,2\}$ put $$ s_A(w)=\sum_{i\in A} s_i(w). $$ Then the eight Mahonian statistics are $maj_{012}+s_A$. In fact the set $A$ indicates which replacements are made in (2.3a-c). For instance the above (W$'$) is $maj_{012}+s_{\{0\}}$ and if we make replacements, say in (2.3b) and (2.3c), then the corresponding statistics will be $maj_{012}+s_{\{1,2\}}$, and so on. We define $s_1$, $s_2$ analogously by giving the non-zero values at adjacent letters. One then adds these values to find the statistic. It is assumed that if $w$ is truncated after the adjacent letters, $w$ has $m$ 0's, $n$ 1's, and~$k$~2's. \flushpar $s_1(w)$: \roster \item ${m}$ \quad for an adjacent $21$, \item ${-k}$ \quad for an adjacent $01$. \endroster $s_2(w)$: \roster \item ${n}$ \quad for an adjacent $02$, \item ${-m}$ \quad for an adjacent $12$. \endroster For example, $$ s_1(22012110201)=-2+1-4=-5, \quad s_2(22012110201)=-1+3=2. $$ Below is a table evaluating $maj_{012}$, $s_0$, $s_1$, and $s_2$ at the 6 permutations of $012$. Note that the $maj_{012}$ generating function is $1+2B+2B^2+B^3$, which is also the generating function for $maj_{012}+s_A$, for any subset $A\subset \{0,1,2\}$. $$ \matrix \text{word} &maj_{012} &\hfill s_0 &\hfill s_1 &\hfill s_2\\ 012&3 &\hfill 0 &\hfill 0 &-1\\ 021&1 &\hfill 0 &\hfill 1 &\hfill 0\\ 102&2 &\hfill 0 &\hfill 0 &\hfill 1\\ 120&1 &-1 &\hfill 0 &\hfill 0\\ 201&2 &\hfill 0 &-1 &\hfill 0\\ 210&0 &\hfill 1 &\hfill 0 &\hfill 0 \endmatrix $$ We repeat that all 48 Mahonian statistics may be found from these 8 by permuting the letters $0$, $1$, and $2$. In this case $maj_{012}$ becomes $maj_{\sigma}$, and each $s_i$ is found by applying $\sigma$ to $0$, $1$, and $2$ in the definition of $s_i$. {\subheading{3. $N$ letters}} In this section we briefly generalize Theorem 2 to words with $N$ letters in Theorem 3. We state the $N$ letter version of Theorem 1 in Corollary 1. There are $N!\,2^N$ Mahonian statistics, which come in $2^N$ families each of size $N!$. We explicitly give the corresponding $2^N$ Mahonian statistics in Corollary 2. Let $W(a_0,a_1,\cdots, a_{N-1})$ be the set of all words $w$ with $a_i$ $i$'s, $0\le i\le N-1$. If the words $w$ have $N$ letters instead of 3 letters, then each adjacent pair $ij$, $i\ne j$, could be weighted by $N$ variables, instead of 3 variables. Also the coefficients $p_i$, $0\le i\le N-1$ would have $N-1$ variables. Together with the base $B$, we have a total of $N(N^2-N)+N(N-1)+1=N^3-N+1$ variables. Each of the $N$ recurrences required by induction gives $N(N-1)$ equations in these variables. So $N(N-1)+1$ variables will be free in the multivariable version of Theorem 2. In order to fully describe the resulting theorem, some care must be taken with notation. The $N(N-1)+1$ free variables may be taken to be the base $B$ along with the $N$ weights of the adjacent pairs $(i+1)i$, for $i=0, \cdots, N-2$, for which we use the variables $$ (x_{i0},x_{i1},\cdots,x_{iN-1}), \quad 0\le i\le N-2. $$ Suppose that $w$ ends in an adjacent pair $ij$, $i\ne j$, and that there are $n_k$ $k$'s preceding the last letter $j$ of $w$. The weight of the pair $ij$ is given by $$ \aligned &\prod_{k=0}^{N-1} \bigl(\prod_{l=j}^{i-1}x_{lk}\bigr)^{n_k} \quad\quad{\text{ if }}j