\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\den{\mathop{\rm den}\nolimits}
\def\denbis{\mathop{\rm denbis}\nolimits}
\def\exc{\mathop{\rm exc}\nolimits}
\def\mar{\mathop{\rm mar}\nolimits}
\def\des{\mathop{\rm des}\nolimits}
\def\maj{\mathop{\rm maj}\nolimits}
\def\ides{\mathop{\rm ides}\nolimits}
\def\imaj{\mathop{\rm imaj}\nolimits}
\def\inv{\mathop{\rm inv}\nolimits}
\def\div{\mathop{\rm div}\nolimits}
\def\ind{\mathop{\rm ind}\nolimits}
\def\poids{\mathop{\rm poids}\nolimits}
\def\Exc{\mathop{\rm Exc}\nolimits}
\def\Nexc{\mathop{\rm Nexc}\nolimits}
\def\titrea#1|#2|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \penalty 10000
	      \centerline{\bf #2}
	      \vskip 5pt
              \penalty 10000 }

%\def\kap{\mathord{{[}{\langle}}}
%\def\Oh{\mathord{{[}\;{]}}}
%\def\revkap{\mathord{{\rangle}{]}}}
%\def\Khi{\mathord{{\rangle}{\langle}}}

\def\kap{\mathord{{[}\mskip -3mu {\langle}}}
\def\Oh{\mathord{{[}\,{]}}}
\def\revkap{\mathord{{\rangle}\mskip -3mu {]}}}
\def\Khi{\mathord{{\rangle}\mskip -3mu{\langle}}}

\def\mak{\mathop{\rm mak}\nolimits}
\def\dd{\mathop{\rm dd}\nolimits}
\def\pk{\mathop{\rm pk}\nolimits}
\def\dr{\mathop{\rm dr}\nolimits}
\def\tr{\mathop{\rm tr}\nolimits}




\auteurcourant={D. FOATA AND D. ZEILBERGER}
\titrecourant={DENERT'S PERMUTATION STATISTIC}

\vglue 20pt
\vskip 20pt
\vskip 1.5cm
\centerline{\bf DENERT'S PERMUTATION STATISTIC}
\vskip 5pt
\centerline{\bf IS INDEED EULER-MAHONIAN}
\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{A conjecture by Marleen Denert concerning
a bivariate statistic on the permutation group
is proved. The statistic has the same distribution
as the pair consisting of the number of descents and
the major index.}

\titre 1. Introduction|
In this paper we prove  a conjecture of  Marleen
Denert ([De1], [De2]) concerning a new permutation statistic
that she  has recently discovered. Namely we will prove that
her statistic when taken jointly with the number of
excedences, has the same  joint distribution as that of the
pair of classical permutation statistics that consists
of the major index and the number of descents.

Let us  start with a little history and  background.
The Hebrew book of Creation, {\it Sepher
Yetsira} (c.~300 C.E., [SU], p.~109, see also [Kn], 
p.~23), stated the
number of permutations of $n$ objects
for $n\le 7$. Saadia  Gaon (882-942 C.E.) 
gave the general rule
that the  number of permutations of 
$n$ objects is $n$ times the
number of permutations of $(n-1)$ objects by  stating  it
explicitly for $n\le 11$, and  then saying that ``if you want to
know the  [permutations] of still  larger numbers,  you may
operate according to the  same method" ([Ga], p.~496).
Saadia, however,  was only interested in these numbers up  to
$n=11$, since the largest word to be found  in the Bible
contains eleven letters, like the word 
``ve ha a kh sh de r pa n i m."
The  general  formula  was proved rigorously in 1321 by
Levi Ben  Gerson,  by what  may have been the first  use of
complete  mathematical induction ([Le], see also [Carle]).

More recently,  more refined counts of
permutations, according to various {\it statistics}, have
been undertaken. The {\it naive count} of a  family of sets $A_n$
is simply a formula for the number  of elements in $A_n$ :
$$a_n:=\sum_a 1\qquad (a\in A_n),$$
where every element carries weight 1. Often, however, the
elements of $A_n$ possess several significant numerical
attributes, called {\it statistics} (like age,  height,
weight for people), say, $f_1(a)$, \dots, $f_r(a)$.
Then one is interested in the {\it refined count} 
according to these statistics
   $$a_n(t_1,\ldots,t_r)
:=\sum_a t_1^{f_1(a)} \ldots t_r^{f_r(a)}
\qquad
(a\in A_n),$$
where every element of $A_n$ carries weight  
$t_1^{f_1(a)}\ldots t_r^{f_r(a)}$ rather than 1. 
It is then desired to find explicit formulas,
and properties of the polynomials $a_n(t_1,\ldots,t_r)$.

Various statistics on permutations 
have been discussed in the past.  Netto considered the
{\it number of inversions}, and MacMahon considered  the
{\it major index}. Another important statistic is the 
{\it number of descents}. These statistics  
are defined on  the symmetric group ${\cal S}_n$ as follows :
$$\displaylines{
   \inv\pi:=\#\{i<j ;\; \pi(i)>\pi(j)\},\qquad
\maj\pi:=\sum_i i\quad  
\bigl(\pi(i)>\pi(i+1)\bigr),\cr
\des\pi:=\#\{i ;\; \pi(i)>\pi(i+1)\}.\cr}$$

The generating functions according to these
statistics are well known (see, for example, [Fo2]) and due to
Netto, MacMahon and Euler, respectively. Using the notation
$[n]_q=(1-q^n)/(1-q)$ we have
$$\eqalignno{
\sum_{\pi\in {\cal S}_n}q^{\maj\pi}
&= [1]_q\,[2]_q\,\ldots [n]_q\,;&\hbox{({\eightrm MAJ})}\cr
\sum_{\pi\in {\cal S}_n}q^{\inv\pi}
&= [1]_q\,[2]_q\,\ldots [n]_q\,;&\hbox{({\eightrm INV})}\cr
\sum_{\pi\in {\cal S}_n}t^{\des\pi}
&=A_n(t)\,;&\hbox{({\eightrm DES})}\cr}$$
where $A_n(t)$ are the so-called {\it Eulerian polynomials}, 
that  do
not have  closed forms by themselves, but do have a nice
generating function (see~[Fo2]).

Carlitz [Carli] considered  the bi-variate refined
counting  of ${\cal S}_n$ according  to the pair 
$(\des,\maj)$. Namely he
defined (in a slightly different  notation):
  $$B_n(t) =\sum_{\pi\in{\cal S}_n} 
t^{\des\pi} q^{\maj\pi},$$
and proved that if one writes
$$B_n(t)=\sum_{k=0}^n  B_{n,k}(q)\,t^k,$$
then the  coefficients $B_{n,k}(q)$ satisfy the recurrence : 
$$B_{n,k}(q) = [k+1]_q B_{n-1,k}(q)
+q^k[n-k]_q B_{n-1,k-1}(q)  ,\eqno\hbox{({\eightrm CARLITZ})}$$
subject to the initial conditions $B_{0,k}(q)=\delta_{0,k}$.

Refined permutation-counting reached new heights with the papers
by Garsia and Gessel [G-G] and Rawlings [Ra], 
who found the generating
function for the quadruple $(\des,\ides,\maj,\imaj)$, where
$\ides\pi=\des\pi^{-1}$ and $\imaj\pi=\maj\pi^{-1}$.
This work was extended to {\it colored permutations}, and shown
to find its natural habitat  
in the theory of tableaux and Schur
functions by D\'esarm\'enien and Foata [D-F1], [D-F2].

Two statistics that have the same generating
function  are said to be
{\it equi-distributed}, and a natural
question then is whether there is a``natural" reason for
this, i.e., whether there is a bijection of the set to itself
that sends one statistic to the  other. For example, since
the right sides of ({\eightrm INV}) 
and ({\eightrm MAJ}) are identical, 
the  two statistics inv
and maj are equi-distributed,
as was first noticed by MacMahon [Ma]. In 1968
a natural bijection that
sends inv to maj was given ([Fo1], see also
[Kn], ex. 5.1.1.19), that explained in a direct manner
why inv and maj are equi-distributed. A permutation
statistic that is equi-distributed with maj (or,
equivalently, inv), is called {\it Mahonian}, and
one that is equi-distributed with  des is called {\it Eulerian}
([Fo2]).
Furthermore, if a pair of statistics has the same
joint distribution as $(\des,\maj)$ that pair is called
{\it Euler-Mahonian}. Many examples of
equi-distributed pairs are given in [Fo2].

In studying the genus zeta function, Denert ([De1],
[De2]) introduced a new permutation statistic, that we will
christen ``den." Her statistic, in a somewhat simpler form,
reads :
$$\eqalign{
\den\pi &:=\#\{1\le l<k\le n ;\;\pi(k)<\pi(l)\le k\}\cr  
&\qquad\qquad{}
+ \#\{1\le l<k\le n ;\;\pi(l)\le k<\pi(k)\}\cr
&\qquad\qquad{}
+\#\{1\le l<k\le n ;\;k<\pi(k)<\pi(l)\}.\cr}
\eqno\hbox{({\eightrm DEN})}$$
The companion statistic  to den in Denert's conjecture is
simple and well known. It is simply the {\it number of
excedences} of a permutation, defined by
$$\exc\pi:=\#\{1\le i\le n ;\; \pi(i)>i  \}. 
\eqno\hbox{\eightrm (EXC)}$$

We are now ready to state
the main result of this paper, that was conjectured
by Denert ([De1], [De2]).

\th Theorem 1|The
pairs of  permutation statistics $(\exc,\den)$
and $(\des,\maj)$ are equi-distributed. In other words, if 
$B_n(t,q)$
are Carlitz's $q$-Eulerian  polynomials introduced above, then
$$\sum_{\pi\in {\cal S}_n}t^{\exc\pi} q^{\den\pi}
= B_n(t,q).$$
\finth

The most natural proof  of this  result would be  in
terms of  a bijection from ${\cal S}_n$ 
to itself that sends the pair
$(\des,\maj)$ {\it simultaneously}  to
the pair $(\exc,\den)$. Although  it
is rather easy to find a  bijection that sends maj to den
(see next section), and it is {\it now} trivial
(see, e.g., [Lo], chap.~10.2) to  find a bijection
that sends exc to des, we are unable, at present, to find a
bijection that does both  at the same time.
Instead, we  will have
to make do with an indirect proof. We really hope that such
a bijective proof of Denert's conjecture  will be  found, and
that it will take less than
the fifty-five years that elapsed
between MacMahon's [Ma] first proof of ({\eightrm MAJ}) and
Foata's [Fo1] bijective proof.

The organization of the paper is as follows.
In section~2 we give a coding for Denert's
statistic that shows that the one-variable
``den" is Mahonian. 

In section~3 we work out
a natural definition for the Denert statistic
in terms of the positions of the excedences
and the inversion tables for the so-called excedence
and non-excedence subwords of the permutation
(theorem~2). It is very conceivable that
more and more mathematicians will rely on
computer-based proofs, especially for
proofs that require basic and lengthy
verifications, as in theorem~2.
In section~4 we then sketch another way of proving
theorem~2 that is based on the calculus
of the partial derivatives for the permutation
group. 

The key object in our derivation
is the weighted bracketing whose properties
are developed in section~5. A weighted bracketing
can be viewed as a lattice path in the
${\bf N}\times {\bf N}$-quadrant that
goes from the origin to a certain
point and whose elementary
steps are weighted. For each pair
of integers $(a,b)$ such that $a\ge b$
there is a set $U_{n,a,b}$ of such
weighted bracketings and the generating
function $D(n,a,b)$ for $U_{n,a,b}$
according to a certain weight
(``ind") can be evaluated
(theorem~3). 

More interesting
for our study is the fact that 
we can find another
recurrence relation for $D(n,a,b)$
that specializes to the
({\eightrm CARLITZ}) recurrence
formula for the {\it $q$-Eulerian
numbers} when $a=b=k$ (see
Theorem~4). This then proves
that $D(n,k,k)=B_{n,k}(q)$.

To prove theorem~1 it remains
to find a bijection of the set
$U_{n,k,k}$ onto the subset
${\cal S}_{n,k}$ of the permutations
having $k$ excedences that
sends the ind-statistic of the weighted
bracketing onto the den-statistic
of the permutation. This is done
in section~7 (theorem~5).

We end the paper by constructing
another bijection of the set $U_{n,a,b}$
into a set of objects called
{\it gravid permutations}. Again,
when $a=b=k$, the bijection sends
the weighted bracketings onto the 
(ordinary) permutations having
$k$ {\it descents}. The Mahonian
statistic ``ind" is then sent
over a new Mahonian statistic
involving the values of the
descents, that we have baptized
mak (see section~8). 
As a companion to the Eulerian statistic
$\des$, we now have two Mahonian statistics,
$\maj$ and $\mak$. The former one depends on
the {\it positions} of the descents, the latter
one on its {\it values}.

The paper ends with a table of the polynomials
$D(n,a,b)$ for $n\le 6$ and with a
description of all the bijections used
in the paper for 
the permutation group~${\cal S}_4$.




\titrea 2. A coding for Denert's statistic that
proves|that it is Mahonian|
Like the clasical ``inversion table" (e.g., Knuth [Kn], p.~21),
it is possible to use the definition ({\eightrm DEN}) 
to introduce the
{\it Denert table} $b_k$, where for
$k=1,\ldots,n$ the integer $b_k$ is the contribution
that came to den from the $k$-th entry $\pi(k)$ :
$$b_k(\pi):=\cases{\#\{l<k;\, \pi(k)<\pi(l)\le k\,\},&if
$\pi(k)\le k$ ;\cr
\#\{l<k;\,\pi(l)\le k\,\}+
\#\{l<k;\,\pi(k)<\pi(l)\,\},&if
$\pi(k)>k$.\cr}$$
Of course, $\den\pi$ is the sum of the
$b_k(\pi)$'s.

For instance, for the 
following permutation we have :
$$\eqalign{
\pi&=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
1&2&3&4&5&6&7&8&9\cr
7&1&5&4&9&2&6&3&8\cr}}\right)\cr
{\rm Denert\ table}&=
\hskip 8pt
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
0&0&2&0&3&2&1&4&1\cr}}\cr}$$
In particular, $\den\pi=13$.
It is obvious that 
$b_k\le k-1$, and it is easy to see that the mapping
$\pi\mapsto (b_k(\pi))$ is injective, and thus a bijection.

To recover $\pi$ from its Denert table $(b_k)$, first let
$\pi(n)=n-b_n$. Suppose that $\pi(k+1)$, \dots, $\pi(n)$
have been determined from the sequence
$b_{k+1}$, \dots, $b_n$. Then write the sequence
$$k, (k-1),\ldots, 2,1,n,(n-1),\ldots,(k+1),$$
and delete all the elements in this list that
are equal to $\pi(l)$ for some $l\ge k+1$.
Then $\pi(k)$ is the $(b_k+1)$-st term in
the resulting list when scanned from left to right.

It follows that the Denert statistic is Mahonian :
$$\sum_{\pi \in {\cal S}_n} q^{\den\pi}=
[1]_q\, [2]_q\,\ldots\, [n]_q.$$
The bijection of [Fo1] implies a natural mapping
between permutations $\pi$ and
sequences $a_k$ such that $0\le a_k\le k-1$
such that maj goes to the sum of the
sequence :
$\maj\pi=a_1+\cdots+a_n$.
Composing with the present correspondence we
get a natural mapping from ${\cal S}_n$ to
itself that sends maj to den.




\titre 3. A less unwieldy definition for Denert's statistic|
We will now give an alternative definition of den
in terms of a more familiar objects.  
Let $\pi=\pi(1)\pi(2)\ldots \pi(n)$
be a permutation of order~$n$. 
If $1\le i\le n-1$ and $\pi(i)>i$, say that
$i$ is an {\it excedence-place} for $\pi$, 
and $\pi(i)$ is an {\it excedence-letter}
for $\pi$ [to  paraphrase the celebrated letter-place
algebras dear to our bon Ma\^{\i}tre Gian-Carlo Rota [DRS]].    
Let $i_1<i_2<\cdots<i_k$ be the increasing 
sequence of the excedence places and 
$j_1<j_2<\cdots<j_{n-k}$ the increasing sequence of 
{\it non-excedence places}.

The subwords $\Exc\sigma=\sigma(i_1)\ldots\sigma(i_k)$ and
$\Nexc\sigma=\sigma(j_1)\ldots\sigma(j_{n-k})$ 
are referred to as the
{\it excedence-letter} and 
{\it non-excedence-letter} subwords.

A permutation $\sigma$ is said to be {\it bi-increasing}
if both subwords $\Exc\sigma$ and $\Nexc\sigma$ are increasing. 
For instance
 $$\sigma=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
1&2&3&4&5&6&7&8&9\cr
4&1&5&2&6&9&3&7&8\cr}}\right)$$ 
is bi-increasing, since $\Exc\sigma=4,5,6,9$ and 
$\Nexc\sigma=1,2,3,7,8$
are both increasing.

\th Theorem 2|Let $\sigma=\sigma(1)\sigma(2)\ldots\sigma(n)$ be
a permutation. Let $i_1$, \dots, $i_k$ be
its excedence-place sequence. Then
$$\den\sigma=i_1+i_2+\cdots+i_k+\inv\Exc\sigma+\inv\Nexc\sigma.$$ 
\finth

For instance, for the permutation $\pi$ shown in
section~2 we have
$i_1=1$, $i_2=3$, $i_3=5$,
$\Exc\pi=7,5,9$,
$\Nexc\pi=1,4,2,6,3,8$,
$\inv\Exc\pi=1$,
$\inv\Nexc\pi=3$, and then
$\den\pi=1+3+5+1+3=13$.       

\vskip 5pt
{\it Proof}\pointir
First we prove the theorem for
bi-increasing
permutations. In such a case $\inv\Exc\sigma=\inv\Nexc\sigma=0$ 
and we have to show that
$$\den\sigma=i_1+i_2+\cdots+i_k.$$  
For $n=1$ there is  nothing  to prove.  
Suppose $n\ge 2$ and let
$\sigma=\sigma(1)\sigma(2)\ldots\sigma(n)$
be a bi-increasing permutation  whose
excedence-place sequence  is $i_1<i_2<\cdots<i_k$. 
Again  we can
assume that $\sigma(i_k)=n$, 
for  otherwise we would have $\sigma(n)=n$ and
the result would  follow by induction.

Denote  by $(b_1(\sigma),b_2(\sigma),\ldots,b_n(\sigma))$ 
the Denert table
of $\sigma$. In  particular $b_{i_k}(\sigma)$ 
is equal to the number of
occurrences of the letters $\le i_k$ in the left factor
$\sigma(1)\sigma(2)\ldots\sigma(i_{k-1})$. 
For $j=i_k+1,i_k+2,\ldots,n$, let $\epsilon_j$ be equal~1
or~0, according as $j$ does or does not occur in
$\sigma(1)\sigma(2)\ldots\sigma(i_{k-1})$. We then have
$$b_{i_k}(\sigma)=i_k-1-(\epsilon_{i_k+1}+
\epsilon_{i_k+2}+\cdots+\epsilon_n).$$
Note that $\epsilon_n=0$. 
Define a  permutation $\sigma'$ in ${\cal S}_{n-1}$ by
$$\sigma'(j)=\cases{\sigma(j),&if $j<i_k$ ;\cr
\sigma(j+1),&if $i_k\le j\le n-1$.\cr}$$
Note that $i_k+1$, \dots, $n-1$, $n$  
are non-excedence places for $\sigma$, so that
$$\sigma(i_k+1)<\sigma(i_k+2)<\cdots<\sigma(n-1)<\sigma(n)<n,$$  
and thus $\sigma(i_k+1)\le i_k$, $\sigma(i_k+2)\le i_k+1$, \dots,
$\sigma(n-1)\le n-2$, $\sigma(n)\le n-1$.

Thus $\sigma'$ is also a bi-increasing permutation whose
excedence-place sequence  is $i_1,i_2,\ldots,i_{k-1}$.
Now
$b_1 ( \sigma )= b_1 ( \sigma')$, \dots,
$b_{ i_{k - 1}} ( \sigma ) = b_{ i_{k - 1}} ( \sigma') $.
Let $j= i_k , i_k +1,\ldots, n-2$. The component
$b_j ( \sigma' )$ is equal to the number of $l$ such that
$1 \le l \le j-1$ and $\sigma' (j) < \sigma' (l) \le j$.
But if $ i_k \le l \le j-1$, we have
$\sigma' (l) < \sigma' (j) $, since the word
$\sigma(i_k+1) \sigma (i_k + 2) \ldots \sigma (n)=
\sigma' ( i_k ) \sigma' ( i_k + 1) \ldots \sigma'(n-1)$ is
increasing.  Hence $b_j ( \sigma' )$ is equal to the number of
$l$ such $1 \le l \le i_k -1$ and
$\sigma' (j) < \sigma' (l) \le j$, i.e.,
$1 \le l \le i_k -1$ and $ \sigma (j+1) < \sigma (l) \le j$.
Hence, for each $j= i_k , i_{k-1} , \ldots , n-2$ we have
$$\displaylines{
b_j ( \sigma' ) = b_{j+1} ( \sigma ) -
\epsilon_{j+1}.\cr 
\noalign{\hbox{Finally,}}
b_{n-1} ( \sigma' ) = n-1-
\sigma' (n-1) = n-1 - \sigma (n) =
(n- \sigma (n) ) -1= b_n ( \sigma ) -1.\cr
\noalign{\hbox{Altogether,}}
\eqalign{ 
\den \sigma  
&=b_1 ( \sigma ) + b_2 ( \sigma ) + \cdots  + b_n ( \sigma ) \cr
&=b_1 ( \sigma' ) + \cdots + b_{ i_k -1} ( \sigma' )\cr
&\qquad\qquad{}+ i_k -1 - \epsilon _{ i_k +1} -
\epsilon _{ i_k +2} - \cdots  -
\epsilon _{n-1}\cr
&\qquad\qquad{}+( b_{i_k} ( \sigma' ) + \epsilon _{ i_k + 1} )+
( b_{ i_k +1} ( \sigma' ) + \epsilon _{ i_k + 2} )+
\cdots \cr
&\qquad\qquad{} + ( b_{n-2} ( \sigma' ) + \epsilon _{n-1} )
+ b_{n-1}( \sigma') +1.\cr}\cr
\noalign{\hbox{This is equal to}}
b_1 ( \sigma' ) + \cdots  + b_{n-1} ( \sigma' ) + i_k,\cr
\noalign{\hbox{which by induction equals}}
i_1 + \cdots  + i_{k-1} + i_k .\cr}$$
This completes the proof for bi-increasing permutations.
 
To prove the general case let $\inv \Exc \sigma = a$,
$\inv \Nexc \sigma =b$.  We prove it by induction on
$c( \sigma ) := a +b$.  Keep the same notation as above.  
In particular,
let $\Exc \sigma = \sigma ( i_1 ) \sigma ( i_2 ) \ldots $
$\sigma ( i_k )$ and
$\Nexc \sigma = \sigma ( j_1 ) \ldots  \sigma ( j_{n-k} )$.
If $\Exc \sigma$ is not increasing, 
let $m$ be the smallest integer
satisfying $1 \le m \le k-1$ and
$\sigma ( i_m ) > \sigma ( i_{m+1} )$.  
Define a new permutation
$\tau$ by letting $\tau (k) = \sigma (k)$ for all $k$ except
$k= i_m , i_{m+1}$, and $\tau ( i_m ) = \sigma ( i_{m+1} )$,
and $\tau ( i_{m+1} ) = \sigma ( i_m )$.  By definition of
$\Exc \sigma$ we have $i_m < i_{m+1}$,
$\sigma ( i_m ) > \sigma ( i_{m+1} )$, and
$ i_m < \sigma ( i_m )$, $i_{m +1} \ge  \sigma ( i_{m +1} )$,
\dots  , $i_{m+1} -1 \ge \sigma ( i_{m+1} -1 )$,
$i_{m+1} < \sigma ( i_{m+1} ) $.
Hence $ i_m < i_{m+1} < \sigma ( i_{m+1} ) = \tau ( i_m )$
and $ i_{m+1} < \sigma ( i_{m+1}) < \sigma ( i_m ) = 
\tau ( i_{m+1 })$.  Thus $ i_1 i_2 \ldots  i_k$ is also
the excedence place sequence for $\tau$.  Furthermore
$\Exc \tau = \sigma ( i_1 ) \ldots  \sigma ( i_{m+1} )
 \sigma ( i_m ) \ldots  \sigma ( i_k )$,
$\Nexc \tau = \sigma ( j_1 ) \sigma ( j_2 ) \ldots  
\sigma ( j_{n-k} ) = \Nexc \sigma $, and
$\inv \tau = \inv \Exc \sigma -1$. 
Hence $ c ( \tau ) = c ( \sigma ) -1$.
 
On the other hand, $b_k ( \tau ) = b_k ( \sigma )$ for every
$k \not= i_m , i_{m+1}$.  But
$b_{i_m} ( \tau ) = b_{i_m} ( \sigma )$, and
$b_{i_{m+1}} ( \tau ) = b_{i_{m+1}} ( \sigma ) -1$.
Hence,
$$\eqalign{\den  \sigma  
&= b_1 ( \sigma ) + \cdots  + b_n ( \sigma )\cr
& =b_1 ( \tau ) + \cdots  + b_n ( \tau ) +1\cr
& =( i_1 + \cdots  + i_k ) + \inv \Exc \tau + \inv \Nexc \tau + 1
\qquad{\rm [by\ induction]}\cr
&= ( i_1 + \cdots  + i_k )+ \inv \Exc \sigma +
\inv \Nexc \sigma .\cr}$$

Now suppose that $\Exc \sigma$ is increasing and let $m$ be the
smallest integer satisfying
$ \sigma ( j_m ) > \sigma ( j_{m+1} )$.  Again define the
permutation $\tau$ to be $\sigma$ with $\sigma ( j_m )$ and
$\sigma ( j_{m+1} )$ trading places.  Once again
$ j_m < j_{m+1}$, $ j_m \ge \sigma ( j_m )$,
$j_{m+1} \ge \sigma ( j_{m+1} )$.  Hence
$ j_m \ge \sigma ( j_m ) > \sigma ( j_{m+1} ) = 
\tau ( j_m )$, and $j_{m+1} > j_m  \ge
\sigma ( j_m ) = \tau ( j_{m+1} )$.  
This shows that
$\Exc \tau = \Exc \sigma$.  
In particular the excedence place sequence
$i_1 \ldots  i_k$ is the same for both permutations.  Also
$$\Nexc \tau = \sigma ( j_1 ) \sigma ( j_{m+1} ) \sigma ( j_m )
 \ldots  \sigma ( j_{n-k} )$$
and thus $\inv \Nexc \tau = \inv \Nexc \sigma -1$.
 
Now let's compare the Denert tables of $\tau$ and $\sigma$.
First $b_r ( \tau ) = b_r ( \sigma )$ for
$r= 1, \ldots  , j_m -1$ and $r= j_{m+1} +1 , \ldots  , n$.
By definition of $ j_m$ we have
$ \sigma ( j_1 ) < \sigma ( j_2 ) < \cdots  < \sigma ( j_m )
\le j_m$.  Hence $b_{j_m} ( \sigma ) =0$.  Also
$b_{j_{m+1}} ( \sigma )$ is equal to the number of $l$ such that
$1 \le l \le j_{m+1} -1$ and $\sigma ( j_{m+1} ) < \sigma (l)
\le j_{m+1}$, i.e., such that $1 \le l \le j_m$ and
$\sigma ( j_{m+1} ) < \sigma (l) \le j_m$.
As $\sigma ( j_{m+1} ) < \sigma ( j_m )$, that number is
one plus the number of $l$ such that $1 \le l \le j_m -1$ and
$\sigma ( j_{m + 1} ) < \sigma (l) \le j_m$.
Hence $b_{j_{m+1}} ( \sigma ) = b_{j_m} ( \tau ) +1$.  Now
$b_{j_m+1} ( \tau ) =0$ since
$\sigma ( j_1 ) < \sigma ( j_2 ) < \cdots  < \sigma ( j_{m+1} )
< \sigma ( j_m )$.
 
If $i_h$ is an excedence place between $j_m$ and
$j_{m+1}$, the number of $l$ such that 
$1\le l\le i_h - 1$ and $1\le \sigma(l) \le i_h$
is equal to the number of $l$ such that
$1 \le l \le j_m$ and
$1 \le \sigma (l) \le j_m$, i.e., $m$.  
The number of $l$ such that
$1 \le l \le j_m$ and $1 \le \tau (l) \le j_m$ is also $m$.
Hence $b_h ( \tau ) = b_h ( \sigma ) $ for
$ j_n < h < j_{m+1}$.
 
Altogether $\den \sigma  = \den  \tau +1$, 
to be compared with
$c( \sigma ) = c ( \tau ) +1$.  
We conclude, as above, that the
identity of the theorem also holds for $\sigma$.\cqfd

 
 


\titre 4. A ``short" proof of Theorem 2|
We will now give an alternative proof of theorem 2 that in some
sense is longer (and less elegant) than the preceding
proof, but in another sense is shorter (and more elegant !).
Up to purely routine calculations
(that can be easily programmed and done by computer) 
the new proof
is  shorter. On the other hand, readers who refuse 
to use computers
can still easily follow the new proof and fill in all
 the details by
hand, but then the resulting proof is messier, longer, 
and ``uglier."  In
fact the new proof is in a sense a condensation of the 
previous proof,
but since we are no longer afraid of messy (but routine)
 calculations,
we are not obligated to be ``clever."


Often in analysis it is required to prove that two functions 
$F(z)$ and
$G(z)$ are identical, but it is hard, or impossible, to do it
directly.  Then one tries to prove that their derivatives
are equal: $F'(z)=G'(z)$, form which follows, of course that
$F$ and $G$ differ by a constant, which is easily 
evaluated by plugging
in an easy value.  This is, for example, 
the way the Weierstrass
elliptic function is proved to be doubly periodic 
([Rai], p. 309).
We will use a {\it permutation group} analog of this method.
But first
we must define the notion of {\it partial derivatives} on
permutation statistics.

Given any permutation statistic $f(\pi)$, define
$\partial_af(\pi):=f((a,a+1)\pi)-f(\pi)$.
Here $(a,a+1)$ is the transposition that exchanges $a$ and
$(a+1)$. In other words $\partial_af(\pi)$ measures
the difference in $f(\pi)$ resulting from swapping
$\pi(a)$ and $\pi(a+1)$ in $\pi$. For example,
$\partial_a\inv(\pi)=2\chi(\pi(a)>\pi(a+1))-1$,
and consequently $\div\inv(\pi)=2\,\des(\pi)-(n-1)$, where
``div" is the sum of all the partial derivatives
$\partial_a$, $a=1,\ldots, n-1 $.

Let us denote the right side of the identity of theorem 2 by
$\denbis $. It is easy to see that 
$\denbis $ may be defined as
follows
$$\eqalign{
\denbis \pi
&=\#\{1 \le l <k \le n ;\, k < \pi(k) < \pi(l) \}\cr
&\qquad\qquad{}+
\#\{1 \le l <k \le n ;\, \pi(k) < \pi(l) \le l \}\cr
&\qquad\qquad{}+
\#\{1 \le l \le k \le n ;\, k < \pi(k) \}.\cr}$$
We have to prove that $\den(\pi)=\denbis (\pi)$, 
for every
permutation $\pi$.  Since the definitions of $\den$ and 
$\denbis $ are so close, 
it seems at first sight that it would be trivial
to prove that they are identical, using
elementary (and routine) Boolean algebra. 
However, we see immediately that
the difference 
$g(\pi):=\den(\pi)-\denbis (\pi)$ 
does not
disappear by simply manipulating sets. However some
cancellation occurs and leads to
$$\eqalign{
g(\pi)&:=\#\{1 \le l <k \le n ;\, \pi(k) < \pi(l) \le k \}\cr
&\qquad\qquad{}+
\#\{1 \le l <k \le n ;\, \pi(l) \le k < \pi(k) \}\cr
&\qquad\qquad{}-
\#\{1 \le l <k \le n ;\, \pi(k) < \pi(l) \le k \}\cr
&\qquad\qquad{}-
\#\{1 \le l \le k \le n ;\, k < \pi(k) \}.\cr}$$
Looking at the ``fundamental events" 
and expressing the above as a
linear combination of cardinalities of certain intersections
of these fundamental sets, does not give $0$. In other words,
the fact that $\den\equiv \denbis $ 
is not a tautology, and depends
on  complex dependence between these sets. 
It would be futile
to try and study these complex dependencies,
since they differ from permutation
to permutation. 

However the
partial derivatives $\partial_a g$ all vanish identically !
It is a completely routine matter
to find an expression for $\partial_a g ( \pi )$.
When we express it in terms of sums of cardinalities of
intersections of ``elementary events,"
all these elementary events
turn out to be independent. It follows that if
$\partial_a g( \pi )$ is indeed $0$ it must necessarily be so
for a tautologous reason.

A long and tedious calculation
(that, however takes a few seconds on a computer) then
shows that indeed $\partial_a g\equiv 0$, for 
$a = 1,\ldots, n-1$.
It follows that $g(\pi) = g ((a,a+1)\pi)$, and since
the transpositions $(a,a+1)$ generate the permutation group,
it follows that $g$ is identically constant. The ``convenient"
point is, of course, the identity permutation, for which
$g$ vanishes, and so the constant is~$0$. It follows that $g$
is identically zero, and thus that $\den\equiv\denbis  $,
proving theorem~2.




\titre 5. Weighted bracketings|
Those bracketings will serve in section 7 to code
permutations. First consider the four-letter
alphabet ${\cal A}=\{\kap,\Oh,\revkap,\Khi\}$,
whose letters will be designated by ``kappa,"
``Oh," ``reverse kappa" and ``Khi," respectively.
Of course, those four letters are simply made of 
left and right angle parentheses and left and right
brackets. We have preferred to keep this typographical
design, rather than adopt the usual font designs
for kappa, O and chi for reasons that will appear
to be clear in section~7.

If $w=x_1x_2\ldots x_n$ is a word whose letters
are taken from $\cal A$ and if $y$ is one of the 
letters $\kap$, $\Oh$, $\revkap$, $\Khi$, we
denote, as usual, by
$\left|x_1x_2\ldots x_n\right|_y$
the {\it number of occurrences} of $y$
in the word $w=x_1x_2\ldots x_n$.

A word $w=x_1x_2\ldots x_n$ is said to be
{\it legal}, if the following two properties
hold :

(i) $\left|x_1x_2\ldots x_r\right|_{\kap}
-\left|x_1x_2\ldots x_r\right|_{\revkap}\ge 0$
for each $r=1,2,\ldots,n$ ;

(ii) whenever $\left|x_1x_2\ldots x_r\right|_{\kap}
-\left|x_1x_2\ldots x_r\right|_{\revkap}= 0$
and $r<n$, then $x_{r+1}=\kap$ or $\Oh$.
(In particular, $x_1=\kap$ or $\Oh$.)

\vskip 5pt
When $a\ge b$, the set of all legal words
$w$ of length~$n$ such that
$$\left|w\right|_{\Khi}+\left|w\right|_{\kap}=a\,;\qquad
\left|w\right|_{\Khi}+\left|w\right|_{\revkap}=b\,;
\leqno(5.1)$$
will be denoted by $W_{n,a,b}$.

Each letter $x_r$ of a word $w=x_1x_2\ldots x_n$
belonging to $W_{n,a,b}$ is given the following
{\it maximum weight} $\nu_r$ defined by
$$\nu_r=\cases{\left|x_1\ldots x_{r-1}\right|_{\kap}
-\left|x_1\ldots x_{r-1}\right|_{\revkap},&
if $x_r=\kap$ or $\Oh$ ;\cr
\left|x_1\ldots x_{r-1}\right|_{\kap}
-\left|x_1\ldots x_{r-1}\right|_{\revkap}-1,&if
$x_r=\Khi$ or $\revkap$.\cr}
\leqno(5.2)$$
Finally, for each triple $(n,a,b)$ we introduce
the set $U_{n,a,b}$ of all pairs $u=(w,t)$, where
$w=x_1x_2\ldots x_n$ belongs to $W_{n,a,b}$ and
$t=t_1t_2\ldots t_n$ is a sequence of integers
satisfying the inequalities :
$$0\le t_r\le \nu_r,\qquad
{\rm for\ each}\ r=1,2,\ldots,n.\leqno(5.3)$$
The elements of $U_{n,a,b}$ will be referred
to as {\it weighted bracketings}.

A weighted bracketing can also be viewed as a
{\it weighted path} defined as follows. In the
${\bf N}\times {\bf N}$-quadrant consider
the {\it lattice paths} going from
$(0,0)$ to $(n,a-b)$ whose basic steps are one
of the four kinds :

(i) {\it North-East} steps ({\eightrm NE}) joining
vertices $(i,j)$ and $(i+1,j+1)$ :

(ii) {\it blue horizontal} steps (blue) joining vertices
$(i,j)$ and $(i+1,j)$ ;

(iii) {\it red horizontal} steps (red) joining vertices
$(i,j)$ and $(i+1,j)$ ;

(iv) {\it South-East} steps ({\eightrm SE}) joining
vertices $(i,j)$ and $(i+1,j-1)$.

\vskip 5pt
Notice that there are two kinds of horizontal steps. With
the correspondence
$\hbox{\eightrm NE}\leftrightarrow \kap$,
${\rm blue}\leftrightarrow \Oh$,
${\rm red}\leftrightarrow \Khi$,
$\hbox{\eightrm SE}\leftrightarrow \revkap$,
we see that each element $w$ in $W_{n,a,b}$
corresponds to a lattice path going from
$(0,0)$ to $(n,a-b)$. The fact that $w$
is legal insures the fact that the lattice
path always remains in the
$\bf N\times N$-quadrant.

For instance the word
$$w=\kap,\ \Oh,\ \kap,\ \Oh,\ \Khi,
\ \Oh,\ \revkap,\ \Oh,\ \revkap$$
that belongs to $W_{9,3,3}$ corresponds to the
lattice path drawn in Fig.~1, where
the red step has been represented by a dotted line.

It is readily seen from (5.2) and the forementioned
correspondence between bracketings and
lattice paths that the maximum weight $\nu_r$ can also
be defined in terms of lattice paths as follows.
Let $s_r$ be the basic step whose origin is
the point $(r-1,j)$. Then
$$\nu_r=\cases{j,&if $s_r$ is {\eightrm NE} or blue ;\cr
j-1,&if $s_r$ is red or {\eightrm SE}.\cr}
\leqno(5.4)$$
A pair $u=(w,t)$, where $w$ is such a lattice path
and $t=t_1\ldots,t_n$ is a word satisfying (5.3)
is called a {\it weighted path}.

\midinsert
\vskip 5pt
\centerline{\vbox{
\tabskip=0pt \offinterlineskip
\def\hauteur{\noalign{\vskip 15pt }}
\def\pointille{\leaders\hbox to 1.5pt{\hss\vrule
height .4pt  width .75pt depth 0.0pt \hss}\hfill}
\def\tir{\vrule height 2pt width .4pt depth 1.6pt }
\halign{\strut\hfil$#$\ &{=}#\ &&\hfil\quad#\quad\hfil\cr
\omit&\omit&\multispan3&\omit\tir\hrulefill&\omit\tir\pointille&
\omit\tir\hrulefill&\omit\tir\hfill&&\cr
\hauteur
\omit&\omit&&\omit\tir\hrulefill&\omit\tir\hfill&\multispan4&
\omit\tir\hrulefill&\omit\tir\hfill\cr
\hauteur
&\omit&\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill&
\omit\tir\hrulefill\tir\cr
r&&1&2&3&4&5&6&7&8&9\cr
\nu_r&&0&1&1&2&1&2&1&1&0\cr}}}
\vskip 5pt
\centerline{Fig. 1}
\vskip 5pt
\endinsert

Such weighted paths have been considered by
Viennot [Vi] in his combinatorial
study of the general orthogonal polynomial.
Viennot [Vi] constructed a 1-1 correspondence
between the set $\bigcup _a U_{n,a,a}$
of weighted paths and ${\cal S}_n$.
In section~7 we will give a completely
different 1-1 correspondence that will
serve to prove Denert's conjecture.
Another correspondence between
weighted paths and permutations
will lead in section~8 to the discovery
of another Euler-Mahonian statistic
$(\des,\mak)$.

Now let $u=(w,t)$ be a weighted
bracketing belonging to $U_{n,a,b}$.
Furthermore, let $w=x_1x_2\ldots x_n$,
$t=t_1t_2\ldots t_n$ and $\nu_r$ be
defined as in (5.2). Finally, let
$i_1$, $i_2$, \dots, $i_k$
be the places where the letters
$\kap$ and $\Khi$ occur in~$w$.
In other words, let
$x_{i_1}$, $x_{i_2}$, \dots, $x_{i_k}$
be the letters in~$w$ that are equal either
to $\kap$ or $\Khi$. The {\it index} 
$\ind u$ of
$u=(w,t)$ is defined by :
$$\ind u=i_1+i_2+\cdots+i_k
+t_1+t_2+\cdots+t_n.\leqno(5.5)$$
For convenience, we will write
$$\poids u=q^{\ind u}.$$
Furthermore, we will denote by
$D(n,a,b)$ the generating function
$$D(n,a,b)=\sum_u \poids u\qquad (u\in U_{n,a,b}).$$
To compute $D(n,a,b)$ we first evaluate
the total contribution to
$\sum \poids u$ $(u\in U_{n,a,b})$
arising from all the weighted bracketings
$u=(w,t)$ having the same first component $w$. This
contribution is clearly :
$$\poids w=q^{i_1+i_2+\cdots+i_k}
[\nu_1+1]_q\, [\nu_2+1]_q\,\ldots\,[\nu_n+1]_q,
\leqno(5.6)$$
in virtue of (5.3).

\th Theorem 3|The generating function
$D(n,a,b)$ satisfies the following recurrence
for $n,a,b\ge 0$, except for
$n=a=b=0$ :
$$\displaylines{(5.7)\quad
D(n,a,b)=[a-b+1]_q\, D(n-1,a,b) + q^n[a-b]_q\,
D(n-1,a-1,b)\hfill\cr
\hfill{}+[a-b+1]_q\,D(n-1,a,b-1)
+q^n [a-b]_q\, D(n-1,a-1,b-1).\cr}$$
\finth

Note that the recurrence is true for {\it all} $n,a,b\ge 0$
(except $n=a=b=0$) if one defines 
$$D(n,a,b) \equiv 0\qquad {\rm for}\ a-b < 0.\leqno(5.8)$$  
It can be used to compute $D(n,a,b)$ uniquely in
$n,a,b \ge 0$ subject to the boundary conditions
$$\leqalignno{
D(n,a,b)&= 0\ {\rm on}\ \{n=-1\}\cup\{a=-1\}
\cup\{b=-1\}\,;&(5.9)\cr
D(0,0,0)&=1.\cr}$$

\vskip 5pt
{\it Proof}\pointir
Consider a weighted bracketing $u=(w,t)$ in $U_{n,a,b}$
and write $w=x_1x_2\ldots x_n$. From (5.1) and (5.2)
it follows that
$\nu_n=\left|w\right|_{\kap}-\left|x_n\right|_{\kap}
 -\left|w\right|_{\revkap}-\left|x_n\right|_{\revkap}$
if $x_n=\kap$ or $\Oh$, i.e.,
$$\nu_n=\cases{a-b-1,&if $x_n=\kap$ ;\cr
a-b,&if $x_n=\Oh$.\cr}$$
In the same manner,
$\nu_n=\left|w\right|_{\kap}-\left|x_n\right|_{\kap}
- \left|w\right|_{\revkap}-\left|x_n\right|_{\revkap}-1$,\
if $x_n=\Khi$ or~$\revkap$, i.e.,
$$\nu_n=\cases{a-b-1,&if $x_n=\Khi$ ;\cr
a-b,&if $x_n=\revkap$.\cr}$$
Write $w'=x_1x_2\ldots x_{n-1}$, so that
$w=w'x_n$. Thus depending on the value of $x_n$ we
have in view of (5.6) :

if $x_n=\Oh$, then $w'\in U_{n-1,a,b}$ and
$\poids w=\poids w'.[a-b+1]_q$ ;

if $x_n=\kap$, then $w'\in U_{n-1,a-1,b}$ and
$\poids w=\poids w'.q^n[a-b]_q$ ;

if $x_n=\revkap$, then $w'\in U_{n-1,a,b-1}$ and
$\poids w=\poids w'.[a-b]_q $ ;

if $x_n=\Khi$, then $w'\in U_{n-1,a-1,b-1}$ and
$\poids w=\poids w'.q^n[a-b]_q$.

Summing $D(n,a,b)=\sum \poids(w'x_n)$ according
to the value of $x_n$ yields the desired
recurrence relation.\cqfd


%\input doron6


\titre 6. Another recurrence for the weighted
bracketings|
Our goal is to establish that $D(n,k,k)$ satisfies the ({\eightrm CARLITZ})
recurrence. A natural way is to find a recurrence
for $D(n,a,b)$ that will reduce to ({\eightrm CARLITZ}) on the
diagonal $a=b=k$. Unfortunately this is not true for
the recurrence of theorem~3. However 
the very fact that $D(n,a,b)$ satisfies some linear partial
recurrence equation with polynomial coefficients (in $q^n$, $q^a$,
$q^b$, $q$) is good news.
 
Most discrete functions $F(n,a,b)$ are not solutions of
any linear partial recurrence equation with polynomial coefficients.
However, those that are solutions of such equations, are
annihilated by a whole ideal of operators in the algebra
of linear operators with polynomial coefficients, i.e.,
are solutions of an infinite number of such equations
([Ze2], see also [Staf]).
All we have to do is to find the one that suits us.
A natural step therefore is to conjecture a partial
linear recurrence that will reduce to ({\eightrm CARLITZ}) upon
plugging $a=b=k$. Since $D(n-1,k-1,k)$ is zero, a reasonable
form would be:
$$\eqalign{
D(n,a,b)&=c_1(q^n,q^a,q^b,q) D(n-1,a,b) \cr
&\qquad{}
+c_2 (q^n,q^a,q^b,q) D(n-1,a-1,b-1)\cr              
&\qquad{}
+ c_3 (q^n, q^a, q^b, q) D(n-1,a-1,b),\cr}
\eqno\hbox{\eightrm (TRY)}$$
where $c_1$, $c_2$ should reduce to $[k+1]$ and $q^k [n-k]$ respectively
when $a=b=k$. By compiling a short table of $D(n,a,b)$ and
trying the generic form of linear polynomials $c_1$, $c_2$, $c_3$
as above, we easily obtained empirically that $D(n,a,b)$ satisfies
the recurrence of theorem 4  below, for small values of
$n$, $a$, $b$. All that remains to do is to prove it rigorously for
all values of $n$, $a$, $b$.

\th Theorem 4|The polynomials
$D(n,a,b)$ also satisfy the following recurrence,
for $n,a,b \ge 1$ :
$$\displaylines{D(n,a,b)=
[a+1]_q\, D(n-1,a,b)+q^a [n-b]_q\, D(n-1,a-1,b-1)
\hfill\cr
\hfill{} +
q^n [a-b]_q \, D(n-1,a-1,b).\quad\cr}$$
\finth

{\it Proof}\pointir
It is convenient to introduce operator
notation.  We refer the reader to [Ze] 
for the general methodology
of linear partial recurrence operators 
and its r\^ole in
combinatorics.  For any discrete function $F(n,a,b)$ let
$$\displaylines{{\cal N}^{-1} F(n,a,b) := F(n-1,a,b)\,;\qquad
{\cal A}^{-1} F(n,a,b) := F(n,a-1,b)\,;\cr
{\cal B}^{-1} F(n,a,b) := F(n,a,b-1).\cr}$$
Let $\cal P$ and $\cal R$ be the following
linear partial recurrence operators :
$$\displaylines{{\cal P}:=I-
[a-b+1]_q\, {\cal N}^{-1} (I+ {\cal B}^{-1} )
- q^n [a-b]_q\,
{\cal N}^{-1} {\cal A}^{-1} (I+ {\cal B}^{-1})\,;\cr
{\cal R}:=I- [a+1]_q\, {\cal N}^{-1}
- q^a [n-b]_q\, {\cal N}^{-1}
{\cal A}^{-1} {\cal B}^{-1}
- q^n [a-b]_q\, {\cal N}^{-1}
{\cal A}^{-1}.\cr}$$
In operator notation, theorems 3 and 4 can be paraphrased
as :

\th Theorem $3'$|We have the identity :
$${\cal P}(D(n,a,b))\equiv
\delta_{n,0} \delta_{a,0}\delta_{b,0}.$$
\finth
 
\th Theorem $4'$|We have the identity :
$${\cal R} (D(n,a,b)) \equiv 0\ {\it in}\ 
\{n,a,b\ge 1 \}.$$
\finth
 
We know that $D(n,a,b)$ is annihilated by a certain operator $\cal P$
in the region $\{n,a,b \ge 1\}$ and we want to prove that it is
also annihilated by the operator $\cal R$. A general algorithm
goes as follows.

Find the ``simplest" operator in the ideal 
generated by $\{ {\cal P},{\cal R} \}$,
i.e., find operators $\cal A$ and
$\cal B$ such that ${\cal Q}:={\cal AP}+{\cal BR}$
is ``as simple as possible." In particular,
if ${\cal Q}=0$ but $\cal A$ and $\cal B$ are not zero, 
than it is ideal (sic !).
Then, if necessary, try to use the method recursively
to prove that given that $\cal P$ annihilates $D(n,a,b)$, 
then so does~$\cal Q$. Assuming that we were successful 
in proving that ${\cal Q}(D(n,a,b))=0$,
we have 
$${\cal B}({\cal R}(D(n,a,b)))=-{\cal A}({\cal P}(D(n,a,b)))=0.$$ 
Then one proves
that ${\cal R}(D(n,a,b))=0$ on the boundary of the region of
interest. This would imply that ${\cal R}(D(n,a,b))\equiv 0$ 
throughout the region for the following reason.
 
For any ``reasonable"
linear recurrence operator $\cal B$ and any 
``reasonable" region,
$F(n,a,b)=0$ on the boundary (appropriately defined) 
of the region
and ${\cal B}( F(n,a,b)) =0$ in the interior of the 
region implies
that $F(n,a,b)\equiv 0$ throughout the region.
 
One way to find such $\cal A$ and $\cal B$ 
is to take successive commutators of
$\cal R$ and $\cal P$. In our case we were lucky, 
the commutator of 
$\cal P$ and $\cal R$
is zero, i.e., $\cal P$ and $\cal R$ commute ! 
(Note that
this  is a minor miracle, since the
algebra of linear partial recurrence 
operators with {\it variable} coefficients
is not commutative !) In other words, in the above
discussion ${\cal A}={\cal R}$, ${\cal B}=-{\cal P}$ and 
${\cal Q}=0$ works.

\vskip 5pt
{\it Proof of Theorem $4'$ (and hence of Theorem
$4$)}\pointir 
A tedious, but completely mechanical,
calculation shows that $\cal P$ and $\cal R$ commute.  
Now apply operator $\cal R$ to the identity of theorem
$3'$ : 
$${\cal R}({\cal P}\,D(n,a,b))
={\cal R}\,\delta_{n,0} \delta_{a,0}
\delta_{b,0}.$$ 
It is easily seen that the right side is zero at 
$\{n\ge 0, a \ge 0,\,b\ge 0 \}$ except for
$(n,a,b)=(0,0,0)$, $(1,0,0)$, $(1,1,0)$.  
Since
${\cal R}\,{\cal P}={\cal P}\,{\cal R}$, we then have 
$${\cal P}({\cal R}\,D(n,a,b)) \equiv 0\ {\rm in}\ 
\{n\ge 0, a \ge 0,\,b \ge 0 \} \setminus \{n=0,1\}.\leqno(6.1)$$
On the other hand, 
${\cal R} D(0,a,b)={\cal R} D(n,0,b)=0$,
except for $n=a=b=0$ by (5.8) and (5.9).
Moreover, when $b=0$, we have 
${\cal R}D(n,a,b)={\cal P}D(n,a,b)=\delta_{n,0}
\delta_{a,0}\delta_{b,0}$ by theorem~$3'$.
Hence
$$\displaylines{\rlap{(6.2)}\hfill
{\cal R}\,D(n,a,b)=0\ {\rm on}\ \{n=0\}
\cup \{a=0\}\cup\{b=0\}\setminus\{(0,0,0)\}.\hfill\cr
\noalign{\hbox{Now by (5.7)}}
\rlap{(6.3)}\hfill
D(1,a,b)= 0\qquad {\rm for}\ a+b\ge 2.\hfill\cr}$$  
Thus (6.2) and (6.3) imply that
${\cal R}\,D(n,a,b)$ is zero on the boundary of the region
$\{n\ge 1, a\ge 0,\,b\ge 0\}$. 
It follows
by induction, using (6.1), that ${\cal R}\,D(n,a,b) \equiv 0$ 
throughout the
region $\{n,a,b \ge 1 \}$.\cqfd 

Putting $a=b=k$ and using the fact that $D(n-1,k-1,k)\equiv 0$,
we see that $D(n,k,k)$ satisfies the same
recurrence ({\eightrm CARLITZ}) 
satisfied by the $B_{n,k}$.  Since
obviously $D(0,0,k)= \delta_{0,k}$, we have
proved, as a corollary, the following result
conjectured by Denert [De1] :

\th Corollary|For any $k,n\ge 0$ we have :
$D(n,k,k)=B_{n,k}(q)$.
\finth



\titre 7. Coding permutations by weighted bracketings|
Every permutation $\pi$ in ${\cal S}_n$ induces two partitions
of $\{1,2,3,\ldots,n\,\}$ : 
$F\cup G$ and $F'\cup G'$, such that
$\left|F'\right|=\left|F\right|$, 
$\left|G'\right|=\left|G\right|$, 
as well as two bijections $f:F\rightarrow F'$ and 
$g:G\rightarrow G'$,
that satisfy $i<f(i)$ for $i$ in $F$ and 
$i\ge g(i)$ for $i$ in~$G$.
Namely, $F$ is the excedence-place set 
$\{i_1,\ldots,i_k\,\}$, while
$G$ is its complement. Moreover 
$F'=\pi(F)$ and $G'=\pi(G)$. 
Finally, $f$ and $g$ are the
restrictions of $\pi$ to $F$ and $G$ 
respectively. Thus there is a
1-1 correspondence between ${\cal S}_n$ 
and the set of pairs of
bijections $(f:F\rightarrow F',\  g:G\rightarrow G')$ 
as above. Furthermore, by theorem~2,
$$\den\pi=\inv f+\inv g+ {\rm sum\ of\ elements\ of}\ F .
\leqno(7.1)$$
Let us fix the sets $F$ and $F'$ 
and let us consider the set of
bijections $f:F\rightarrow F'$ that satisfy $i<f(i)$ 
for every $i$ in~$F$. We
will represent such a mapping in terms of a {\it subscripted
angle parenthesizing} as follows.

Write all the integers $\{1,2,3,\ldots,n\}$ in a line.
For each $i$ in $F$ put a left angle parenthesis 
``$\langle$", also called a {\it langle} for short,
to the right of~$i$.
Analogously, for each~$j$ in~$F'$ put a right 
angle parenthesis, i.e., a {\it rangle}, 
``$\rangle$" to
the left of~$j$. For example, if $n=9$, $F=\{1,3,5\,\}$, and
$F'=\{5,7,9\,\}$, then the angle parenthesizing
corresponding to the pair
$(F,F')$ (observe that we have not introduced $f$ yet)~is :
$$1{\langle}\quad 2\quad 3{\langle}\quad 4\quad  
{\rangle}5{\langle}\quad 
6\quad {\rangle}7\quad 8\quad {\rangle}9 .$$
Note that there exists a bijection $f:F\rightarrow F'$
such that $i<f(i)$ for every $i$ in~$F$, 
iff the induced angle parenthesizing
is legal. Now to represent such a bijection~$f$, 
we indicate the fact $f(i)=j$ 
by having the rangle that lies after $i$ 
point to the langle
that lies before~$j$. 
For example, with $f(1)=7$, $f(3)=5$, $f(6)=9$, 
we have
$$\displaylines{
\noalign{\vskip 15pt }
1{\langle}\quad 2\quad 3{\langle}\quad 4\quad  
{\rangle}5{\langle}\quad 
6\quad {\rangle}7\quad 8\quad {\rangle}9.\cr}$$
The condition that $i<f(i)$ translates to the
requirement that every rangle should be 
matched with a certain langle to its left. 

\vskip 5pt
\noindent
(7.2) {\it Definition}\pointir
If a rangle belongs to the integer~$r$, 
denote by $\nu_r$ the difference 
between the number of langles
and the number of rangles that lie to the left
of~$r$. [Note that the rangle belonging
to~$r$ is counted in the difference.]

\vskip 5pt
As each rangle can be matched with
a langle to its left, we have $\nu_r\ge 0$.
%Call $\nu_r$
%the {\it maximal rank} of~$r$.
If $r$ is the $i$-th integer
that possesses a rangle (when
$1,2,\ldots,n$ is read from left to right),
we label it $r_i$.
In the previous example,
$r_1=5$, $r_2=7$, $r_3=9$, and
$\nu_5=1$, $\nu_7=1$, $\nu_9=0$.

Next let us label all the langles to the left
of the first rangle 0, 1, \dots, $\nu_{r_1}$
when reading them from left to right.
If the arrow pointing to this first
rangle comes from a langle labeled, say,
$t_{r_1}$, give the first rangle the
{\it rank}~$t_{r_1}$. The langle labeled
$t_{r_1}$ will then be called {\it committed}. Next
erase this first labeling and relabel
0, 1, \dots, $\nu_{r_2}$ the {\it uncommitted} langles
to the left of the second rangle. If the
arrow pointing to this second rangle comess
from a langle labeled~$t_{r_2}$, give the 
second rangle the rank~$t_{r_2}$. Furthermore,
declare the langle labeled~$t_{r_2}$ committed
and erase this second labeling.
Continue this procedure until the last
rangle is reached and ranked. 
With the previous example, the letter $c$ meaning
``committed," we have :
 $$\displaylines{
\noalign{\vskip 15pt }
\vcenter{
\halign{#\hfil\quad &&$\quad \hfil#\hfil\ $\cr
&1{\langle}&2&3{\langle}&4&{\rangle}5{\langle}&
6&{\rangle}7&8&{\rangle}9\cr
label&0&&1\cr
rank&&&&&{\bf 1}\cr
label&0&&c&&1\cr
rank&&&&&&&{\bf 0}\cr
label&c&&c&&0\cr
rank&&&&&&&&&{\bf 0}\cr}}\cr}$$
So the final output for $f$ is the following
{\it subscripted angle parenthesizing}
$$1{\langle}\quad 2\quad 3{\langle}\quad 4\quad  
{\rangle}_1 5{\langle}\quad 
6\quad {\rangle}_0 7\quad 8\quad {\rangle}_0 9.\leqno(7.3)$$

It is easy to see that the sequence of rangle ranks
is nothing but the {\it left to right
inversion table} of~$f$. With the same example we have :
$$\eqalign{
f&=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
1&3&5\cr
7&5&9\cr}}\right)\cr
{\rm inversion\ table}&=
\hskip 8pt
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
0&1&0\cr}}\cr}$$

We will now subject the
bijection $g:G\rightarrow G'$ 
%such that $g(i)\le i$. 
to an analogous treatment. To distinguish it from
the former case, we will use square brackets 
``[" and ``]", later referred to as {\it lbracks} 
and {\it rbracks}. Now each element of $G'$ 
receives an lbrack {\it immediately before} it, while
each element of $G$ receives an rbrack {\it right after}.
With the above $F$ and $F'$ we are forced to have
$G=\{2,4,6,7,8,9\,\}$ and $G'=\{1,2,3,4,6,8\,\}$. 
The bracketing corresponding to this pair $(G,G')$ 
is then :
$${[}1\quad {[}2{]}\quad {[}3\quad {[}4{]}\quad 5\quad 
{[}6{]}\quad 7{]}\quad {[}8{]}\quad  9].$$
To represent $g$ we make each point
$j=g(i)$ point to~$i$.
For example if
$g(2)=1$, $g(4)=4$, $g(6)=2$, $g(7)=6$, $g(8)=3$, $g(9)=8$, 
we get :
$$\displaylines{
\noalign{\vskip 15pt }
{[}1\quad {[}2{]}\quad {[}3\quad {[}4{]}\quad 5\quad 
{[}6{]}\quad 7{]}\quad {[}8{]}\quad  9].\cr}$$

\vskip 5pt
\noindent
(7.4) {\it Definition}\pointir
If an lbrack belongs to the integer~$s$, 
denote by $\nu_s$ the difference 
between the number of rbracks
and the number of lbracks that lie to the right of
$[s$ of the bracketed word. 
[In this difference we include
the lbrack and the rbrack (if any) belonging
to~$s$.]

\vskip 5pt
When $1,2,\ldots,n$ is scanned from right
to left, the integers that possess an
lbrack are denoted by $s_1$, $s_2$, \dots\ 
In the previous example we have :
$s_1=8$, $s_2=6$, $s_3=4$, $s_4=3$,
$s_5=2$, $s_6=1$, and
$\nu_8=1$, $\nu_6=2$, $\nu_4=2$,
$\nu_3=1$, $\nu_2=1$, $\nu_1=0$.

The ranking on the lbracks is defined
in the same way as the ranking on the langles
with the major difference that the word
1, 2, \dots, $n$ is now scanned from
{\it right to left}. The rbracks to the right
of the lbrack $s_1$ belonging to $s_1$ are labeled 
0, 1, \dots, $\nu_{s_1}$
when reading them from right to left.
If the arrow going out of that lbrack
points to an rbrack labeled, say,
$t_{s_1}$, give the lbrack belonging to $s_1$ the
{\it rank}~$t_{s_1}$. The rbrack labeled
$t_{s_1}$ is now {\it committed}. Next
erase this first labeling and relabel
0, 1, \dots, $\nu_{s_2}$ the {\it uncommitted} rbracks
to the right of~$s_2$. If the
arrow going out of the lbrack
belonging to $s_2$ points to
an rbrack labeled~$t_{s_2}$, give the lbrack
belonging to $s_2$ the rank~$t_{s_2}$. Furthermore,
declare the rbrack labeled~$t_{s_2}$ committed
and erase this second labeling.
Continue this procedure until the last
lbrack is reached and ranked. 
With the previous example
 $$\displaylines{
\noalign{\vskip 15pt }
\vcenter{
\halign{#\hfil\ &&$\ \hfil#\hfil\ $\cr
&{[}1&{[}2{]}&{[}3&{[}4{]}&5&
{[}6{]}&7{]}&{[}8{]}& 9]\cr
label&&&&&&&&1&0\cr
rank&&&&&&&&{\bf 0}&\cr
label&&&&&&2&1&0&c\cr
rank&&&&&&{\bf 1}&&&\cr
label&&&&2&&1&c&0&c\cr
rank&&&&{\bf 2}&&&&&\cr
label&&&&c&&1&c&0&c\cr
rank&&&{\bf 0}&&&&&&\cr
label&&1&&c&&0&c&c&c\cr
rank&&{\bf 0}&&&&&&&\cr
label&&0&&c&&c&c&c&c\cr
rank&{\bf 0}&&&&&&&&\cr
}}\cr}$$
The final output for $g$ is the following
{\it subscripted bracketing}
$${[}_0 1\quad {[}_0 2{]}\quad {[}_0 3\quad 
{[}_2 4{]}\quad 5\quad 
{[}_1 6{]}\quad 7{]}\quad {[}_0 8{]}\quad  9].
\leqno(7.5)$$
It is readily seen that the sequence of subscripts
is nothing but the {\it right to left
inversion table} of~$g$. 

With the same example we have :
$$\eqalign{
g&=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
2&4&6&7&8&9\cr
1&4&2&6&3&8\cr}}\right)\cr
{\rm right\ to\ left\ inversion\ table}&=
\hskip 8pt
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
0&2&0&1&0&0\cr}}\cr}$$

Consider a typical permutation $\pi$ in ${\cal S}_n$. The
excedence part, materialized by $f$, 
corresponds to a subscripted angle parenthesizing, 
where the subscripted are on the rangles. The
non-excedence part, described by $g$ 
corresponds to a subscripted bracketing, where the 
subscripts are on the lbracks. 
As each integer from 1 to~$n$ belongs to exactly
one of the four subsets
$F\cap F'$, $F\cap G'$, $F'\cap G$, $G\cap G'$,
it possesses exactly one of the four pairs :
$$\Khi,\quad
\kap,\quad
\revkap,\quad
\Oh,\leqno(7.6)$$
that we now consider as real letters
as in section~5.
However only the {\it rangles} and the {\it lbracks}
are subscripted. Accordingly, each 
symbol listed in (7.6) is given one and only one
subscript, when the angle parenthesizing and the
bracketing are superimposed on the sequence
$1,2,\ldots,n$. 
If we write the subscripts as a separate word
$t=t_1t_2\ldots t_n$, we see that
each permutation or order~$n$
corresponds to a pair $u=(w,t)$,
where $w$ is a word $w=x_1x_2\ldots x_n$ in
the four-letter alphabet (7.6) and 
$t=t_1t_2\ldots t_n$ is a sequence of
positive integers satisfying
$0\le t_r\le \nu_r$ for all
$r=1,2,\ldots,n$.

As both angle parenthesizing and bracketing 
are legal, the word $w$ is also {\it legal},
as was defined in the beginning of section~5.

Now as $F$ has $k$ elements $i_1$, $i_2$,
\dots, $i_k$, the word $w$ has exactly $k$
letters equal to $\kap$ or $\Khi$
and $k$ letters equal to $\revkap$ or $\Khi$.
Hence, $w$ belongs to $W_{n,k,k}$, as defined
in~(5.2).

After superimposition the rangles occur in
the symbols $\revkap$ and $\Khi$. If $r$
possesses a rangle, the letter $x_r$
is either $\revkap$ or $\Khi$. Hence,
definition (7.2) implies
$$\eqalign{\nu_r&=\left|x_1\ldots x_r\right|_{\kap}
+\left|x_1\ldots x_r\right|_{\Khi}
-\left|x_1\ldots x_r\right|_{\revkap}
-\left|x_1\ldots x_r\right|_{\Khi}-1\cr
&=\left|x_1\ldots x_{r-1}\right|_{\kap}
-\left|x_1\ldots x_{r-1}\right|_{\revkap}-1,\cr}$$
which agrees with the definition of $\nu_r$ 
given in~(5.2).

In the same manner, if $s$ possesses an lbrack,
then $x_s=\kap$ or $\Khi$. Hence, by definition (7.4)
$$\eqalign{\nu_s&=\left|x_s\ldots x_n\right|_{\revkap}
+\left|x_s\ldots x_n\right|_{\Khi}
-\left|x_s\ldots x_n\right|_{\kap}
-\left|x_s\ldots x_n\right|_{\Khi}\cr
&=\left|x_1\ldots x_{s-1}\right|_{\kap}
-\left|x_1\ldots x_{s-1}\right|_{\revkap},\cr}$$
since $\left|w\right|_{\kap}
=\left|w\right|_{\revkap}$. Again this
agrees with (5.2). Hence
$$u=(w,t)\in U_{n,k,k}.\leqno(7.7)$$
Furthermore, the elements of $F$ are those
that possess a langle. Accordingly, 
$$F=\{i;\,x_i=\kap\ {\rm or}\ \Khi\ \}
=\{i_1,i_2,\ldots,i_k\,\} .\leqno(7.8)$$

Finally, let $p$ be
the juxtaposition product of the inversion
table of $f$ and the left to right inversion
table of $g$. As the word $t$ is a rearrangement
of the word $p$, we have :
$$\inv f+ \inv g=t_1+t_2+\cdots +t_n.\leqno(7.9)$$
It then follows from (7.1), (7.8) and (7.9) that
$$
\den\pi=i_1+i_2+\cdots+i_k+t_1+t_2+\cdots +t_n,
\leqno(7.10)$$
i.e., $\den\pi=\ind u$, by (5.5).
Clearly each step in the construction can
be reversed. We have just
proved the following theorem.

\th Theorem 5|For each 
$k=0,1,\ldots,(n-1)$ the above construction
sets up a bijection $\pi\mapsto u$
between the set
${\cal S}_{n,k}$ of the permutations
having $k$ excedences and the set $U_{n,k,k}$
of the weighted bracketings 
having exactly $k$ letters equal
to $\kap$ or $\Khi$ and $k$
letters equal to $\revkap$ or $\Khi$.

Furthermore, if $u=(w,t)$
with $w=x_1x_2\ldots x_n$ and
$t=t_1t_2\ldots t_n$, then
$$\leqalignno{
\den\pi&=\ind u,&(7.11)\cr
\noalign{\hbox{and so}}
q^{\den\pi}&=\poids u.\cr}$$
\finth

By theorem 5 we have
$$\eqalign{\sum_\pi q^{\den\pi}
&=\sum_u \poids u\qquad 
(\pi\in{\cal S}_n,\,\exc\pi=k\,;\ u\in U_{n,k,k})\cr
&=D(n,k,k)=B_{n,k}(q),\cr}$$
by the corollary of section~5.
This then proves theorem~1.

\rem Epilogue|
The construction of the bijection 
$\pi\mapsto u$ can be summarized
and illustrated as follows :

(i) start with a permutation, e.g.,
$$\pi=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
1&2&3&4&5&6&7&8&9\cr
7&1&5&4&9&2&6&3&8\cr}}\right).$$

(ii) determine the excedence place set
$F=\{i_1,\ldots,i_k\}$ and the non-excedence\
place set $G=\{j_1,\ldots,j_{n-k}\}$ ; here
$F=\{1,3,5\,\}$, and $G=\{2,4,6,7,8,9\,\}$.

(iii) set up the bijections $f:F\rightarrow F'$
and $g:G\rightarrow G'$ and determine the
inversion table
$p_{f(i_1)}\ldots p_{f(i_k)}$ for
$f(i_1)\ldots f(i_k)$ 
and the right to left inversion table
$p_{g(j_1)}\ldots p_{g(j_{n-k})}$ for
$g(j_1)\ldots g(j_{n-k})$. Here 
$$\eqalign{
f&=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
1&3&5\cr
7&5&9\cr}}\right)\cr
p_f&=
\hskip 8pt
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
0&1&0\cr}}\cr}
\qquad
\eqalign{
g&=\left(
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
2&4&6&7&8&9\cr
1&4&2&6&3&8\cr}}\right)\cr
p_g&=
\hskip 8pt
\vcenter{
\halign{&$\ \hfil#\hfil\ $\cr
0&2&0&1&0&0\cr}}\cr}$$

\goodbreak
(iv) form the words
$w=x_1\ldots x_n$ and $t=t_1\ldots t_n$
as follows :

\noindent
if $c\in F\cap F'$, let $x_c=\Khi$, $t_c=p_c$ ;
if $c\in F'\cap G$, let $x_c=\revkap$, $t_c=p_c$ ;

\noindent
if $c\in F\cap G'$, let $x_c=\kap$, $t_c=p_c$ ;
if $c\in G\cap G'$, let $x_c=\Oh$, $t_c=p_c$.

Here
$$\vcenter{
\halign{$#={}$\quad&&$\ \hfil#\hfil\quad $\cr
w&\kap&\Oh&\kap&\Oh&\Khi&\Oh&\revkap&\Oh&\revkap\cr
t&0&0&0&2&1&1&0&0&0\cr}}$$





\titre 8. Another Mahonian mate for the number of descents|
 
We have just seen that there is a natural bijection between weighted
(complete) bracketings and permutations, and used the latter to
prove Denert's conjecture.  However, in order to prove the conjecture,
we had to colonize the more general set of incomplete bracketings,
in which in general there are more left parentheses than right
parentheses. Unfortunately, the bijection does not seem
to extend, and it is not at all clear what are the permutation
counterparts of incomplete bracketings.  In this final section, we
will introduce another bijection, for which incomplete bracketings
correspond to so-called {\it gravid permutations}.  This, in turn,
will induce another Mahonian statistic, mak,
on gravid permutations,
and in particular, on regular permutations.  By theorem 5, we then
know right away that the pair $(\des,\mak)$ is also
Euler-Mahonian.
 
A {\it gravid permutation} of order $n$ 
is a usual permutation of order~$n$ with one or more
$\infty$ symbols inserted in the middle, 
such that there are {\it never
two consecutive} infinities, 
and there is always an $\infty$ at the end.
The class of regular permutations is in 1-1 correspondence with
gravid permutations that only have a single infinity, that is
necessarily at the end.  For example
$\sigma=6, 3, 1, \infty, 4, \infty, 2, 5, \infty$ 
is a gravid permutation with
$n=6$ and 3 infinities.
 
Clearly a gravid permutation of order $n$ has at
most $(n+1)$ infinities and at most $n$ descents.
We denote by $G_{n,l,k}$ the set of
gravid permutations of order~$n$ with $l$ infinities
and $k$ descents. Then $G_{n,l,k}$ is empty, unless
$1\le l\le n+1$ and $l-1\le k\le n$.

Let $\sigma=\sigma(1)\sigma(2)\ldots \sigma(n+l)$ be a gravid
permutation of order~$n$ with $l$ infinities. 
Let $1\le i\le n+l$ ; if either
$i=1$ and $\sigma(1)>\sigma(2)$, or
$2\le i\le n+l-2$ and $\sigma(i-1)<\sigma(i)>\sigma(i+1)$,
we say that $i$ is a {\it peak-place} and
$\sigma(i)$ a {\it peak-letter}.
In the same manner, if $2\le i\le n+l-1$ 
and $\sigma(i-1)>\sigma(i)<\sigma(i+1)$,
we say that $i$ is a {\it trough-place} and
$\sigma(i)$ a {\it trough-letter}.
If $2\le i\le n+l-1$ and $\sigma(i-1)>\sigma(i)$,
we say that $(i-1)$ is a {\it descent-place}
and $\sigma(i)$ is a {\it descent bottom value}.
The letter $\sigma(i-1)$ would be the
the {\it descent top value}, but the notion will not
be used here.

When read from left to right the gravid permutation
$\sigma$ has a succession of peak and trough places, say,
$\pk_1, \tr_1, \pk_2, \tr_2, \ldots$. If $\sigma(f_m)$ 
is the $m$-th
letter of $\sigma$ that is not equal to $\infty$,
we denote by $t_m$ the number of pairs 
$(\sigma(\pk_j),\sigma(\tr_j))$
{\it to the left of} $\sigma(f_m)$ such that
$$\sigma(\pk_j)>\sigma(f_m)>\sigma(\tr_j).\leqno(8.1)$$
Now if $i_1$, $i_2$, \dots , $i_k$ are the
{\it descent bottom values} of $\sigma$,
the {\it mak}-statistic of $\sigma$ is defined by :
$$\mak\sigma:=i_1+i_2+\cdots+i_k
+t_1+t_2+\cdots+t_n.\leqno(8.2)$$
This definition is to be compared with the definition
of $\den$ recalled in (7.10).

For the following gravid permutation we have :
$$\vbox{
\halign{\hfil$#$&$#$&&$\ \hfil#\hfil\ $\cr
i&{}={}&1&2&3&4&5&6&7&8&9\cr
\sigma(i)&{}={}&6&3&1&\infty&4&\infty&2&5&\infty\cr
(i_1,\ldots,i_k)&{}={}&
&3&1&&4&&2&&\cr
(t_1,\ldots,t_n)&{}={}&
0&0&0&&1&&1&3&\cr}}$$
so that $\mak\sigma=3+1+4+2+1+1+3=15$.

As in the previous sections we denote by
$U_{n,a,b}$ the set of the weighted bracketings $u=(w,t)$, where
$w$ has exactly $a$ letters equal to
$\kap$ or $\Khi$, and $b$ letters equal to $\Khi$ or $\revkap$,
and where $0\le t_r\le \nu_r$ $(1\le r\le n)$.

We now define a bijection $B$ between $U_{n,a,b}$ and
$G_{n,b-a+1,b}$, by recursion, as follows. The map
$B$ applied to the empty word is the gravid permutation
$\infty$ of $G_{0,1,0}$.  Let
$u=(w,t)$ be a typical pair in $U_{n,a,b}$.  Let
$x_n$ be the last letter of $w$, and $t_n$ the last
component of $t$, and let $w'$ and $t'$ be the words 
obtained by chopping the last letters from $w$ and
$t$ respectively : i.e., $w= w' x_n$, $s= s' t_n$.
Let $\sigma' := B( w',t')$ be the gravid
permutation assumed to be obtained by induction.
We now define $\sigma := B(w,t)$
in the following manner :

\vskip 5pt 
Case I : $x_n = \kap$.  Let $\sigma$ be the permutation
obtained from $\sigma '$ by inserting the
two-letter word $ n \infty $ right after
the $(t_n+1)$-st infinity.
 
Case II : $ x_n =\revkap$.  Let $\sigma  $ be the permutation
obtained from $\sigma'$ by replacing the $(t_n+1)$-st
infinity by~$n$.
 
Case III : $x_n = \Oh$.  Let $\sigma  $ be the permutation
obtained from $\sigma'$ by inserting $ n $ right before
the $(t_n+1)$-st infinity.
 
Case IV : $x_n = \Khi$.  Let $\sigma  $ be the permutation
obtained from $\sigma'$ by inserting $ n $ right after
the $(t_n+1)$-st infinity.

\goodbreak
\rem Example|
The construction of $B$ is illustrated as follows :

$$\vbox{
\halign{\hfil$#$&$#$&&$\ \hfil#\hfil\ $\cr
i&{}={}&1&2&3&4&5&6\cr
w&{}={}&\kap&\kap&\Khi&\kap&\Oh&\revkap\cr
t&{}={}&0&1&0&1&3&0\cr}
\vskip 5pt 
\halign{\hfil$#$&$#\qquad$&&$\ \hfil#\hfil\ $\cr
\empty&&\infty\cr
x_1=\kap\,;\;t_1=0\,;&&\infty&1&\infty\cr
x_2=\kap\,;\;t_2=1\,;&&\infty&1&\infty&2&\infty\cr
x_3=\Khi\,;\;t_3=0\,;&&\infty&3&1&\infty&2&\infty\cr
x_4=\kap\,;\;t_4=1\,;&&\infty&3&1&\infty&4&\infty&2&\infty\cr
x_5=\Oh\,;\;t_5=3\,;&&\infty&3&1&\infty&4&\infty&2&5&\infty\cr
x_6=\revkap\,;\;t_6=0\,;&&6&3&1&\infty&4&\infty&2&5&\infty\cr
}}$$
Hence $\sigma=6,3,1,\infty,4,\infty,2,5,\infty$.
Furthermore, $u\in U_{6,4,2}$, $\sigma\in G_{6,4,3}$
and $\ind u=(1+2+3+4)+1+1+3=15$,
that agrees with $\den\sigma$ calculated above.

 
\th Theorem 6|The map $B:u\mapsto \sigma$ is
a bijection of $U_{n,a,b}$ onto
$G_{n,b-a+1,b}$ having the following property
$$\ind u=\mak\sigma.\leqno(8.3)$$
\finth

\th Corollary|The map $B$ sends each set $U_{n,a,a}$
of weighted complete bracketings onto the
set $G_{n,a}=G_{n,1,a}$ of the permutations
of order~$n$ having $a$ descents in such
a way that $(8.3)$ holds.
\finth

{\it Proof}\pointir
It is easy to prove that this bijection is well defined,
and that it is indeed a bijection, by writing down explicitly the
inverse bijection $B^{-1}$ and proving that it is also well
defined. We do not give the details. However we should
like to make some comments about the mak-statistic. 

In the construction of $B$ we see that 
$x_n$ is a descent bottom value whenever
$x_n=\kap$ or $\Khi$ (cases I and IV)
and remains so for the further insertions.
On the other hand, $x_n$ has exactly
$t_n$ infinity symbols to its left,
if and only if $x_n$ has exactly
$t_n$ pairs $(\infty,\hbox{\rm trough-letters})$ to its left.
All those trough-letters are less than $x_n$
and if for the further insertions
some $\infty$'s are replaced by integers
(case~II), the pairs 
$(\infty,\hbox{\rm trough-letters})$
will be replaced by, say, 
$(\sigma(\pk_j),\sigma(\tr_j))$ that satisfy
$\sigma(\pk_j)>x_m>\sigma(\tr_j)$. Thus (8.1) holds.\cqfd


Theorem 6 translates, via the bijection $B$, to the following
theorem
 
 
\th Theorem 7|The pair of permutation statistics
$(\des,\mak)$, on regular permutations, is Euler-Mahonian.
\finth

\titre Tables|
In the first table we give the list of the
polynomials $D(n,a,b)$ up to $n=6$.

\vskip 5pt
The second table illustrates, for $n=4$, the
construction of the first bijection
$\pi\mapsto u$ (of section~7). We found it
convenient to list the weighted paths
instead of the weighted bracketings.
Recall that we have the correspondence :
$\hbox{\eightrm NE}\leftrightarrow \kap$,
${\rm blue}\leftrightarrow \Oh$,
${\rm red}\leftrightarrow \Khi$,
$\hbox{\eightrm SE}\leftrightarrow \revkap$.

The second bijection (section 8) $u\mapsto \pi'$
is described in the fourth and fifth columns.
The rightmost column simply contains
the major index $\maj\pi'$ of~$\pi'$.

\vfill\eject



\eightpoint

\def\add{\mathord {+}}

\newbox\dun
\newbox\ddeux
\newbox\dtrois
\newbox\dquatre
\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\dun=\vbox{\offinterlineskip %\eightpoint
\halign{\tv\thinspace\hfil$#$\thinspace&\tv#&
\thinspace\hfil$#$\hfil\thinspace\tv\cr
\multispan3\strut\hfil$n=1$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&0\cr
\noalign{\hrule}
a{=}0&&1\cr
\omit\ttv\hfil&\multispan2\hrulefill\cr
1&& q\cr
\noalign{\hrule}
}} 



\setbox\ddeux=\vbox{\offinterlineskip %\eightpoint
\halign{\tv\thinspace\hfil$#$\thinspace&\tv#&&
\thinspace\hfil$#$\hfil\thinspace\tv\cr
\multispan4\strut\hfil$n=2$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&0&1\cr
\noalign{\hrule}
a{=}0&&1&\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
1&&(2 q \add  1) q& q\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
2&&(q\add 1) q^3&q^3\cr
\noalign{\hrule}
}} 



 

\setbox\dtrois=\vbox{\offinterlineskip %\eightpoint
\halign{\tv\thinspace\hfil$#$\thinspace&\tv#&&
\thinspace\hfil$#$\hfil\thinspace\tv\cr
\multispan5\strut\hfil$n=3$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&0&1&2\cr
\noalign{\hrule}
a{=}0&&1&&\cr
\omit\ttv\hfil&\multispan4\hrulefill\cr
1&&(3 q^2  \add  3 q \add  1) q& 2 (q \add  1) q&\cr
\omit\ttv\hfil&\multispan4\hrulefill\cr
2&&(3 q^3\add 5q^2  \add  3 q \add  1) q^3&(3 q^2  \add  5 q \add  2)
q^3&q^3\cr \omit\ttv\hfil&\multispan4\hrulefill\cr
3&&(q^2  \add  q \add  1)(q \add  1)  q^6&(q \add  2) (q \add  1) q^6&q^6\cr
\noalign{\hrule}
}} 



\setbox\dquatre=\vbox{\offinterlineskip %\eightpoint
\halign{\tv\thinspace\hfil$#$\thinspace&\tv#&&
\thinspace\hfil$#$\hfil\thinspace\tv\cr
\multispan6\strut\hfil$n=4$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&0&1&2&3\cr
\noalign{\hrule}
a{=}0&&1&&&\cr                  
\omit\ttv\hfil&\multispan5\hrulefill\cr
1&&(4q^3\add 6q^2\add 4q\add 1)q&(3q^2\add 5q\add 3)q&&\cr
\omit\ttv\hfil&\multispan5\hrulefill\cr
2&&(6q^5\add 14q^4\add 15q^3\add 10q^2\add 4q\add 1)q^3&
(6q^4\add 16q^3\add 19q^2\add 11q\add 3)q^3&
(3q^2\add 5q\add 3)q^3&\cr
\omit\ttv\hfil&\multispan5\hrulefill\cr
3&&(4q^6\add 11q^5\add 16q^4\add 15q^3\add 9q^2\add 4q\add 1)q^6&
(4q^5\add 15q^4\add 25q^3\add 22q^2\add 11q\add 3)q^6&
(4q^3\add 9q^2\add 9q\add 3)q^6&q^6\cr
\omit\ttv\hfil&\multispan5\hrulefill\cr
4&&(q^3\add q^2\add q\add 1)(q^2\add q\add 1)(q\add 1)q^{10}&
(q^2\add 2q \add 3)(q^2\add q\add 1)(q\add 1)q^{10}&
(q^2\add 3q \add 3)(q\add 1)q^{10}&
q^{10}\cr
\noalign{\hrule}
}}

\tenpoint
\centerline{\bf Table of $\bf D(n,a,b)$ for 
$\bf 0\le b\le a\le n=6$}

\eightpoint
\vfill
\centerline{\box\dun\quad\box\ddeux\quad\box\dtrois}
\vfill
\centerline{\box\dquatre}
\vfill



\newbox\strotbox
\setbox\strotbox=\hbox{\vrule height 10pt depth 3pt width 0pt }
\def\strot{\relax\ifmmode\copy\strotbox\else\unhcopy\strotbox\fi}

\newbox\stritbox
\setbox\stritbox=\hbox{\vrule height 8pt depth 3pt width 0pt }
\def\strit{\relax\ifmmode\copy\strotbox\else\unhcopy\stritbox\fi}




\newbox\dcinq

%\def\add{\mathord {+}}
%\let\add=+

%\newbox\ttvbox

%\setbox\ttvbox\hbox{\vrule height .4pt depth 0pt }
%\def\ttv{\relax\ifmmode\copy\ttvbox\else\unhcopy\ttvbox\fi}



\setbox\dcinq=\vbox{\offinterlineskip 
\halign{\strot\vrule\thinspace\hfil$#$\thinspace&\vrule#&&
\thinspace\vtop{\hsize=6.5cm \noindent
\strit#\strit
}\thinspace\vrule\cr
\multispan4\strut\hfil$n=5$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&\omit\hfil 0\hfil\vrule&\omit\hfil 1\hfil\vrule\cr
\noalign{\hrule}
a{=}0&&1&\cr                  
\omit\ttv\hfil&\multispan3\hrulefill\cr
1&&$(5q^4+10q^3+10q^2+5q+1)q$&
$(4q^3+9q^2+9q+4)q$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
2&&
$(10q^7+30q^6+45q^5+44q^4+30q^3+15q^2+5q+1)q^3$&
$(10q^6+35q^5+60q^4+64q^3+44q^2+19q+4)q^3$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
3&&
$(10q^9+35q^8+66q^7+85q^6
+80q^5+59q^4+34q^3+15q^2+5q+1)q^6$&
$(10q^8+45q^7+101q^6+146q^5
+146q^4+105q^3+54q^2+19q+4)q^6$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
4&&
$(5q^{10}+19q^9+40q^8+61q^7
+71q^6+66q^5+49q^4+29q^3+14q^2+5q+1)q^{10}$&
$(5q^9+24q^8+64q^7+115q^6+146q^5
+137q^4+96q^3+50q^2+19q+4)q^{10}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
5&&
$(q^4+q^3+q^2+q+1)(q^3+q^2+q+1)
(q^2+q+1)(q+1)q^{15}$&
$(q^3+2q^2+3q+4)(q^3+q^2+q+1)
(q^2+q+1)(q+1)q^{15}$\cr
\noalign{\hrule}
}}

\centerline{\box\dcinq}
\vfill

\newbox\dcinqb

\setbox\dcinqb=\vbox{\offinterlineskip 
\halign{\strot\vrule\thinspace\hfil$#$\thinspace&\vrule#&
\thinspace\hfil#\hfil\thinspace\vrule&
\thinspace\hfil#\hfil\thinspace\vrule&
\thinspace\hfil#\hfil\thinspace\vrule\cr
\multispan5\strut\hfil$n=5$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&2&3&4\cr
\noalign{\hrule}
a{=}2&&$2(3q^4+8q^3+11q^2+8q+3)q^3$&&\cr
\omit\ttv\hfil&\multispan4\hrulefill\cr
3&&
$(10q^6+35q^5+66q^4+76q^3+57q^2+26q+6)q^6$&
$(4q^3+9q^2+9q+4)q^6$&\cr
\omit\ttv\hfil&\multispan4\hrulefill\cr
4&&
$(5q^7+24q^6+59q^5+89q^4+90q^3+61q^2+26q+6)q^{10}$&
$(5q^4+14q^3+19q^2+14q+4)q^{10}$&
$q^{10}$\cr
\omit\ttv\hfil&\multispan4\hrulefill\cr
5&&
$(q^4+3q^3+7q^2+8q+6)(q^2+q+1)(q+1)q^{15}$&
$(q^3+4q^2+6q+4)(q+1)q^{15}$&
$q^{15}$\cr
\noalign{\hrule}
}}


\centerline{\box\dcinqb}

\vfill
\eject





%\input a4
%\eightpoint

%\newbox\strotbox
%\setbox\strotbox=\hbox{\vrule height 10pt depth 3pt 
%width 0pt }
%\def\strot{\relax\ifmmode\copy\strotbox\else\unhcopy\strotbox\fi}


%\def\add{\mathord {+}}
%\let\add=+

%\newbox\ttvbox

%\setbox\ttvbox\hbox{\vrule height .4pt depth 0pt }
%\def\ttv{\relax\ifmmode\copy\ttvbox\else\unhcopy\ttvbox\fi}

\newbox\dsix

\setbox\dsix=\vbox{\offinterlineskip 
\halign{\strot\vrule\thinspace\hfil$#$\thinspace&\vrule#&&
\thinspace\vtop{\hsize=6.5cm \noindent \normalbaselineskip=11pt
\strut#\strit}\thinspace\vrule\cr
\multispan4\strut\hfil$n=6$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&\omit\hfil 0\hfil\vrule&\omit\hfil
1\hfil\vrule\cr 
\noalign{\hrule}
a{=}0&&1&\cr                  
\omit\ttv\hfil&\multispan3\hrulefill\cr
1&&
$(6q^5+15q^4+20q^3+15q^2+6q+1)q$&
$(5q^4+14q^3+19q^2+14q+5)q$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
2&&
$(15q^9+55q^8+105q^7+134q^6
+125q^5+90q^4+50q^3+21q^2+6q+1)q^3$&
$(15q^8+64q^7+139q^6+198q^5
+203q^4+153q^3+83q^2+29q+5)q^3$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
3&&
$(20q^{12}+85q^{11}+196q^{10}+315q^9
+385q^8+379q^7+308q^6+209q^5
+119q^4+56q^3+21q^2+6q+1)q^6$&
$(20q^{11}+105q^{10}+286q^9+526q^8
+721q^7+770q^6+653q^5+442q^4
+237q^3+98q^2+29q+5)q^6$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
4&&
$(15q^{14}+69q^{13}+175q^{12}+321q^{11}
+462q^{10}+547q^9+545q^8+464q^7
+342q^6+218q^5+119q^4+55q^3+21q^2+6q+1)q^{10}$&
$(15q^{13}+84q^{12}+259q^{11}+560q^{10}
+922q^9+1204q^8+1279q^7+1122q^6
+819q^5+497q^4+247q^3+98q^2+29q+5)q^{10}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
5&&
$(6q^{15}+29q^{14}+78q^{13}+154q^{12}
+245q^{11}+328q^{10}+377q^9+377q^8
+330q^7+253q^6+169q^5+98q^4+49q^3+20q^2+6q+1)q^{15}$&
$(6q^{14}+35q^{13}+113q^{12}+267q^{11}
+497q^{10}+750q^9+938q^8+985q^7
+874q^6+656q^5+414q^4+218q^3+93q^2+29q+5)q^{15}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
6&&
$(q^5+q^4+q^3+q^2+q+1)(q^4+q^3+q^2+q+1)
(q^3+q^2+q+1)(q^2+q+1)(q+1)q^{21}$&
$(q^4+2q^3+3q^2+4q+5)(q^4+q^3+q^2+q+1)
(q^3+q^2+q+1)(q^2+q+1)(q+1)
q^{21}$\cr
\noalign{\hrule}
}}

\centerline{\box\dsix}

\vskip 1cm


\newbox\dsixa

\setbox\dsixa=\vbox{\offinterlineskip 
\halign{\strot\vrule\thinspace\hfil$#$\thinspace&\vrule#&&
\thinspace\vtop{\hsize=6.5cm \noindent \normalbaselineskip=11pt
\strut#\strit}\thinspace\vrule\cr
\multispan4\strut\hfil$n=6$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&\omit\hfil 2\hfil\vrule&\omit\hfil
3\hfil\vrule\cr 
\noalign{\hrule}
a{=}2&&
$(10q^6+35q^5+66q^4+80q^3+66q^2+35q+10)q^3$&\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
3&&
$(20q^9+90q^8+222q^7+372q^6+459q^5
+428q^4+302q^3+156q^2+55q
+10)q^6$&
$(10q^6+35q^5+66q^4+80q^3+66q^2+35q+10)q^6$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
4&&
$(15q^{11}+84q^{10}+254q^9+524q^8+806q^7
+963q^6+909q^5+679q^4+397q^3
+176q^2+55q+10)q^{10}$&
$(15q^8+64q^7+149q^6+233q^5+264q^4+219q^3
+130q^2+50q+10)q^{10}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
5&&
$(6q^{12}+35q^{11}+119q^{10}+287q^9
+526q^8+758q^7+875q^6+813q^5+608q^4
+362q^3+166q^2+55q+10)q^{15}$&
$(6q^9+35q^8+104q^7+203q^6+287q^5+303q^4
+239q^3+135q^2+50q+10)
q^{15}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
6&&
$(q^6+3q^5+7q^4+13q^3+16q^2+15q+10)
(q^3+q^2+q+1)
(q^2+q+1)(q+1)
q^{21}$&
$(q^6+4q^5+11q^4+19q^3+25q^2+20q+10)
(q^2+q+1)(q+1)q^{21}$\cr
\noalign{\hrule}
}}

\centerline{\box\dsixa}

\vskip 1cm



\newbox\dsixb

\setbox\dsixb=\vbox{\offinterlineskip 
\halign{\strot\vrule\thinspace\hfil$#$\thinspace&\vrule#&
\thinspace\hfil#\hfil\thinspace\vrule&
\thinspace\hfil#\hfil\thinspace\vrule\cr
\multispan4\strut\hfil$n=6$\hfil\cr
\noalign{\hrule}
b{=}{}&\omit&4&5\cr
\noalign{\hrule}
a{=}4&&
$(5q^4+14q^3+19q^2+14q+5)q^{10}$&\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
5&&
$(6q^5+20q^4+34q^3+34q^2+20q+5)q^{15}$&
$q^{15}$\cr
\omit\ttv\hfil&\multispan3\hrulefill\cr
6&&
$(q^4+5q^3+10q^2+10q+5)(q+1)q^{21}$&
$q^{21}$\cr
\noalign{\hrule}
}}


\centerline{\box\dsixb}

\vfill\eject





\newbox\stratbox
\setbox\stratbox=\hbox{\vrule height 7pt
depth 2pt width 0pt }
\def\strat{\relax\ifmmode\copy\stratbox
\else\unhcopy\stratbox\fi}

\newbox\stretbox
\setbox\stretbox=\hbox{\vrule height 9pt
depth 0pt width 0pt }
\def\stret{\relax\ifmmode\copy\stratbox
\else\unhcopy\stratbox\fi}

\newbox\stritbox
\setbox\stritbox=\hbox{\vrule height 2pt
depth 0pt width 0pt }
\def\strit{\relax\ifmmode\copy\stratbox
\else\unhcopy\stratbox\fi}

\centerline{\bf The bijections for $\bf n=4$}
\vfill

\eightpoint
\centerline{\vbox{
\tabskip=0pt \offinterlineskip
\def\hauteur{\noalign{\vskip 10pt }}
\def\pointille{\leaders\hbox to 3pt{\hss\vrule
height .4pt  width 1pt depth 0.0pt \hss}\hfill}
\def\trait{\noalign{\hrule }}
\def\espace{\kern5pt }
\def\borne{\vrule height 1pt depth .6pt width .4pt }
\halign{
\strat#&\vrule#\tabskip=3pt plus 1pt&
\hfil#\hfil&
\vrule#&
\hfil#\hfil&
\vrule#&
\hfil$#$\hfil&
\vrule#\tabskip=0pt &
\hfil\kern3pt\espace#\espace\hfil&
\hfil\espace#\espace\hfil&
\hfil\espace#\espace\hfil&
\hfil\espace#\espace\kern3pt\hfil &
\vrule#\tabskip=3pt plus 1pt&
\hfil$#$\hfil&
\vrule#&
\hfil#\hfil&
\vrule#&
\hfil#\hfil&
\vrule#\hfil&
\hfil#\hfil&
\vrule#\tabskip=0pt\cr
\trait
&&exc&&den&&\pi&&\multispan4\hfil weighted path\hfil&&
\pi'&&des&&mak&&maj&\cr
\trait
&&&&&
&&
&\omit\kern3pt\borne\hrulefill\borne&
\omit\hrulefill\borne&
\omit\hrulefill\borne&
\omit\hrulefill\borne\kern3pt&
&&&&&&&&\cr
&&0&&0&&
1,2,3,4&
&0&0&0&0&
&1,2,3,4&&0&&0&&0&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\hfill&
\omit\hfill&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&\omit\borne\hrulefill\borne&
\omit\hrulefill\borne\kern3pt&
&&&&&&&&\cr
&&1&&1&&
2,1,3,4&
&0&0&0&0&
&2,1,3,,4&&1&&1&&1&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\hrulefill\borne&
\omit\hfill&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\borne\hrulefill\borne\kern3pt&
&&&&&&&&\cr
&&1&&1&&
3,1,2,4&
&0&0&0&0&
&2,3,1,4&&1&&1&&2&\cr
&&1&&2&&
3,2,1,4&
&0&1&0&0&
&3,1,2,4&&1&&2&&1&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\hrulefill\borne&
\omit\hrulefill\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&1&&1&&
4,1,2,3&
&0&0&0&0&
&2,3,4,1&&1&&1&&3&\cr
&&1&&2&&
4,2,1,3&
&0&1&0&0&
&3,4,1,2&&1&&2&&2&\cr
&&1&&2&&
4,1,3,2&
&0&0&1&0&
&2,4,1,3&&1&&2&&2&\cr
&&1&&3&&
4,2,3,1&
&0&1&1&0&
&4,1,2,3&&1&&3&&1&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\hfill\borne&
\omit\hfill&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hrulefill\borne&&&
\omit\borne\hrulefill\borne\kern3pt&
&&&&&&&&\cr
&&1&&2&&
1,3,2,4&
&0&0&0&0&
&1,3,2,4&&1&&2&&2&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\hfill&
\omit\borne\hrulefill\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hrulefill\borne&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&1&&2&&
1,4,2,3&
&0&0&0&0&
&1,3,4,2&&1&&2&&3&\cr
&&1&&3&&
1,4,3,2&
&0&0&1&0&
&1,4,2,3&&1&&3&&2&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\hfill&
\omit\hfill\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hrulefill\borne&
\omit\hrulefill\borne&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&1&&3&&
1,2,4,3&
&0&0&0&0&
&1,2,4,3&&1&&3&&3&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&\omit\borne\pointille\borne&
\omit\hfill&&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\borne\hrulefill\borne\kern3pt&
&&&&&&&&\cr
&&2&&3&&
2,3,1,4&
&0&0&0&0&
&3,2,1,4&&2&&3&&3&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\pointille\borne&
\omit\hrulefill\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&2&&3&&
2,4,1,3&
&0&0&0&0&
&3,4,2,1&&2&&3&&5&\cr
&&2&&4&&
2,4,3,1&
&0&0&1&0&
&4,2,1,3&&2&&4&&3&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\hfill\borne&&&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\hfill\borne&&
\omit\hfill\borne&&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&2&&3&&
3,4,1,2&
&0&0&0&0&
&3,2,4,1&&2&&3&&4&\cr
&&2&&4&&
3,4,2,1&
&0&1&0&0&
&3,1,4,2&&2&&4&&4&\cr
&&2&&4&&
4,3,1,2&
&0&0&1&0&
&4,2,3,1&&2&&4&&4&\cr
&&2&&5&&
4,3,2,1&
&0&1&1&0&
&4,1,3,2&&2&&5&&4&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill\borne&
&\omit\hfill\borne&&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&
\omit\hfill\borne&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&2&&4&&
2,1,4,3&
&0&0&0&0&
&2,1,4,3&&2&&4&&4&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\hrulefill\borne&
\omit\pointille\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&2&&4&&
3,1,4,2&
&0&0&0&0&
&2,4,3,1&&2&&4&&5&\cr
&&2&&5&&
3,2,4,1&
&0&1&0&0&
&4,3,1,2&&2&&5&&3&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\hfill\borne&
\omit\pointille\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hrulefill\borne&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&2&&5&&
1,3,4,2&
&0&0&0&0&
&1,4,3,2&&2&&5&&5&\cr
\trait
\omit\strit&&&&&
&&
&\omit\hfill&
\omit\borne\pointille\borne&
\omit\pointille\borne&
\omit\hfill&
&&&&&&&&\cr
\omit\stret&&&&&&&&
\omit\kern3pt\borne\hfill&&&
\omit\hfill\borne\kern3pt&
&&&&&&&&\cr
&&3&&6&&
2,3,4,1&
&0&0&0&0&
&4,3,2,1&&3&&6&&6&\cr
\trait
}}}

\vfill
\eject

\pageno=29
\vglue .1pt
\vfill
\eightpoint
\centerline{REFERENCES}
\vskip 10pt
\livre Carle|(Dr.) J. Carlebach|Lewi ben 
Gerson als Mathematiker|Louis Lamm, Berlin, {\oldstyle1910}|
\article Carli|L. Carlitz|q-Bernouli and 
Eulerian numbers|Trans.
Amer. Math. Soc.|76|1954|332--350|
\divers De1|M. Denert|Private communication|
\divers De2|M. Denert|The genus zeta function 
of hereditary orders in
central simple algebras over global fields, preprint|
\article D-F1|J. D\'esarm\'enien and D. Foata|Fonctions 
sym\'etriques
et s\'eries hyper\-g\'eo\-m\'e\-triques basiques 
multivari\'ees|Bull. Soc. Math. France|113|1985|3--22|
\divers D-F2|J. D\'esarm\'enien and D. Foata|Fonctions 
sym\'etriques
et s\'eries hyper\-g\'eo\-m\'e\-triques basiques 
multivari\'ees, II,
in : {\sl Combinatoire \'enum\'erative} 
[Proceedings, Montr\'eal. {\oldstyle 1985} ;
G. Labelle and P. Leroux, eds.], p.~68--90\pointir
Springer, Berlin ({\it Lecture Notes in Math.},
{\bf 1234})|
\article DRS|P. Doubilet, G.-C. Rota and J. Stein|On the
foundations of combinatorial theory, IX. Combinatorial
methods in invariant theory|Studies in Appl. 
Math.|53|1974|185--216|
\article Fo1|D. Foata|On the Netto inversion 
number of a sequence|Proc. Amer. Math. Soc.|19|1968|236--240|
\divers Fo2|D. Foata|Distributions eul\'eriennes
et mahonniennes sur le
groupe des permutations, in {\sl Higher Combinatorics}
[M. Aigner, ed.,
Berlin. 1976], p.~27-49\pointir
D. Reidel, Amsterdam, {\oldstyle 1977} (Proc. NATO Adv. Study
Inst.)|
\livre Ga|S. Gandz|Studies in Hebrew Astronomy 
and Mathematics|Ktav, New York, {\oldstyle 1970}|
\article G-G|A. Garsia and I. Gessel|Permutations Statistics and
Partitions|Adv. in Math.|31|1979|288--305|
\livre Kn|D. E. Knuth|The Art of Computer Programming, 
{\rm vol.~3},
Sorting and Searching|Addison-Wesley, Reading, {\oldstyle1973}|
\divers Le|(Rabbi) Levi Ben Gerson ("RALBAG")|Ma'asse Khoshev
($\equiv$ ``Sepher Hamispar")\pointir Orange, France, 
{\oldstyle 1321}. (A German
translation appears in [Carle], p.~151--179)|
\livre Lo|M. Lothaire|Combinatorics on Words|Addison-Wesley,
Reading, ({\sl Enclycopedia of Math. and its Appl.},
{\bf 17}), {\oldstyle 1983}|
\article Ma|(Major) P. A. MacMahon|The indices 
of permutations and the
derivation therefrom of functions of a 
single variable associated
with the permutations of any assemblage 
of objects|Amer. J.
Math.|35|1913|314-321|
\livre Rai|E. D. Rainville|Special Functions|MacMillan,
New York, $\oldstyle 1960$ [Reprinted : Chelsea,
Bronx, N.Y., $\oldstyle 1971$]|
\article Ra|D. Rawlings|Generalized Worpitzki identities with
applications to permutation enumeration|Europ. J. 
Comb.|2|1981|67-78|
\article Staf|J.T. Stafford|Module structure of Weyl algebras|J. London
Math. Soc.|18|1978|429--442|
\livre Su|C. Suar\`es|The Sepher Yetsira, {\rm 
translated from the
French by M. and V. Stuart}|Shambhala, London and Boulder, 
{\oldstyle 1976}|
\divers Vi|G. Viennot|Une th\'eorie combinatoire
des polyn\^omes orthogonaux g\'en\'eraux, Notes conf.,
Univ. Qu\'ebec \`a Montr\'eal, $\oldstyle 1984$|
\article Ze|D. Zeilberger|Partial difference equations in
$m_1\ge m_2 \ge\cdots \ge  m_n$ and their applications to
combinatorics|Discrete Math.|31|1980|65-77|
\divers Ze2|D. Zeilberger|A holonomic systems approach
to special functions identities, preprint, $\oldstyle 1988$,
51.~p|
\vfill\eject





\bye
