%This is a plain TeX file that will produce 23 pages
%No additional format or input

\voffset=6mm
\hoffset=4mm
\catcode'32=9
\magnification=1200

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

%%\font\tengoth=eufm10
%%\font\eightgoth=eufm8
%%\font\sevengoth=eufm7
%%\font\sixgoth=eufm6
%%\font\fivegoth=eufm5

%%\newfam\gothfam


\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt \r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  %% \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth 
  %% \scriptscriptfont\gothfam=\fivegoth
  %%  \def\goth{\fam\gothfam\tengoth}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  %%\textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  %%\scriptscriptfont\gothfam=\fivegoth
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

%permet dans la frappe de retrouver les habitudes de
%la dactylographie francaise qui conseille de mettre 
%un espace avant les signes de ponctuation ; : ! ?
%et d'empecher pourtant une coupure de ligne a cet
%endroit dans le traitement

\catcode`\;=\active
\catcode`\:=\active
\catcode`\!=\active
\catcode`\?=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
  \unskip\kern\fontdimen2\font \kern-1.4\fontdimen3\font
  \fi\fi\string;}
\def:{\relax\ifhmode\ifdim\lastskip>\z@
  \unskip\penalty\@M\ \fi\fi\string:}
\def!{\relax\ifhmode\ifdim\lastskip>\z@
  \unskip\kern\fontdimen2\font
  \kern-1.4\fontdimen3\font\fi\fi\string!}
\def?{\relax\ifhmode\ifdim\lastskip>\z@
  \unskip\kern\fontdimen2\font
  \kern-1.4\fontdimen3\font\fi\fi\string?}

\frenchspacing
\tenpoint

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse 
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high

\catcode`\@=12

% Ce qui suit vient de lothar.tex

\font\petcap=cmcsc10
\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }
\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak\hskip 0em
  plus .3em minus .4em }
\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}
\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }
\def\section#1|
                {\par\vskip .3cm
                {\bf #1}\pointir}
\def\ssection#1|
                {\par\vskip .2cm
                {\it #1}\pointir}
\long\def\th#1|#2\finth{\par\vskip 5pt
              {\petcap #1\pointir}{\it #2}\par\vskip 3pt}
\long\def\tha#1|#2\fintha{\par\vskip 5pt
                    {\petcap #1.}\par\nobreak{\it #2}\par\vskip 3pt}
\def\cf{{\it cf}}
\def\rem#1|
{\par\vskip 5pt
                 {{\it #1}\pointir}}
\def\rema#1|
{\par\vskip 5pt
                 {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, v.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\hbox{\hskip 1pt\vrule width 4pt height 6pt
depth 1.5pt\hskip 1pt}}
\def\cqfd{\penalty 500 \hbox{\qed}\par\vskip 3pt}




\def\Lig{\mathop{\rm Ligne}\nolimits}   
\def\Ilig{\mathop{\rm Iligne}\nolimits}   
\def\Colig{\mathop{\rm Coligne}\nolimits}   
\def\Icolig{\mathop{\rm Icoligne}\nolimits}   
\def\des{\mathop{\rm des}\nolimits}   
\def\maj{\mathop{\rm maj}\nolimits}   
\def\codes{\mathop{\rm codes}\nolimits}   
\def\comaj{\mathop{\rm comaj}\nolimits}   
\def\ides{\mathop{\rm ides}\nolimits}   
\def\imaj{\mathop{\rm imaj}\nolimits}   
\def\div{\mathop{\rm div}\nolimits}  
\def\ig{\hbox{\bf i}}    
\def\rg{\hbox{\bf r}}    
\def\cg{\hbox{\bf c}}    
\def\R{\mathop{\rm R{}}}   
\def\Bij{\mathop{\rm Bij}}   
\def\inv{\mathop{\rm inv}\nolimits}   
\def\Fix{\mathop{\rm Fix}\nolimits}   
\def\Trans{\mathop{\rm Trans}\nolimits}   
\def\card{\mathop{\rm card}\nolimits}  
\def\sgn{\mathop{\rm sgn}\nolimits}  
\def\shape{\mathop{\rm shape}\nolimits}    
\let\findem=\cqfd   
\def\weight{\mathop{\rm weight}\nolimits}    
\def\length{\mathop{\rm length}\nolimits}    
\def\red{\mathop{\rm red}\nolimits}    


\auteurcourant={D. FOATA AND D. ZEILBERGER}
\titrecourant={MULTIBASIC EULERIAN POLYNOMIALS} 



\vglue1.5cm
  
\centerline{{\bf MULTIBASIC EULERIAN POLYNOMIALS}}
\vskip 2.8mm 
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{{\petcap Dominique} FOATA 
\footnote{$(^*)$}{Department
of Mathematics, Drexel University, 
Philadelphia, PA 19104, USA. 
Supported in part by NSF grant
DMS 8901610. On leave (1989) from
D\'epartement de math\'ematique, 
Universit\'e Louis-Pasteur, 7,
Rue Ren\'e-Descartes, F-67084 Strasbourg, France.}
{\sevenrm AND} {\petcap Doron} ZEILBERGER 
\footnote{$(^{**})$}{Department of Mathematics, 
Drexel University,
Philadelphia, PA 19104, USA. 
Supported in part by NSF grant
DMS 8800663.}}
\vskip 1cm
\abstract{Eulerian polynomials with several bases are
defined. Their combinatorial interpretations are given
as well as congruence properties modulo
some ideals generated by cyclotomic polynomials.}

\titre 1. Introduction|   
It is well-known (see, e.g., [Ri, chap.~7]) that 
the identity
$$\sum_n {u^n\over n!} A_n(t)=
{1-t\over 1 - t\exp\bigr((1-t)u\bigl)}\qquad
(n\ge 0)\leqno(1.1)$$
defines a sequence of polynomials
$(A_n(t))$, called {\it Eulerian polynomials}, whose
classical combinatorial interpretation is the following :
for each permutation
$\sigma=\sigma(1)\ldots\sigma(n)$ 
let $\des\sigma$ be the {\it number of descents}
of $\sigma$, that is, the number of
$i$ such that 
$1\le i\le n-1$ and $\sigma(i)>\sigma(i+1)$. Then
$A_n(t)=\sum_\sigma t^{1+\des\sigma}$ 
$(\sigma\in {\cal S}_n)$. This shows, in particular,
that each polynomial $A_n(t)$ has positive integral coefficients
whose sum is $n!$  

As usual, let
$$(u;q)_n=\cases{1,&if $n=0$ ;\cr
(1-u)(1-uq)\ldots (1-uq^{n-1}),&if $n\ge 1$ ;\cr}$$
denote the $q$-ascending factorial and also let
$$(u;q){_\infty}=\prod_{n=0}^\infty (1-uq^n).$$
Further, let
$${n\brack i}_q={(q;q)_n \over (q;q)_i (q;q)_{n-i}}$$
denote the Gaussian polynomial for $0\le i\le n$.
Finally, let the two $q$-exponentials be given by
(see [An, chap.~2])
$$\leqalignno{e(u;q)&=\sum_{n\ge 0} 
{u^n\over (q;q)_n}=(u;q)^{-1}_\infty\,;&(1.2)\cr
E(u;q)&=\sum_{n\ge 0} q^{n(n-1)/2} 
{u^n\over (q;q)_n}=(-u;q)_\infty.&(1.3)\cr}$$
Our purpose is to investigate the properties of a class of
polynomials 
$(A_{\bf n}(s;q_1,\ldots,q_l))$ 
(${\bf n}=(n_1,\ldots,n_l)\in {\bf N}^l$,
$l\ge 1$)
in $(l+1)$ variables [in short, $A_{\bf n}(s;{\bf q})$]
defined by the identity
$$
\sum _{\bf n} 
{\prod_j u_j^{n_j} \over \prod_j (q_j;q_j)_{n_j}}
A_{\bf n}(s;{\bf q})
={1-s\over 
1-s\prod_j e\bigl((1-s)u_j;q_j\bigr)},
\leqno(1.4)$$
where $j$ goes from 1 to $l$. 
To convince ourselves that each
$A_{\bf n}(s;{\bf q})$
is a {\it polynomial} with {\it integral}
coefficients we may rewrite (1.4)
as $L=(1-R)^{-1}$. The identity
$L(1-R)=1$ yields
the recurrence relation
$$
A_{\bf n}(s;{\bf q})=\sum_{\bf i}
\prod _j {n_j\brack i_j}_{q_j}
A_{\bf i}(s;{\bf q})
s(1-s)^{n_1-i_1+\cdots+n_l-i_l-1},
\leqno(1.5)$$
where $j$ goes from 1 to $l$ and
where ${\bf i}=(i_1,\ldots, i_l)$ runs over
all sequences of nonnegative integers
satisfying ${\bf i}\not=(n_1,\ldots,n_l)$
and $0\le i_1\le n_1$, \dots,
$0\le i_l\le n_l$. As $A_{\bf 0}(s;{\bf q})=1$,
relation (1.5) shows by induction that each
$A_{\bf n}(s;{\bf q})$
is a polynomial with integral coefficients.
To show that the coefficients are indeed positive
and of sum $(n_1+\cdots+n_l)!$ requires more
analysis and will be a consequence of theorem~1 
or theorem~2 below.

The second class of polynomials under study will be
denoted by $(B_{\bf n}(s;{\bf q}))$
$({\bf n}\in {\bf N}^{k+1},\ k\ge 0,\ 
{\bf q}=(q_1,\ldots,q_k))$. They are defined by
$$\displaylines{(1.6)
\quad
\sum _{\bf n} 
{\prod_{j=1}^{k+1} u_j^{n_j} \over 
\prod_{j=1}^k (q_j;q_j)_{n_j}  n_{k+1}!}
B_{\bf n}(s;{\bf q})\hfill\cr
\noalign{\vskip -5pt }
\hfill{}={1-s\over 
1-s\prod_{j=1}^k e\bigl((1-s)u_j;q_j\bigr)
\,\exp\bigl((1-s)u_{k+1}\bigr)}.
\quad\cr}$$
Assume $0\le k$, $k+1=l$ and 
let $q_{l}=1$ in
(1.5). Then $A_{\bf n}(s;{\bf q})$
is transformed into a polynomial in $(k+1)$
variables $s,q_1,\ldots,q_k$. Furthermore, the Gaussian
polynomial ${n_l\brack i_l}_{q_l}$ becomes the ordinary
binomial coefficient ${n_l\choose i_l}$. Hence (1.4) itself
is transformed into identity (1.6). Thus
$$B_{n_1,\ldots,n_{k+1}}(s;q_1,\ldots,q_k)
=A_{n_1,\ldots,n_{k+1}}(s;q_1,\ldots,q_k,q_{k+1})
\Big|_{\textstyle q_{k+1}=1}.\leqno(1.7)$$
Conversely, put $u_{k+1}=0$ in (1.6) and let $k=l$.
Then (1.6) yields (1.4), so that
$$A_{n_1,\ldots,n_{k}}(s;q_1,\ldots,q_k)
=B_{n_1,\ldots,n_k,0}(s;q_1,\ldots,q_k).\leqno(1.8)$$
We emphasize the fact that $A_{\bf n}(s;{\bf q})$
has $l$ indices and $(l+1)$ variables, whereas
$B_{\bf n}(s;{\bf q})$ has $(k+1)$ indices and 
$(k+1)$ variables.

When $k=0$, then 
$B_{\bf n}(s,q_1,\ldots,q_k)$
reduces to the usual Eulerian polynomial
$A_n(s)$ defined in (1.1). When
$l=1$, then
$A_{\bf n}(s,q_1,\ldots,q_l)$
is the $q$-{\it Eulerian polynomial}
$A_n(s,q)$ that is known to be
[St] the generating polynomial for the
permutation group by the bivariate
statistic $(1+{\rm number\ of\ descents} ,
{\rm inversion\ number})$. Identity (1.6)
for $k=1$  was considered by
D\'esarm\'enien [De] for his definition
of the $q$-{\it Eulerian polynomials
with two indices}.

The theory of basic hypergeometric series
is now well understood, witness the
forthcoming book by Gasper and Rahman [GaRa2].
They have also paved the way for the
almost untouched forest of 
{\it multi}-basic hypergeometric series
([Ga], [GaRa1]). Our intention here is
to derive the properties of the
multibase-analog of the classical
Eulerian polynomials using mainly symmetric
function techniques and combinatorial
manipulations on the inversion numbers.

We first give
a combinatorial interpretation to
$A_{\bf n}(s;{\bf q})$ and
$B_{\bf n}(s;{\bf q})$. Because of (1.7) it suffices to do  
it for the $A_{\bf n}(s;{\bf q})$'s.
Two combinatorial interpretations will be given,
the first one in terms of {\it lignes of route} of
permutations, the second one in terms of
{\it inversion numbers}.
The {\it ligne of route} $\Lig \sigma$ 
of $\sigma=\sigma(1)\ldots\sigma(n)$ is defined
to be the set of all $r$ such that
$1\le r\le n-1$ and $\sigma(r)>\sigma(r+1)$.
Hence $\left|\Lig\sigma\right|$ is the {\it number
of descents}, $\des\sigma$, defined above.
Furthermore, the sum of all $r$ in $\Lig\sigma$
is the classical {\it major index}, $\maj\sigma$,
of~$\sigma$. 

Let ${\bf n}=(n_1,\ldots,n_l)$ satisfy
$n_1+\cdots+n_l=n$. Also let
$n_0=0$ and denote by ${\bf n}_j$ the partial sum
${\bf n}_j=n_1+\cdots+n_j$ $(0\le j\le l)$.
For $j=1,\ldots,l$ define the $j$-th
{\it {\bf n}-inverse ligne of route} of $\sigma$
as being
$$\Ilig_j\sigma =\{ r:{\bf n}_{j-1}+1\leq r\leq {\bf n}_j-1,\,
\sigma ^{-1}(r)>\sigma ^{-1}(r+1)\} ,$$
and the $j$-th {\it {\bf n}-inversion number}
of $\sigma$ as
$$\inv_j\sigma =\#\{ (r,r'):{\bf n}_{j-1}+1\leq r
<r'\leq {\bf n}_j,\,
\sigma ^{-1}(r)>\sigma ^{-1}(r')\} .$$
Also let
$$\imaj_j \sigma 
=\sum \{ r-{\bf n}_{j-1}:r\in  \Ilig_j \sigma \}
\qquad(j=1,\ldots,l).$$
When $l=1$, the statistics $\imaj_1\sigma$
and $\inv_1\sigma$ are the familiar
inverse major index and inversion number of
the permutation $\sigma$, respectively.

The first two results of the paper can be stated as follows.

\goodbreak
\th Theorem 1|For each ${\bf n}=(n_1,\ldots,n_l)$
the generating polynomial for the permutation group
${\cal S}_n$ by the $(l+1)$-vector
$(1{+}\des,\imaj_1,\ldots,\imaj_l)$
is equal to
$A_{\bf n}(s;{\bf q})$. In other words,
if $A_{\bf n}(s;{\bf q})$
is defined by identity~$(1.4)$, then
$$A_{\bf n}(s;{\bf q})
=\sum_\sigma s^{1+\des \sigma} q_1^{\imaj_1\sigma}
\ldots q_l^{\imaj_l\sigma}\qquad
(\sigma\in {\cal S}_n).\leqno(1.9)$$ 
\finth

\vskip -5pt
\th Theorem 2|For each ${\bf n}=(n_1,\ldots,n_l)$
the generating polynomial for the permutation group
${\cal S}_n$ by the $(l+1)$-vector
$(1{+}\des,\inv_1,\ldots,\inv_l)$
is equal to $A_{\bf n}(s;{\bf q})$, i.e.,
$$A_{\bf n}(s;{\bf q})
=\sum_\sigma s^{1+\des \sigma} q_1^{\inv_1\sigma}
\ldots q_l^{\inv_l\sigma}\qquad
(\sigma\in {\cal S}_n).\leqno(1.10)$$ 
\finth

The proof of theorem 1, derived in section 2, makes
use of symmetric function techniques, especially
the Schur function algebra. To prove theorem~2 it is
more conventient to show that
$A_{\bf n}(s;{\bf q})$,
as defined in (1.10) satisfies the recurrence
relation (1.5). This is done in section~3,
by using an appropriate factorization of
permutations.

The combination of (1.9) and (1.10) suggests that
there must be a bijection of
${\cal S}_n$ onto itself that
sends the vector
$(1{+}\des,\imaj_1,\ldots,\imaj_l)$
onto
$(1{+}\des,\inv_1,\ldots,\inv_l)$.
Such a bijection can indeed be derived
(section~4). Call it 
$\sigma\mapsto\sigma'$. It has
even the following stronger property.

\th Theorem 3|The bijection
$\sigma\mapsto\sigma'$ satisfies :
$$
\Lig\sigma=\Lig\sigma'\,;\qquad
\imaj_j\sigma_j=\inv_j\sigma'\quad
(j=1,\ldots,l).$$
In particular, $\des\sigma=\des\sigma'$
and $\maj\sigma=\maj\sigma'$.
\finth

In its turn theorem~3 suggests that the polynomial
$${}^1\kern-3pt A_{\bf n}(s,p;{\bf q})
=\sum_\sigma s^{\des \sigma} 
p^{\maj\sigma}q_1^{\imaj_1\sigma}
\ldots q_l^{\imaj_l\sigma}\qquad
(\sigma\in {\cal S}_n)$$ 
should also be investigated. Using
the techniques developed in [DeFo2]
its generating function can be calculated in the form
 $$\displaylines{
\sum _{\bf n}
{\prod_j u_j^{n_j} \over (s;p)_{n_1+\cdots+n_l} 
\prod_j(q_j;q_j)_{n_j}}
\,{}^1\kern-3pt A_{\bf n}(s,p;{\bf q})
=\sum _{r} 
{s^r \over \prod_j (u_j;p,q_j)_{r+1,\infty}},\cr 
\noalign{\hbox{where}}
(u_j;p,q_j)_{r+1,\infty}=
\prod_{1\le i\le r+1}
(u_jp^{i-1};q_j)_{\infty}\qquad
(j=1,\ldots,l).\cr}$$
However the series on the right-hand side 
cannot be put into a form explicit enough
to deserve further study.
Note that the previous generating function for
the $\,{}^1\kern-3pt A_{\bf n}(s,p;{\bf q})$'s
specializes for $l=1$ to an identity worked
out by Gessel~[Ge1]. For $p=1$ the right-hand
side can be summed, as will be shown in the
proof of theorem~1 (section~2). The idea of
having the ligne of route of a permutation
split into compartments is due originally
to Remmel~[Re]. Further work along these
lines can be found in~[DeFo2].

The second goal of the paper is to work out congruence
properties for the polynomials
$B_{\bf n}(s;{\bf q})$ 
$({\bf n}\in {\bf N}^{k+1})$.
Let
$(d_1,\ldots,d_k)$ be a given sequence of positive integers
and for each ${\bf n}=(n_1,\ldots,n_k,n_{k+1})$ let
$$n_j=d_ja_j+b_j,\quad
0\le b_j\le d_j-1\qquad (1\le j\le k)\leqno(1.11)$$
be the Euclidean division of $n_j$ by $d_j$.
Then define $\div {\bf n}$ to be
$$\div {\bf n}=(b_1,\ldots,b_k,n_{k+1}+a_1+\cdots+a_k).$$
Further let $\Phi_d(q)$ denote the $d$-th cyclotomic
polynomial ($\Phi_1(q)=1-q$, $\Phi_2(q)=1+q$, \dots\thinspace).
We also prove the following theorem.

\th Theorem 4|We have the congruences :
$$
\displaylines{\quad 
B_{\bf n}(s;{\bf q})
\equiv
(1-s)^{(d_1-1)a_1+\cdots+(d_k-1)a_k}
B_{\div {\bf n}}(s;{\bf q})\hfill\cr
\hfill{}\pmod{(\Phi_{d_1}(q_1),\ldots,\Phi_{d_k}(q_k))}
\quad\cr}
$$
\finth

\noindent
The case $k=1$ is due originally to
D\'esarm\'enien [De] (see also [DeFo2]).

\th Corollary|If all the remainders
$b_j$ in $(1.11)$ are equal to
$0$ or~$1$, then
$$\displaylines{(1.12)\quad
B_{\bf n}(s;{\bf q})
\equiv
(1-s)^{(d_1-1)a_1+\cdots+(d_k-1)a_k}
A_{a_1+b_1+\cdots+a_k+b_k+n_{k+1}}(s)
\hfill\cr
\hfill{}\pmod{(\Phi_{d_1}(q_1),\ldots,\Phi_{d_k}(q_k))}\,;
\quad\cr
(1.13)\quad
A_{\bf n}(s;{\bf q})
\equiv
(1-s)^{(d_1-1)a_1+\cdots+(d_l-1)a_l}
A_{a_1+b_1+\cdots+a_l+b_l}(s)
\hfill\cr
\hfill{}\pmod{(\Phi_{d_1}(q_1),\ldots,\Phi_{d_k}(q_k))}\,;
\quad\cr}$$
where the polynomial $A_{a_1+\cdots}(s)$ on both right-hand sides 
is the Eulerian polynomial defined
in $(1.1)$.

In particular, if ${\bf n}=(2a_1+b_1,\ldots,2a_l+b_l)$ with
$b_1=0, 1$, \dots, $b_l=0,1$ and
$q_1=\cdots=q_l=q$, then
$$A_{\bf n}(s;{\bf q})
\equiv
(1-s)^{a_1+\cdots+a_l}A_{a_1+b_1+\cdots+a_l+b_l}(s)
\pmod{(1+q)}.\leqno(1.14)$$
\finth

Both theorem~4 and its corollary are proved in section~5.
The case $l=1$ of (1.14)
was in fact conjectured by Loday [Lod]
for a side calculation of the
cyclic homology of commutative algebras.
It has since received several specific proofs in [DeFo2] and
[Wa]. Michelle Wachs [Wa] derived a very ingenious
involution for proving (1.14) in the case
$l=1$. In section~6 we give a Wachs-style
combinatorial proof of theorem~4.



\titre 2. Proof of theorem 1|
In fact (1.4) with the interpretation given
in (1.7) can be viewed as a specialization of a result
on the $(k,l)$-colored permutations derived in
[DeFo2]. To make the paper self-contained we have
preferred to prove theorem~1 from scratch using
a working example. Take up again the notations preceding
theorem~1 with $\sigma$ designating a permutation of
order~$n$. For each $j=1,\ldots,l$ let $\tau_j$ be the
restriction of $\sigma$ to the set
$\sigma^{-1}([{\bf n}_{j-1}+1,{\bf n}_j])$, so that:
$$\tau_j:\sigma^{-1}([{\bf n}_{j-1}+1,{\bf n}_j])
\rightarrow [{\bf n}_{j-1}+1,{\bf n}_j].\leqno(2.1)$$
Using the Robinson-Schensted correspondence
([Kn, p. 48--72]) each bijection $\tau_j$ is mapped onto
a pair $(P_j,Q_j)$ of Young tableaux of the same
{\it shape} that we shall denote by~$\lambda_j$.
It follows from the properties of that correspondence
that the entries of $P_j$ are the elements of the interval
$[{\bf n}_{j-1}+1,{\bf n}_j]$ and the entries
of $Q_j$ are those of the set
$\sigma^{-1}([{\bf n}_{j-1}+1,{\bf n}_j])$.
For $j=1,\ldots,l$ let $T_j$ be the Young tableau
obtained from $P_j$ by replacing each entry $r$ by
$r-{\bf n}_{j-1}$ and let $U$ be the product
$$U=Q_1\otimes \cdots \otimes Q_l.$$
In the French way of displaying tableaux this
means that $U$ is the skew tableau obtained
by placing each $Q_j$ {\it to the right of}
$Q_{j-1}$ and just {\it under} it for $j=2,\ldots,l$.
Thus each $T_j$ is a Young tableau of shape
$\lambda_j$ whose entries are $1,2,\ldots,n_j$
$(j=1,\ldots,l)$ ; the entries of $U$ are
$1,2,\ldots,n$ and the shape of $U$ is the 
skew shape $\lambda_1\otimes\cdots\otimes\lambda_l$.
We summarize all this by writing :
$$\eqalign{\shape T_j&=\lambda_j\,;\quad
\left|\lambda_j\right|=n_j\,;\quad (j=1,\ldots,l)\,;\cr
\shape U&=\lambda_1\otimes\cdots\otimes\lambda_l\,;\quad
\left|\lambda_1\right|+\cdots+\left|\lambda_l\right|=n.\cr}
\leqno(2.2)$$

For instance, let $l=2$, ${\bf n}=(5,4)$ and
  $$\displaylines{
\sigma =\left(\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
1&2&3&4&5&6&7&8&9\cr
8&6&4&5&2&1&9&7&3\cr}}
\right) ;\quad
\sigma ^{-1}=\left(\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
1&2&3&4&5\cr
6&5&9&3&4\cr
}}\right.
\left|\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
6&7&8&9\cr
2&8&1&7\cr
}}\right).\cr
\noalign{\hbox{Then}}
\tau_1=\left(\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
3&4&5&6&9\cr
4&5&2&1&3\cr
}}\right);
\quad \tau_2=\left(\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
1&2&7&8\cr
2&6&9&7\cr
}}\right).\cr}$$
Under the Robinson-Schensted correspondence
$$\displaylines{
\tau _{1}\mapsto  (P_{1},Q_{1})
=\raise 16pt \hbox{$\left(\vcenter{\halign{&$\hfil#\hfil\;$\cr
                        4\cr
                        2&5\cr
                        1&3\cr}}\right.$},\;
\raise 16pt \hbox{$\left.\vcenter{\halign{&$\hfil#\hfil\;$\cr
                 6\cr
                 5&9\cr
                 3&4\cr}}\right)$};\quad
\lambda_1=(2,2,1)\,;\cr
\tau _{2}\mapsto  (P_{2},Q_{2})=
\raise 8pt \hbox{$\left(\vcenter{\halign{&$\hfil#\hfil\;$\cr
8&9\cr
6&7\cr}}\right.$},\;
\raise 8pt \hbox{$\left.\vcenter{\halign{&$\hfil#\hfil\;$\cr
2&8\cr
1&7\cr}}\right)$};\quad \lambda_2=(2,2)\,;\cr
\noalign{\hbox{and}}
T_1=P_1=
\raise 16pt \hbox{$\vcenter{\halign{&$\hfil#\hfil\;$\cr
4\cr
2&5\cr
1&3\cr}}$}\,;\quad
T_2=P_2-{\bf n}_1=
\raise 8pt \hbox{$\vcenter{\halign{&$\hfil#\hfil\;$\cr
3&4\cr
1&2\cr}}$}\,;\quad
U=\vcenter{\halign{&$\hfil#\hfil\;$\cr
6\cr
5&9\cr
3&4\cr
&&2&8\cr
&&1&7\cr}}.\cr}$$

The {\it inverse ligne of route} $\Ilig U$ of $U$
is defined as being the set of all entries
$r$ such that $(r+1)$ lies in a {\it higher} row than $r$
in $U$ (in the French way of displaying tableaux).
Furthermore, define
$$\imaj U=\sum\{r:r\in \Ilig U\}\qquad
\ides U=\left|\Ilig U\right|.$$
 
With the working example, 
$\Ilig U=\{1,2,4,5,7,8\}$,
$\imaj U=27$ and $\ides U=6$.

\th Lemma 2.1|The mapping
$(\sigma,{\bf n})\mapsto (\lambda_1,\ldots,\lambda_l;
T_1,\ldots,T_l;U)$
is a bijection having properties $(2.2)$ and satisfying
$$\eqalign{\Ilig_j\sigma_j-{\bf n}_{j-1}&=\Ilig T_j\quad
(j=1,\ldots,l)\,;\cr
\Lig \sigma&=\Ilig U.\cr}\leqno(2.3)$$
\finth

We do not prove lemma 2.1, as it was already derived in
[DeFo2] in the context of the $(k,l)$-colored permutations.
With our working example
$\Ilig_1\sigma=\{1,3\}=\Ilig T_1$ ;
$\Ilig_2\sigma=\{2\}=\Ilig T_2$ ;
$\Lig \sigma =\{1,2,4,5,7,8\}=\Ilig U$.

\vskip 5pt
It follows from (2.3) that
$$\imaj_j\sigma=\imaj T_j\quad
(j=1,\ldots,l)\,;\qquad
\des\sigma=\ides U.\leqno(2.4)$$

Let $s\,{^1\kern-3pt A_{\bf n}}(s;{\bf q})$ denote 
the right-hand
side of (1.9). Then by (2.3) and (2.4) 
$${^1\kern-3pt A_{\bf n}}(s;{\bf q})
=\sum_{(\lambda_j)}\sum_{(T_j),U}
s^{\ides U} q_1^{\imaj T_1}\ldots q_l^{\imaj T_l} ,\leqno(2.5)$$
where the first sum is over the sequences
$(\lambda_1,\ldots,\lambda_l)$ of partitions
satisfying
$\left|\lambda_1\right|=n_1$, \dots,
$\left|\lambda_l\right|=n_l$, and
the second over all sequences of tableaux
$(T_1,\ldots,T_l,U)$ satisfying (2.2).

The next step is to express the right-hand
side of (2.5) in terms of skew Schur functions.
Let $S_\theta(x_1,x_2,\ldots)$ designate the
skew Schur function associated with the
skew diagram $\theta$ ([Mac, p. 39]). The following lemma
was proved in [DeFo1].

\th Lemma 2.2|If $\theta$ is a skew diagram of $n$
elements, then
$${1\over (s;q)_{n+1}}
\sum_T s^{\ides T} q^{\imaj T}
=\sum_r s^r S_\theta(1,q,q^2,\ldots,q^r),$$
where the first sum is over all standard tableaux
$T$ of shape~$\theta$.
\finth

We are using here two specializations of this lemma
obtained by letting $q=1$ and $s=1$, respectively :
$$\leqalignno{
{1\over (1-s)^{n+1}}
\sum_T s^{\ides T} 
&=\sum_r t^r S_\theta(1^{r+1}),&(2.6)\cr
{1\over (q;q)_{n}}
\sum_T  q^{\imaj T}
&= S_\theta(1,q,q^2,\ldots\,),&(2.7)\cr}$$
where $S_\theta(1^{r+1})$ is the skew Schur function
obtained by taking an alphabet of $(r+1)$ letters
all equal to~1.

By (2.5), (2.6) and (2.7) we have :
$$\eqalign{
{{^1\kern-3pt A_{\bf n}}(s,{\bf q})
\over (1-s)^n\prod_j(q_j;q_j)_{n_j}}
&={1\over (1-s)^n\prod_j(q_j;q_j)_{n_j}}
\sum_{(\lambda_j),(T_j),U}
s^{\ides U}\prod_j q_j^{\imaj T_j}\cr
&=\sum_{(\lambda_j)}
\sum_r s^r S_{\lambda_1\otimes\cdots\otimes\lambda_l}
(1^{r+1})\prod_j S_{\lambda_j}(1,q_j,q_j^2,\ldots\,)\cr
&=\sum_{(\lambda_j)} \sum_r s^r 
\prod_j S_{\lambda_j}(1^{r+1})
S_{\lambda_j}(1,q_j,q_j^2,\ldots\,),\cr
}$$
as $U$ is of shape $\lambda_1\otimes\cdots\otimes\lambda_l$.
In the last step we have used the fondamental multiplicative property
of the Schur functions :
$S_{\lambda\otimes\mu}(x)=S_\lambda(x)S_\mu(x)$.
Now the Cauchy identity for Schur functions
$$\displaylines{
\sum_\lambda u^{|\lambda|} S_\lambda(x)S_\lambda(y)
=\prod_{i,j}{1\over (1-ux_iy_j)}\cr
\noalign{\hbox{yields}}
\eqalign{
\sum_{\lambda_j} u_j^{|\lambda_j|} S_{\lambda_j}(1^{r+1})
S_{\lambda_j}(1,q_j,q_j^2,\ldots\,)
&=\prod_{d\ge 1} {1\over (1-u_j q_j^{d-1})^{r+1}}\cr
&={1\over {(u_j;q_j)_{\infty}}^{r+1}}.\cr}\cr}$$
As $\left|\lambda_j\right|=n_j$ $(j=1,\ldots,l)$, we may
write
$$\displaylines{\quad
\sum_{\bf n} {\prod_j u_j^{n_j}\over (1-s)^n\prod_j(q_j;q_j)_{n_j}}
\,{^1\kern-3pt A_{\bf n}}(s,{\bf q})\hfill\cr
\hfill\eqalign{
&=\sum_{\bf n} \prod_j u_j^{n_j}
\sum_{(\lambda_j)} \sum_r s^r \prod_j S_{\lambda_j}(1^{r+1})
S_{\lambda_j}(1,q_j,q_j^2,\ldots\,)\hfill\cr
&=\sum_r s^r \sum_{(\lambda_j)}
\prod_j u_j^{|\lambda_j|} S_{\lambda_j}(1^{r+1})
S_{\lambda_j}(1,q_j,q_j^2,\ldots\,)\hfill\cr
&=\sum_r s^r \prod_j \sum_{\lambda_j}
 u_j^{|\lambda_j|} S_{\lambda_j}(1^{r+1})
S_{\lambda_j}(1,q_j,q_j^2,\ldots\,)\hfill\cr
&=\sum_r \prod_j {s^r\over {(u_j;q_j)_{\infty}}^{r+1}}
={1\over -s + \prod_j (u_j;q_j)_{\infty}}.\cr}\quad\cr}$$
Next replace each $u_j$ by $u_j/(1-s)$. This yields  
$$\eqalign{\sum_{\bf n} {\prod_j u_j^{n_j}\over \prod_j(q_j;q_j)_{n_j}}
\,{^1\kern-3pt A_{\bf n}}(s,{\bf q})
&={1 -s \over -s+\prod_j ((1-s)u_j;q_j)_{\infty}}\cr
&={1 -s \over -s+\prod_j E\bigl((s-1)u_j;q_j\bigr)},\cr}$$
using the notation of the second $q$-exponential introduced
in (1.3).

The generating function for the polynomials
$A_{\bf n}(s,{\bf q})$
involves the {\it first} $q$-exponential, as shown in
the next calculation
$$\eqalign{
1+\sum _{\bf n\not= 0} 
{\prod_j u_j^{n_j} \over \prod_j(q_j;q_j)_{n_j}}
A_{\bf n}(s,{\bf q})
&=s{1 -s \over -s+\prod_j E\bigl((s-1)u_j;q_j\bigr)}-s+1
\cr
&={1-s\over 
1-s\prod_j e\bigl((1-s)u_j;q_j\bigr)},
\cr}$$
since $E(u;q)e(-u;q)=1$.
This proves theorem 1.




\titre 3. Proof of theorem 2|
Call $A^{\hbox{\sevenrm inv}}_{\bf n}(s;{\bf q})$ the 
right-hand side of (1.10), namely the generating function
for ${\cal S}_n$ by the vector
$(1+\des,\inv_1,\ldots,\inv_l)$.
We will prove that $A^{\hbox{\sevenrm inv}}_{\bf n}(s;{\bf q})$
satisfies recurrence
(1.5), i.e., the equation obtained from (1.5) by replacing
$A_{\bf n}$ and $A_{\bf i}$ by $A^{\hbox{\sevenrm inv}}_{\bf n}$
and $A^{\hbox{\sevenrm inv}}_{\bf i}$, respectively. Since 
$A_{\bf 0}=A^{\hbox{\sevenrm inv}}_{\bf 0}=1$ by convention, 
the result will follow by induction.

Consider the set ${\cal T}_n$ of all ``commaed" permutations
that consist of a permutation in ${\cal S}_n$ together with a
comma inserted in  such a way that the sequence after
the comma is {\it increasing}. For example, 
$4\,7\,1\,3, 2\,5\,6$ ;\quad
$4\,7\,1\,3\,2, 5\,6$ ;\quad
$4\,7\,1\,3\,2\,5, 6$ ;\quad
are all members of ${\cal T}_n$, but
$4\,7, 1\,3\,2\,5\,6$ is not.

To each member $(\sigma_1 , \sigma _2)$ (i.e., $\sigma_2$ is
increasing and non-empty and $\sigma:= \sigma_1 \sigma_2$
is a regular permutation of ${\cal S}_n$)
of ${\cal T}_n$ associate the weight
$$\weight( \sigma_1 , \sigma_2 )= s^{1+\des\sigma_1} s
(1-s)^{\length\sigma_2-1}  
\prod_j q_j^{\inv_j \sigma}.$$
 
Next to each $\sigma$ in ${\cal S}_n$
associate the set $C(\sigma)$
of all commaed permutations obtained from $\sigma$
by inserting a comma right before one of the
entries that belong to the maximal terminal increasing
right factor of $\sigma$.
 
For example,  $\sigma=4\,7\,1\,3\,2\,5\,6$
gives rise to the following set
$$C(\sigma)=\{4\,7\,1\,3, 2\,5\,6\,;\quad
4\,7\,1\,3\,2, 5\,6\,;\quad
4\,7\,1\,3\,2\,5, 6\,\}.$$ 

We claim that this mapping $C$ is weight preserving, 
i.e., 
$$s^{1+\des\sigma}\prod_j q_j^{\inv_j\sigma}
=\sum_{\tau\in C(\sigma)}\weight\tau.$$
Indeed the
$\prod_j q_j^{\inv_j \sigma}$ factor
is the same at both sides. The $s$-contribution is as
follows, letting $r$ be the length of the maximal increasing
right factor of $\sigma$ :
$$\displaylines{
\weight(\sigma (1)\ldots\sigma (n-r) )
[s (1-s)^{r-1}+s^2(1-s)^{r-2}+\cdots+s^2(1-s)^0 ]\hfill\cr
\hfill
{}=\weight( \sigma (1) \ldots\sigma (n-r) ) s
=\weight( \sigma (1) \ldots\sigma (n) )
=\weight(\sigma).\cr}$$
  
Thus the sum of the weights of all the elements of
${\cal S}_n$ (i.e., 
$A^{\hbox{\sevenrm inv}}_{\bf n}(s;{\bf q})$)
is the same as the sum of all the weights
of the elements of ${\cal T}_n$. Let's compute the latter,
noting that $\inv_j\sigma$ is also equal to :
$$\inv_j\sigma=\#\{(r,r'):1\le r<r'\le n,\;
{\bf n}_j\ge \sigma(r) > \sigma(r') \ge {\bf n}_{j-1}+1\,\}.$$
Consider the subset of ${\cal T}_n$ consisting of all elements
such that the comma comes right after
$i_1$ members of the first class, \dots,
$i_l$ members of the  $l$-th class.
Let $h_1=n_1 - i_1$, \dots, $h_l = n_l - i_l$
and assume that after the comma we have the fixed increasing
factor
$a_1^{(1)} \ldots a_{h_1}^{(1)} \ldots
a_1^{(l)} \ldots a_{h_l}^{(l)}$, 
with ${\bf n}_{j-1}+1\le 
a_1^{(j)} < \cdots < a_{h_j}^{(j)}\le
{\bf n}_l$ for $j=1,\ldots,l$.
The total weight of the above factor is easily seen to be
$$\displaylines{\quad
A^{\hbox{\sevenrm inv}}_{\bf i}(s;{\bf q})\,
s (1-s)^{n_1 - i_1 + n_2 - i_2 + \cdots +n_l - i_l -1}\hfill\cr
\hfill{}\times \prod_j
q_j^{ (n_j - a_{h_j}^{(j)}) 
+ (n_j - a_{h_j -1}^{(j)} -1 ) +
\cdots 
+(n_j - a_j^{(j)} - (h_j -1))}.\quad\cr}$$
Now for a fixed ${\bf i}=(i_1, i_2 ,\ldots , i_l)$ 
we have that the
sum runs independently with respect
to each of the exponents of the $q_j$'s.
It is easy to see that inside the exponent of 
$q_j$ ($j=1, \ldots, l$)
we have a typical partition of 
$n$ with largest part at most equal to
$n_j - h_j$ ($=i_j$)
and number of parts at most equal to
$h_j$. The generating function of which is
well known to be the $q$-binomial 
${n_j \brack i_j}_{q_j}$ to base $q_j$.
Since the sums over each $q_j$ run 
independently, the total weight
of members of ${\cal T}_n$ such that right 
before the comma come
$i_1$ members of the first class, \dots, 
$i_l$ members of the  $l$-th class
(regardless of what comes after) is
$$\prod_j {n_j \brack i_j }_{q_j}
A^{\hbox{\sevenrm inv}}_{\bf i}(s;{\bf q})
s (1-s)^{n_1 - i_1 + \cdots +n_l - i_l -1}.$$ 
Summing over all conceivable $\bf i \not= n$ 
establishes (1.5).\cqfd

The technique used here was inspired by some
methods developed in [Ge2] and [Ze].



\titre 4. Inversion numbers|
The proof of theorem 3 relies upon the properties
of the so-called {\it second fundamental
transformation} ([Lot, chap.~10]), we shall designate
by~$\phi$. Let $w=x_1\ldots x_m$ be a word whose letters belong
to $\bf N$ and let $x$ be an integer. If the
last letter of $w$ is greater (resp. smaller than or equal to)
$x$, the word $w$ admits a unique factorization
$(w_1y_1,\ldots,w_py_p)$, called its
$x$-{\it factorization} having the following
properties :

(i) each $y_i$ $(i=1,\ldots,p)$ satisfies
$y_i>x$ (resp. $y_i\le x$) ;

(ii) each word $w_i$ $(i=1,\ldots,p)$ is either
empty, or has all its letters smaller than or equal to
(resp. greater than)~$x$.

Define $\gamma_x(w)=y_1w_1\ldots y_pw_p$. (Note that
$w=w_1y_1\ldots w_py_p$.) The transformation $\phi$
is defined by induction as follows :
$\phi(w)=w$, if $w$ is of length one ; if $w$ has
a length at least equal to~2, write $w=vx$ with
$x$ being the last letter of $w$, and define :
$$\phi(vx)=\gamma_x\bigl(\phi(v)\bigr)x.$$
Let $W$ be the rearrangement
class of some word~$w_0$. It was proved in
[Fo] that $\phi$
is a bijection of $W$ onto itself having the
property that
$$\maj w=\inv\phi(w),\leqno(4.1)$$
for every $w\in W$.

A further property of $\phi$ was stated and
proved in [FoSch] for the rearrangement classes
$W$ containing only words without repetitions, say,
subwords of permutations. If $w$ is such 
a word, its {\it inverse ligne of route}
$\Ilig w$ may be defined as being the set of all $k$ such 
that $k$ and $(k+1)$ are letters of~$w$ and
$(k+1)$ is to the left of~$k$ in~$w$.
In particular, if $w$ is a permutation
of $1,2,\ldots,n$, then $\Ilig w$
is simply the ligne of route of the inverse
permutation~$w^{-1}$.
Thus when the rearrangement class $W$
contains only subwords of permutations,
it was shown in [FoSch] that
$$\Ilig w=\Ilig\phi(w).\leqno(4.2)$$
Recently, Bj\"orner and Wachs [BjWa]
have extended the properties of the 
second fundamental transformation to a
larger set of combinatorial objects,
and found several characterizations
for sets that satisfied (4.2).
Our purpose presently is to include
$\phi$ in the construction of a bijection
that will serve to prove theorem~3.

If 
$\sigma=\sigma(1)\ldots\sigma(n)$ 
is a permutation and if
${\bf n}=(n_1,\ldots,n_l)$ is a sequence
of integers of sum~$n$, let
$$\sigma_j=\sigma({\bf n}_{j-1}+1)\, 
\sigma({\bf n}_{j-1}+2)\,\ldots \,\sigma({\bf n}_j+1)$$
for $j=1,\ldots,l$. If $\Theta$ is any
transformation on ${\cal S}_n$, we will write :
$$(\Theta\sigma)_j=\Theta\sigma({\bf n}_{j-1}+1)\, 
\Theta\sigma({\bf n}_{j-1}+2)\,\ldots \,
\Theta\sigma({\bf n}_j+1).$$
In particular, if we apply the second fundamental
transformation $\phi$ to each $\sigma_j$ and form
the juxtaposition product
$$\psi(\sigma)=\phi(\sigma_1)\ldots\phi(\sigma_l),
\leqno(4.3)$$
we define a new transformation on ${\cal S}_n$.
Furthermore, $\phi(\sigma_j)=(\psi\sigma)_j$
using the previous notations.

\th Proposition 4.1|The sequence $\bf n$ being given,
the mapping $\psi$ is a bijection of ${\cal S}_n$
onto itself satisfying :
$$\displaylines{
(4.4)\hfill\maj\sigma_j=\inv(\psi\sigma)_j
\qquad (j=1,\ldots,l)\,;\hfill\cr 
(4.5)\hfill
\Ilig\sigma=\Ilig\psi(\sigma).\hfill\cr}$$
\finth

{\it Proof}\pointir
Relation (4.4) is just (4.1) rewritten for the
factors $\sigma_j$. Now by (4.2) we have
$\Ilig\sigma_j=\Ilig\phi(\sigma_j)$. This
takes care of all the pairs $(k,k+1)$ contained
in a single factor $\sigma_j$, and therefore
in a factor $\phi(\sigma_j)$. Next, if
$1\le i< j\le l$ and $(k+1)$ is a letter
of $\sigma_i$, while $k$ is a letter of
$\sigma_j$, then $(k+1)$ will be to the left\
of $k$ both in $\sigma$ and $\psi(\sigma)$.\cqfd

Let ${\bf i}\,\sigma=\sigma^{-1}$
and form the sequence :
$$\displaylines{
\sigma\mapsto {\bf i}\,\sigma
\mapsto \psi\,{\bf i}\,\sigma
\mapsto {\bf i}\,\psi\,{\bf i}\,\sigma,\cr
\noalign{\hbox{By (4.5)}}
\rlap{$(4.6)$}\hfill
\Lig\sigma=\Ilig {\bf i}\,\sigma
=\Ilig \psi\,{\bf i}\,\sigma
=\Lig {\bf i}\,\psi\,{\bf i}\,\sigma.\hfill\cr
\noalign{\hbox{Furthermore, by (4.4)}}
\rlap{$(4.7)$}\hfill
\maj({\bf i}\,\sigma)_j=\inv(\psi\,{\bf i}\,\sigma)_j
\qquad(j=1,\ldots,l).\hfill\cr}$$
Define
$$\sigma':={\bf i}\,\psi\,{\bf i}\,\sigma.$$
Then $\sigma\mapsto\sigma'$ is a bijection
satisfying
$\Lig\sigma=\Lig\sigma'$ by (4.6).
Furthermore, 
$$\imaj_j\sigma_j=\maj({\bf i}\,\sigma)_j
=\inv(\psi\,{\bf i}\,\sigma)_j
=\inv({\sigma'}^{-1})_j=\inv_j\sigma'.$$
This completes the proof of theorem 3.




\titre 5. The D\'esarm\'enien Verfahren|
Let $x=(x_1,x_2,\ldots\,)$ be an infinite sequence
of variables and for each $r=1,2,\ldots\,$ denote
by $h_r(x)$ the {\it homogeneous} symmetric function
in the $x_j$'s and by $p_r(x)$ the {\it power sum}
$\sum_j x_j^r$. By convention, $h_0(x)=1$.
The generating function $H(u;x)=\sum_{r\ge 0} u^r h_r(x)$
can be evaluated in different forms :
$$H(u;x)=\prod_{j\ge 1} (1-ux_j)^{-1}=\exp\sum_{r\ge 1} 
u^r{p_r(x)\over r}.\leqno(5.1)$$
(See, e.g., [Mac, p. 14 and 17].)

Recall that a partition of an integer $n$ can be expressed as
a non-increasing sequence
$\lambda=(\lambda_1,\lambda_2,\ldots\,)$
$(\lambda_1\ge\lambda_2\ge\cdots\,)$, or as
a word $\lambda=1^{m_1}2^{m_2}\ldots$ (the multiplicative
notation) with the meaning
that $\lambda$ has $m_1$ parts $\lambda_i$ equal to~1,
$m_2$ parts $\lambda_i$ equal to~2, etc\dots\  As usual, to
each partition
$\lambda$ we attach the constant
$$z_\lambda=1^{m_1}2^{m_2}\ldots m_1!\,m_2!\,\ldots$$
and the {\it power symmetric function}
$$p_\lambda(x)=p_{\lambda_1}(x)p_{\lambda_2)}(x)\ldots$$
Also $|\lambda|=n$ means that $\lambda$ is
a partition of~$n$ and the notation
$l(\lambda)$ stands for the number
of parts of~$\lambda$.

D\'esarm\'enien [De] introduced the polynomials
$$T_\lambda(q)={(q;q)_n\over \prod_j (1-q^j)^{m_j}},
\leqno(5.2)$$
where $\lambda=1^{m_1}2^{m_2}\ldots$ is a partition of $n$.
He noticed that $T_\lambda(q)$ is a polynomial of
degree $n(n-1)/2$ and can also be expressed as :
$$T_\lambda(q)=(q;q)_n \,p_\lambda(1,q,q^2,\ldots).
\leqno(5.3)$$
Furthermore, he proved the following congruence property.

\th Lemma 5.1|Let $n=da+b$, $0\le b\le d-1$ and
$\lambda=1^{m_1}2^{m_2}\ldots$ be a partition of~$n$. Then the
following congruences hold :

{\parindent=1cm
\item{(i)}{if $m_d\not=a$, then $T_\lambda(q)\equiv 0 
\pmod {\Phi_d(q)}$.}
\item{(ii)}{if $m_d=a$, let $\mu=\lambda\setminus d^a$ 
be the partition obtained from $\lambda$ by
deleting the $m_d$ parts equal to~$d$. Then
$$T_\lambda\equiv d^a a!\,T_{\mu}(q) \pmod{\Phi_d(q)}.$$
}

}
\finth

Now let $(c_i)$  $(i=0,1,\ldots\,)$ be a sequence of elements
belonging to some given ring. The relation
$$\sum_{i\ge 0} C_i {u^i\over i!}=
\sum_{i\ge 0} c_i (e^u-1)^i\leqno(5.4)$$
defines a sequence $(C_i)$ in a unique manner.

D\'esarm\'enien considered the expansion
$$\sum_{m\ge 0,\,n\ge 0}
{\cal C}_{n,m}(x) u^n {v^m\over m!}
=\sum_{i\ge 0} c_i 
\bigl(H(u;x)e^v-1\bigr)^i$$
and showed that ${\cal C}_{n,m}(x)$ can
be expressed in terms of the symmetric
finctions  $(p_\lambda(x))$ as
$${\cal C}_{n,m}(x) =\sum_\lambda C_{m+l(\lambda)}
{p_\lambda(x)\over z_\lambda}\qquad(\left|\lambda\right|=n).
$$
Then he defined the polynomials
$$K_{m,n}(q)=(q;q)_n\, {\cal C}_{m,n}(1,q,q^2,\ldots),$$
and using lemma 5.1 proved the congruence
$$K_{m,da+b}(q)\equiv K_{m+a,b}(q)
\pmod {\Phi_d(q)}.$$
Finally, he applied the latter congruence to
his $q$-Eulerian polynomials with two
indices to obtain theorem~4 for $k=1$.

\vskip 5pt
The program for an arbitray $k$ and
consequently for the multibasic Eulerian polynomials
will closely follow the foregoing pattern.
This time we have to introduce 
$l$ sequences of variables
$x^j=(x_1^j,x_2^j,\ldots\,)$ 
$(1\le j\le l)$,
and relation (5.4) being given we expand the expression
$\sum_{i\ge 0} c_i \bigl(\prod_j H(u_j;x^j)-1\bigr)^i$,
as a power series in the $u_j$'s. This is done as follows.

\th Proposition 5.2|If
$$\displaylines{\rlap{$(5.5)$}\hfill
\sum_{\bf n} \prod_{j=1}^{l} u_j^{n_j} {\cal C}_n
=\sum_{i\ge 0} c_i \Bigl(\prod_{j=1}^l 
H(u_j;x^j)-1\Bigr)^i,\hfill\cr
\noalign{\hbox{then}}
\rlap{$(5.6)$}\hfill
{\cal C}_{\bf n} =\sum_{\lambda^1,\ldots,\lambda^l}
 C_{l(\lambda^1)+\cdots+l(\lambda^l)}
\prod_{j=1}^l 
{p_{\lambda^j}(x^j)\over z_{\lambda^j}},\hfill\cr}$$
the sum being over all partitions satisfying
$\left|\lambda^1\right|=n_1$, \dots, 
$\left|\lambda^l\right|=n_l$.
\finth

The proof has been made in [DeFo2] 
in the case $l=2$ and
$H(u_2;x^2)=e^{u_2}$. The proof for
an arbitrary $l$ is quite similar and will therefore be
left out.

\vskip 5pt
Let $0\le k$ and $k+1=l$ and suppose that
$H(u_{l};x^{l})$ is equal to $e^{u_l}$. From (5.1)
it follows that $p_1(x^l)=1$ and $p_r(x^l)=0$
for $r\ge 2$. Hence, if $\left|\lambda^l\right|=n_l$,
we have
$${p_{\lambda^l}(x^l)\over z_{\lambda^l}}
=\cases{0,&if $\lambda^l\not=(1^{n_l})$ ;\cr
1/n_l!,&if $\lambda^l=(1^{n_l})$.\cr}\leqno(5.7)$$
Hence (5.6) takes the form
$${\cal C}_{\bf n}=\sum_{\lambda^1,\ldots,\lambda^k}
 C_{l(\lambda^1)+\cdots+l(\lambda^k)+n_{k+1}}
\prod_{j=1}^k{p_{\lambda^j}(x^j)\over z_{\lambda^j}}
\,{1\over n_{k+1}!},\leqno(5.8)$$
where $\left|\lambda^1\right|=n_1$, \dots, 
$\left|\lambda^k\right|=n_k$, 
and (5.5) the form
$$\sum_{\bf n} \prod_{j=1}^{k+1} u_j^{n_j} {\cal C}_n
=\sum_{i\ge 0} c_i \Bigl(\prod_{j=1}^k H(u_j;x^j)
e^{u_{k+1}}-1\Bigr)^i.\leqno(5.9)$$
For $j=1,\ldots,k$ and $r=1,2,\ldots$
replace each $x_r^j$ by $q_j^{r-1}$
in (5.8) and (5.9). This substitution being made, define
$$K_{\bf n}(q_1,\ldots,q_k)
=\prod_{j=1}^k(q_j;q_j)_{n_j}\,n_{k+1}!
\,{\cal C}_{\bf n}\Big|_{\textstyle x_r^j\leftarrow
q_j^{r-1}}.$$ 
By (5.3) and (5.8) we obtain
$$
K_{\bf n}(q_1,\ldots,q_k)
=\!\!\!\!\sum_{\left|\lambda^1\right|=n_1,\ldots,
\left|\lambda^k\right|=n_k}
\!\!\!\!{\cal C}_{l(\lambda^1)+\cdots+l(\lambda^k)+n_{k+1}}
\prod_{j=1}^k {T_{\lambda^j}(q_j)\over z_{\lambda^j}}.
\leqno(5.10)$$
On the other hand, by (1.2) and (5.1)
$$H(u_j;x^j)\Big|_{\textstyle x_r^j\leftarrow q_j^{r-1}}
=\prod_{r\ge 1}(1-u_jq_j^{r-1})^{-1}
=e(u_j;q_j).$$
Hence (5.9) becomes
$$
\sum_{\bf n} {\prod_{j=1}^{l+1} u_j^{n_j} \over
\prod_{j=1}^k (q_j;q_j)_{n_j}n_{k+1}!}
K_{\bf n}(q_1,\ldots,q_k)
=\sum _{i\ge 0}\Bigl(\prod_{j=1}^k e(u_j;q_j)
e^{u_{k+1}} - 1\Bigr)^i.\leqno(5.11)$$

\rem Remark|
In the notations of lemma 5.1, case (ii) 
($m_d=a$) we have
$l(\lambda)=l(\mu)+a$
and $z_\lambda=z_\mu d^a a!$
Hence
$${T_\lambda(q)\over z_\lambda}
\equiv {T_\mu(q)\over z_\mu}
\pmod{\Phi_d(q)}.\leqno(5.12)$$

Now let $(d_1,\ldots,d_k)$ be given and let
$n_j=d_ja_j+b_j$ $(0\le b_j\le d_j-1;\ 
1\le j\le k)$. When $K_{\bf n}$ is taken
mod $(\Phi_{d_1}(q_1),\ldots,\Phi_{d_k}(q_k))$,
formula (5.10) becomes in view of lemma 5.1 and (5.12) :
$$
K_{\bf n}({\bf q})
=\!\!\!\!\sum_{\left|\mu^1\right|=b_1,\ldots,
\left|\mu^k\right|=b_k}
\!\!\!\!{\cal C}_{l(\mu^1)+a_1+\cdots+l(\mu^k)+a_k+n_{k+1}}
\prod_{j=1}^k {T_{\mu^j}(q_j)\over z_{\mu^j}}.
$$
But by (5.10) the right-hand side of the previous
congruence is also equal to
$K_{\div {\bf n}}({\bf q})$
with
$$\div {\bf n}=(b_1,\ldots,b_k,n_{k+1}+a_1+\cdots+a_k).$$
Hence
$$K_{\bf n}({\bf q})\equiv
K_{\div {\bf n}}({\bf q})
\pmod{(\Phi_{d_1}(q_1),\ldots,\Phi_{d_k}(q_k))}.
\leqno(5.13)$$

To apply the foregoing congruence results to
the multibasic Eulerian polynomials we note
that (1.6) can be rewritten as
$$\displaylines{\quad
\sum_{\bf n} {\prod_{j=1}^{k+1} u_j^{n_j}\over
\prod_{j=1}^k (q_j;q_j)_{n_j}\, n_{k+1}!}
{B_{\bf n}(s;{\bf q})\over (1-s)^{n_1+\cdots+n_{k+1}}}
\hfill\cr
\noalign{\vskip -5pt }
\hfill{}=
\sum_{i\ge 0}
\Bigl({s\over 1-s}\Bigr)^i
\Bigl(\prod_{j=1}^k e(u_j;q_j)e^{u_{k+1}}-1\Bigr)^i.\quad\cr}$$
Comparing the latter identity with (5.11) we see that we can
apply (5.13) to
$K_{\bf n}({\bf q})
=B_{\bf n}(s;{\bf q})/(1-s)^{n_1+\cdots+n_{k+1}}$,
which are polynomials in the $q_j$'s with coefficients
in the field ${\bf Q}(s)$. This gives immediately
theorem~4.

\vskip 5pt
Consider a polynomial $B_{\bf n}(s;{\bf q})$
$({\bf n}\in {\bf N}^{k+1})$ and
suppose that the first $k$ components
of {\bf n} are equal to 0 or~1. It then follows from
(1.7) and theorem~1 that there is no
variable $q_j$ occurring in the expression
of $B_{\bf n}(s;{\bf q})$. Therefore,
this polynomial reduces to the
ordinary Eulerian polynomial
$A_{n_1+\cdots+n_{k+1}}(s)$
defined in (1.1). The corollary is then
a consequence of this observation and theorem~4.




\titre 6.
A Wachs-style proof of Theorem 4| 
We will give a Wachs-style proof of theorem 2 of [DeFo2]., i.e.
the one-colored case of theorem~4. The same argument then goes to
prove theorem~4 itself. We use the combinatorial interpretation of
theorem~2.
 
We have to prove that if $\omega=\hbox{\rm primitive 
$d$-th root of unity}$,
then
$$B_{da+b,m}(s;\omega)=(1-s)^{(d-1)a} B_{b,m+a}(s;\omega).
\leqno(6.1)$$
Let us first prove the case $a=1$, $b=0$, $m=0$, i.e., that
$B_{d,0} (s; \omega ) =(1-s)^{d-1} B_{0,1}(s;\omega)=
(1-s)^{d-1}A_1(s)=(1-s)^{d-1}s$.  This follows from 
recurrence (1.5) with one color, and the fact that
$$
{ d \brack i}_q =
 {(1- q^d ) (1- q^{d-1} ) \ldots (1- q^{d-i+1} )
\over
(1-q^i) \ldots(1- q)}
$$
vanishes when $q= \omega$ and $1\le i<d$.  
Thus by plugging in $q= \omega$ in
(1.5) there is only one surviving term, $i=0$.
We summarize this result as :
$$\sum_{{\cal S}_{d+0}}\weight\sigma=(1-s)^{d-1}s.
\leqno(6.2)$$
 
Now let us prove (6.1) in general. 
We may write
$$B_{da+b,m}(s;q)
=\sum_{{\cal S}_{(da+b)+m}} \weight\pi
=\sum_\pi s^{1+\des\pi} q^{\inv_1\pi},\leqno(6.3)$$
with $\pi$ running over ${\cal S}_{(da+b)+m}$,
so that only the elements
$1, 2,\ldots, da+b$
are taken into account for the calculation of
the exponent of~$q$.
Group those $(da+b)$ 
colored elements into
families of
consecutive $d$ elements :
$$\displaylines{
V_1 := \{1 , \ldots , d \}\,;\ 
V_2 := \{ d+1 , \ldots , 2d \}\,;\, 
\ldots\,
V_a := \{ (a-1)d+1 , \ldots , ad \}\,;\cr
\noalign{\hbox{plus a set of ``bachelors"}}
W:= \{ ad+1 , \ldots , ad+b \}.\cr}$$
It is possible to view a permutation as a ``seating" in a one-row
auditorium. From now on ``seating" and ``permutation" will be used
interchangeably. A {\it happy} seating is one in which no family
had to split, i.e., every family sits in $d$ consecutive chairs.
An {\it unhappy} seating is one in which at least one of the
$d$ families had to split.
We claim
 
(i) The sum of all the weights of the happy seatings is
$$(1-s)^{(d-1)a} B_{b,m+a} (s; \omega ).$$
 
 
(ii) The sum of the weights of all the unhappy seatings is zero.
 
\vskip 5pt 
{\it Proof} of (i)\pointir
Each happy seating can 
be characterized by a sequence
$\pi=(\sigma,\pi_1,\ldots,\pi_a)$,
where $\sigma$ belongs to ${\cal S}_{(b)+(m+a)}$
and indicates how the $b$ bachelors, the
$m$ uncolored elements and the $a$ family-blocks
are displayed on the one-row seating and where
$\pi_1$, \dots, $\pi_a$ 
are permutations that arrange the seatings within each family.
We have
$$
\des\pi = \des\sigma + \des\pi_1  + \cdots + \des\pi_a ,$$
since the total number of descents is the sum of the inter-family
and intra-family descents.   We also have that the number of
inversions of $\pi$ (that count, i.e., the inversions between the
$da+b$ elements themselves, disregarding relationships with
the $m$ elements that ``don't count") equals $d^2$ times
the number of inversions in $\sigma$
between the $a$ family blocks, plus 
$d$ times the number of
inversions that result between the $b$ bachelors
and the $a$ family blocks. To these we have to
add, of course, the ``intra-family" inversions, i.e.,
$\inv\pi_1  + \cdots + \inv \pi_a $, and finally we have to
add the inversions between the $b$ bachelors.  
Moding out by $d$ the contributions
from the first two kinds of inversions vanish
and we have (recall $q= \omega$, $\omega$ a primitive $d$-th root
of unity)
$$\displaylines{
\weight\pi=s^{1+\des\sigma}q^{\inv_1\sigma}
s^{\des\pi_1} q^{\inv\pi_1}
\ldots s^{\des\pi_a} q^{\inv\pi_a},\cr
\noalign{\hbox{so that}}
s^{a}
\weight\pi = \weight\sigma \weight\pi_1
\ldots \weight\pi_a.\cr
\noalign{\hbox{Thus}}
\eqalign{
\sum_{ \pi\ {\rm happy }}\!\!\!\!  \weight\pi
&= s^{-a}\!\!\!
\sum _{S_{b+(m+a)}}\!\!\!\! \weight\sigma 
\sum _{S_d } \weight\pi_1 
\ldots \sum_{S_ d} \weight\pi_a\cr
&= B_{b,m+a} (s; \omega )
(1-s)^{(d-1)a},
\cr}\cr}
$$
by (6.2) and (6.3). 
 
{\it Proof} of (ii)\pointir
For any set $X=\{x_1< x_2< \cdots < x_L\}$
and any permutation  $\rho=x_{i_1}x_{i_2}\ldots x_{i_L}$
of $X$ we denote by $\red\rho$ the permutation of
$1,2,\ldots,L$, called the {\it reduction} of $\rho$,
defined by $\red\rho={i_1} {i_2}\ldots {i_L}$.

Michelle Wachs ($d=2$) killed bad guys
in pairs.  We would have to exterminate them in bunches.
Let $r$ ($1\le r \le a$) be the smallest unhappy family
(i.e., $r$ is the smallest integer for which $V_r$ is an unhappy
family). Let the connected components of the seats occupied
by the $V_r$-family members have
lengths $\alpha_1, \ldots , \alpha_c$.  Obviously $c\ge 2$ and
$\alpha_1 + \alpha_2 + \cdots+ \alpha_c =d$.  

Consider all permutations
that give rise to the same unhappy $r$, same component sizes
$\alpha_1 ,\ldots , \alpha_c$, whose
last connected component {\it reduces} to the same permutation
$p\in {\cal S}_{\alpha_c}$
and in which all the non-$V_r$ objects
stay the same.  In other words, once the show has begun, only
the $V_r$-family members can move seats between themselves,
but they must observe the same ``pattern" in the
last component. We will now show that the sum of all the weights
of the seatings that are related in such a way is zero.

The descents and inversions with ``the outside world" remains fixed,
as do the descents and inversions within ``the outside world".  All
the changes are the descents and inversions due to the placements
of the $V_r$-family members themselves.  Furthermore, even
the descents and inversions due to the inhabitants 
of the last component
among themselves remain fixed, since only the relative sizes matter.
In addition the sum of the contributions to the weights from the
relative placements of the members of the $V_r$-family within
the first $c-1$ components remain the same, regardless the occupants
of the last component. (Only relative size matters.)
The only things that do change are the
inversions caused by the interaction between the $V_r$-members that
occupy the last component and the rest of their family. If the
set of occupants of the last component is
(let $\alpha_c = L$)
($x_1 , \ldots , x_L $)
($ x_1 < x_2 <\cdots < x_L$), then the
number of inversions contributed by these interactions is
$(d -\overline x_L ) + (d-1-\overline x_{L-1}) +\cdots
+(d-(L-1)-\overline x_1)$,  where $\overline x_i $ are the
reduced labels in the $V_r$-family :
$\overline x_i := x_i - rd$. What we get is
a typical partition with $\le L$ parts and largest part
$\le d-L$, whose generating function (see [An, chap. 3]) is
$(1- q^d ) \ldots (1- q^{d-L+1} )/(1-q)\ldots(1- q^L )$,
and therefore vanishes when $q= \omega$. Since all the
unhappy seatings can be partitioned into these sets, they
all die.\cqfd
 
 
\rem Note|
The same argument exactly goes over to prove
theorem 4 of the present paper. We partition each color
into the appropriate number of families and ``bachelors", and
in order to kill the unhappy seatings, we choose the lowest
color that has an unhappy family, and within this color, the
lowest unhappy family.
 

\vfill\eject

\centerline{\bf Tables of $A_{n_1,n_2,n_3}(s;q_1,q_2,q_3)$}
\vskip 5pt
\centerline{\bf for $6\ge n_1\ge n2\ge n_3\ge 0$}
\vskip 15pt
A table of the polynomials 
$A_{n_1,n_2,n_3}(s;q_1,q_2,q_3)$ such that
$n_2=0, 1$ and $n_3=0, 1$ and $n_1\le 6$ has already been
published by D\'esarm\'enien [De]. Write
$A^d_{m,n}$ for the notations adopted in [De]
and keep $A_{n_1,n_2,n_3}$ for ours. We have the
correspondence
$A_{n_1,n_2,n_3}=A^d_{n_2+n_3,n_1}$,
whenever $0\le n_2,\,n_3\le 1$. We then just list
$A_{2,2,0}$, $A_{3,2,0}$, $A_{2,2,1}$,
$A_{4,2,0}$, $A_{3,3,0}$, $A_{3,2,1}$,
$A_{2,2,2}$ that have not appeared before. 
Only the last one actually involves
the four variables $s$, $q_1$, $q_2$, $q_3$.

For example, the $(2,2,0)$-table is to be read :
$A_{2,2,2}(s;q_1,q_2,q_3)
=s+s^2(3+3q_1+3q_2+q_1q_2)+s^3(1+3q_1+3q_2+4q_1q_2)+s^4$.

\newbox\twotwozero
\newbox\threetwozero
\newbox\twotwoone
\newbox\fourtwozero
\newbox\threethreezero
\newbox\threetwoone
\newbox\twotwotwo
\newbox\tvbox
\newbox\ttvbox
\setbox\tvbox=\hbox{\vrule height 10pt depth 3pt }
\def\tv{\relax\ifmmode\copy\tvbox\else\unhcopy\tvbox\fi}
\setbox\ttvbox\hbox{\vrule height .4pt depth 0pt }
\def\ttv{\relax\ifmmode\copy\ttvbox\else\unhcopy\ttvbox\fi}


\setbox\twotwozero=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan6\strut\hfil$(2,2,0)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1q_2\cr
\noalign{\hrule}
s&&1&&&\cr
s^2&&4&3&3&1\cr
s^3&&1&3&3&4\cr
s^4&&&&&1\cr
\noalign{\hrule}
}} 



\setbox\threetwozero=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan{10}\strut\hfil$(3,2,0)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1^2&q_1q_2&q_1^3&q_1^2q_2&q_1^3q_2\cr
\noalign{\hrule}
s&&1&&&&&&&\cr
s^2&&6&6&4&6&2&&2&\cr
s^3&&3&12&6&12&12&6&12&3\cr
s^4&&&2&&2&6&4&6&6\cr
s^5&&&&&&&&&1\cr
\noalign{\hrule}
}} 



\setbox\twotwoone=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan6\strut\hfil$(2,2,1)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1q_2\cr
\noalign{\hrule}
s&&1&&&\cr
s^2&&12&6&6&2\cr
s^3&&15&18&18&15\cr
s^4&&2&6&6&12\cr
s^5&&&&&1\cr
\noalign{\hrule}
}} 





\setbox\fourtwozero=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan{16}\strut\hfil$(4,2,0)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1^2&q_1q_2&q_1^3&q_1^2q_2&q_1^4&q_1^3q_2&
q_1^5&q_1^4q_2&q_1^6&q_1^5q_2&q_1^6q_2\cr
\noalign{\hrule}
s&&1&&&&&&&&&&&&&\cr
s^2&&8&9&5&12&3&9&4&3&3&&1&&&\cr
s^3&&6&27&10&42&24&45&35&33&33&18&20&&9&\cr
s^4&&&9&&20&18&33&33&35&45&24&42&10&27&6\cr
s^5&&&&&1&&3&3&4&9&3&12&5&9&8\cr
s^6&&&&&&&&&&&&&&&1\cr
\noalign{\hrule}
}} 




\setbox\threethreezero=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan{18}\strut\hfil$(3,3,0)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1^2&q_1q_2&q_2^2&q_1^3&q_1^2q_2&q_1q_2^2&
q_2^3&q_1^3q_2&q_1^2q_2^2&q_1q_2^3&q_1^3q_2^2&
q_1^2q_2^3&q_1^3q_2^3\cr
\noalign{\hrule}
s&&1&&&&&&&&&&&&&&&\cr
s^2&&9&8&8&8&4&8&&4&4&&&4&&&&\cr
s^3&&9&24&24&24&36&24&10&36&36&10&8&36&8&8&8&1\cr
s^4&&1&8&8&8&36&8&10&36&36&10&24&36&24&24&24&9\cr
s^5&&&&&&4&&&4&4&&8&4&8&8&8&9\cr
s^6&&&&&&&&&&&&&&&&&1\cr
\noalign{\hrule}
}} 




\setbox\threetwoone=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan{10}\strut\hfil$(3,2,1)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_1^2&q_1q_2&q_1^3&q_1^2q_2&q_1^3q_2\cr
\noalign{\hrule}
s&&1&&&&&&&\cr
s^2&&17&12&8&12&4&&4&\cr
s^3&&33&60&34&60&44&18&44&9\cr
s^4&&9&44&18&44&60&34&60&33\cr
s^5&&&4&&4&12&8&12&17\cr
s^6&&&&&&&&&1\cr
\noalign{\hrule}
}} 


\setbox\twotwotwo=\vbox{\eightpoint\offinterlineskip 
\halign{\tv\thinspace\hfil$#$\hfil\thinspace &\tv#&
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace & 
\thinspace \hfil$#$\hfil\thinspace \tv\cr
\multispan{10}\strut\hfil$(2,2,2)$\hfil\cr
\noalign{\hrule}
&&1&q_1&q_2&q_3&q_1q_2&q_1q_3&q_2q_3&q_1q_2q_3\cr
\noalign{\hrule}
s&&1&&&&&&&\cr
s^2&&20&9&9&9&4&3&3&1\cr
s^3&&48&45&45&45&33&33&33&20\cr
s^4&&20&33&33&33&45&45&45&48\cr
s^5&&1&3&3&3&9&9&9&20\cr
s^6&&&&&&&&&1\cr
\noalign{\hrule}
}} 



\vfill
\line{\box\twotwozero\hfil\box\threetwozero\hfil\box\twotwoone}
\vfill
\centerline{\box\fourtwozero}
\vfill
\centerline{\box\threethreezero}
\vfill\eject
\centerline{\box\threetwoone\qquad\box\twotwotwo}
\vfill\eject

\vfill\eject


%\vskip 44pt
\vglue 44pt
\vskip 0pt plus 10pt
{\eightpoint 
\centerline{REFERENCES} 
\penalty 10000 \vskip .5cm\noindent 
\livre An|\pd ANDREWS (George E.)|The Theory of 
Partitions|Reading, Mass., Addison-Wesley, {\oldstyle1976}
({\sl Enclycopedia of Math. and Its. Appl., {\bf 2}})|
\divers BjWa|\pd BJ\"ORNER (Anders) and \pd WACHS
(Michelle L.)|Permutation Statistics and Linear
Extensions of Posets, {\oldstyle 1988}|
\article De|\pd D\'ESARM\'ENIEN (Jacques)|Fonctions
sym\'etriques associ\'ees \`a des suites classiques
de nombres|Ann. scient. \smash{\'E}c. Norm. Sup.|16|1983|271--304|
\article DeFo1|{\pc D\'ESARM\'ENIEN|} (Jacques) et
{\pc FOATA|} (Dominique)|Fonctions sym\'etriques
et s\'eries hyperg\'eom\'etriques basiques 
multivari\'ees|Bull. Soc. Math. France|113|1985|3--22|
\divers DeFo2|{\pc D\'ESARM\'ENIEN|} (Jacques) et
{\pc FOATA|} (Dominique)|Statistiques d'ordre sur
les permutations color\'ees, to appear in
{\sl Discrete Math}|
\divers DeFo3|{\pc D\'ESARM\'ENIEN|} (Jacques) and
{\pc FOATA|} (Dominique)|The signed Eulerian Numbers,
submitted|
\article Fo|\pd FOATA (Dominique)|On the Netto
inversion number of a sequence|Proc. Amer. Math.
Soc.|19|1968|236--240|
\article Fo-Sch|{\pc FOATA| (Dominique)} and {\pc
SCH\"UTZENBERGER| (Marcel-Paul)}|Major Index and Inversion
of  Permutations|Math. Nachr.|83|1978|143--159|
\article Ga|\pd GASPER (George)|Summation, transformation,
and expansion formulas for bibasic series|Trans. Amer. Math.
Soc.|312|1989|257--277|
\divers GaRa1|\pd GASPER (George) and \pd RAHMAN 
(Mizan)|An indefinite bibasic summation formula and
some quadratic, cubic, and quartic summation and
transformation formulas, preprint|
\livre GaRa2|\pd GASPER (George) and \pd RAHMAN 
(Mizan)|Basic Hypergeometric Series|Cambridge Univ.
Press, to appear|
\divers Ge1|\pd GESSEL (Ira)|Generating functions
and enumeration of sequences, Ph. D. thesis,
Dept. Math., M.I.T., Cambridge, Mass.,
111 p., {\oldstyle 1977}|
\article Ge2|\pd GESSEL (Ira)|A $q$-analogue of
the exponential formula|Discrete Math.|40|1982|69--80|
\livre Kn|Knuth (Donald E.)|The Art of Computer
Programming,  {\rm vol.~3},
Sorting and Searching|Addison-Wesley, Reading, {\oldstyle1973}|
\article Lod|\pd LODAY (Jean-Louis)|Op\'erations sur l'homologie
cyclique des alg\`ebres commutatives|Inv. Math.|96|1989|205--230|
\livre Lot|\pd LOTHAIRE (M.)|Combinatorics on
words|Addison-Wesley, Reading, {\oldstyle 1983}
({\sl Enclyclopedia of Math. and its Appl.}, {\bf 17})|
\livre Mac|\pd MACDONALD (I.G.)|Symmetric Functions and Hall
polynomials|Oxford, Clarendon Press, {\oldstyle 1979}|
\article Re|\pd REMMEL (J.B.)|Permutation Statistics
and $(k,l)$-hook Schur functions|Discrete Math.|67|1987|271--298|
\livre Ri|\pd RIORDAN (John)|An Introduction to Combinatorial
Analysis|New York, J. Wiley, {\oldstyle 1958}|
\article St|\pd STANLEY (Richard P.)|Binomial posets, M\"obius
inversion, and permutation enumeration|J. Combinatorial
Theory Ser.~A|20|1976|336--356|
\divers Wa|\pd WACHS (Michelle L.)|An involution for
signed Eulerian numbers, submitted|
\article Ze|\pd ZEILBERGER (Doron)|A lattice walk
approach to the counting of multiset permutations|J.
Math. Anal. Appl.|74|1980|192--199|

}


\bye
