\catcode'32=9
\magnification=1200

% particularite du pilote canon

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% 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

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

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm8
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\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\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \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}%
  \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
  \let\petcap=\tenpc
  \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\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \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}%
  \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}

\let\bb=\bboard

\tenpoint

%���������������������� dactylographie fran�aise �����������������

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

%���������������������� format de sortie �����������������

\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



\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\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\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}, t.\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\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

%les differents retraits, voir aussi \item
\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}


\catcode`\@=12

%end format

%some macros from LaTeX

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%������������������������������������������������������������������

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
\noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip}}

%������������������������������������������������������������������

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%������������������������������������������������������������������


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\def\cput(#1,#2)#3{\noalign{\nointerlineskip\centerput(#1,#2){#3}
                             \nointerlineskip}}



\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\def\boucle{\vbox{\offinterlineskip
\leftput(0,4){\vector(0,-1){3}}
\segment(0,0)\dir(-1,1)\long{4}
\segment(-4,4)\dir(1,0)\long{4}
}}

%end of LaTeX macros

%some local macros

\def\oui{$\bullet$}
\def\nein{\phantom{$\bullet$}}

\def\ouic{{$\atop\displaystyle \bullet$}}

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

\newbox\stritbox
\setbox\stritbox=\hbox{\vrule height 10pt depth 4.5pt width 0pt }
\def\strit{\relax\ifmmode\copy\stritbox\else\unhcopy\stritbox\fi}
\def\oui{$\bullet$}
\def\nein{\phantom{$\bullet$}}

\def\cyc{\mathop{\rm cyc}\nolimits}
\def\Inc{\mathop{\rm Inc}\nolimits}
\def\card{\mathop{\rm card}\nolimits}
\def\proof{\par{\it Proof}\pointir }
\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt } 

{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}

%end of macros

\raggedbottom


\pageno=73
\eightpoint
\leftline{S\'eminaire Lotharingien de Combinatoire, 
B16a (1987), 14 pp.}
\leftline{[Formerly : Publ. I.R.M.A. Strasbourg, $\oldstyle 1987$, 
341/S--16, p. 73--86.]}

\tenpoint

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

\vskip 1.5cm
\centerline{{\bf LINEARIZATION COEFFICIENTS FOR}}
\vskip 5pt
\centerline{{\bf THE JACOBI POLYNOMIALS}}
\vskip 2.8mm
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{{\petcap Dominique} FOATA {\sevenrm AND}
{\petcap Doron} ZEILBERGER}
\vskip 24pt
\resume{Une formule explicite pour les coefficients
de lin\'earisation des polyn\^omes de Jacobi a \'et\'e donn\'ee
par \pc RAHMAN|, d'o\`u l'on tire, sans calcul, les
propri\'et\'es de positivit\'e. L'obtention
de la formule de \pc RAHMAN| par des m\'ethodes combinatoires
semble malais\'ee. On peut cependant donner plusieurs interpr\'etations
combinatoires de l'int\'egrale du produit de polyn\^omes de Jacobi
$\prod _iP_{n_i}^{(\alpha ,\beta )}(x)$ et en d\'eduire
une \'evaluation dans le cas particulier o\`u
$n_1=n_2+\cdots+n_m$.}
\vskip 5pt
\abstract{The explicit non-negative representation of
the linearization coefficients
of the Jacobi polynomials obtained by \pc RAHMAN|
seems to be difficult to be derived by 
combinatorial methods. However several combinatorial
interpretations can be provided for the 
integral of the product of Jacobi polynomials
$\prod _iP_{n_i}^{(\alpha ,\beta )}(x)$ and furnish an evaluation
of this integral in the particular case where
$n_1=n_2+\cdots+n_m$.}

\vskip 6pt plus 6pt
\section 1. Introduction|
Standard definition for the Jacobi polynomials
reads : 
  $$\displaylines{P_n^{(\alpha ,\beta )}(x)=
\sum _{j=0}^n {n+\alpha \choose n-j} {n+\beta \choose j}
\left({x-1\over 2}\right)^j
\left({x+1\over 2}\right)^{n-j}\hfill\cr
\hfill{}={2^{-n}\over n!}
\sum _{j=0}^n {n\choose j} (\alpha +1+n-j)_j\,
(\beta +1+j)_{n-j}\,
(x-1)^{n-j}
(x+1)^j.\cr}$$
(See, e.g., [Er], [Sz]). Let ${\bf n}=(n_1,\ldots,n_m)$ and
consider the integral  
  $$\displaylines{I_{\bf n}=\int _{-1}^{+1} (1-x)^\alpha  (1+x)^\beta 
\prod _{i=1}^m P_{n_i}^{(\alpha ,\beta )}(x)\,dx.\cr
\noalign{\hbox{Using the classical evaluation}}
\int _{-1}^{+1} (1-x)^\alpha  (1+x)^\beta \,dx
={\Gamma (\alpha +1)\Gamma (\beta +1)\over \Gamma (\alpha +\beta +2)},\cr
\noalign{\hbox{it is readily seen that}}
(1.1)\quad I_{\bf n}={2^{\alpha +\beta +1}\over \prod _i n_i!\,(\alpha +\beta +2)_{\Sigma n_i}}
{\Gamma (\alpha +1)\Gamma (\beta +1)\over \Gamma (\alpha +\beta +2)} L_{\bf n},\hfill\cr
\noalign{\hbox{with}}
(1.2)\quad L_{\bf n}=\smash{\sum _{\bf k}} (-1)^{\Sigma (n_i-k_i)}\, (\alpha +1)_{\Sigma (n_i-k_i)}\,
(\beta +1)_{\Sigma k_i}\hfill\cr
\hfill{}\times  \prod _i {n_i\choose k_i}
(\alpha +1+n_i-k_i)_{k_i}\, (\beta +1+k_i)_{n_i-k_i}.\qquad\cr}$$
The linearization problem consists of 
finding an appropriate representation for
$I_{\bf n}$ in such a way that non-negative properties 
of $I_{\bf n}$ are directly apparent from the representation itself.
Along those lines
\pc RAHMAN| [Ra] 
found the following fantastic
formula involving the series $_9F_8$ :
let $s+1\leq n$, $0\leq j\leq 2n-2s$ and let
  $$\displaylines{(1.3)\hfill
I_{s+j,n-s,n}={(\alpha +1)_{s+j}(\alpha +1)_{n-s}(\alpha +1)_n \over  
(s+j)!\,(n-s)!\, n!}{\Gamma (\alpha +1)\Gamma (\beta +1)
\over 2^{-(\alpha +\beta +1)}\Gamma (\alpha +\beta +1)}\cr
\hfill{}\times 
{(s+j)!\,(\beta +1)_{s+j}
\over 
(\alpha +\beta )_{s+j}(\alpha +\beta +1)_{s+j}(2s+2j+\alpha +\beta +1)}
g(s+j,n-s,n).\cr}$$
Then, for $j$ even 
  $$\displaylines{\eqalign{g(s+j,n-s,n)
&={\alpha +\beta +1+2s+2j\over \alpha +\beta +1}(\alpha +\beta +1+n-s)_{n-s}\cr
&\quad{}\times 
{(\alpha +1)_{s+j}(\beta +1)_n(\alpha +\beta +1)_{2s+j}(\alpha +\beta +1)_j n!
\over (\alpha +1)_s(\alpha +1)_{n-s}(\beta +1)_{s+j}(\alpha +\beta +2)_{2n+j}\,s!\,j!}\cr
&\quad{}\times 
{(s-n)_{j/2}(\alpha +\beta +n+1)_{j/2} \over 
\left(s-n-\displaystyle {\alpha +\beta \over 2}\right)_{\kern-2pt j/2}
(s+1)_{j/2}(\alpha +1)_{j/2} }\cr
&\quad{}\times 
{(s-n-\alpha )_{j/2}(\beta +n+1)_{j/2}(1/2)_{j/2} \over 
\left(\displaystyle {1\over 2}+s-n-\displaystyle {\alpha +\beta \over 2}\right)_{\kern-2pt j/2}
(s+1)_{j/2}(\alpha +1)_{j/2} }\cr
&\quad{}\times 
{}_9F_8\Biggl[
{\alpha ,1+\displaystyle {\alpha \over 2},
\alpha +\displaystyle {1\over 2},\displaystyle {\alpha -\beta \over 2}
\displaystyle {\alpha -\beta +1\over 2},
\atop
\displaystyle {\alpha \over 2},\displaystyle {1\over 2},
\displaystyle {\alpha +\beta \over 2}+1,\displaystyle {\alpha +\beta +1\over 2},}\cr}\hfill\cr
\hfill
{\alpha +\beta +n+1+\displaystyle {j\over 2}, s-n+\displaystyle {j\over 2},
-s-\displaystyle {j\over 2},-\displaystyle {j\over 2}
\atop
-\beta -n-\displaystyle {j\over 2},
\alpha +n+1-s-\displaystyle {j\over 2},\alpha +s+1
+\displaystyle {j\over 2},\alpha +1+\displaystyle {j\over 2}}
\Biggr]\quad\cr}$$
and a corresponding formula for $j$ odd. Note that in
\pc RAHMAN|'s paper [Ra, p.~917, formula (1.7)]
the factor
$(\alpha +\beta +1+n-s)_{n-s}$ occurring after the first fraction
above is missing.
As proved by \pc RAHMAN| [Ra], the foregoing formula shows that
if $j$, $s$, $n$ are non-negative integers with 
$s+1\leq n$, $0\leq j\leq 2n-2s$, then
$g(s+j,n-s,n)\geq 0$ whenever
$\alpha \geq \beta >-1$ and $\alpha +\beta +1\geq 0$.

Putting back the value of $g(s+j,n-s,n)$ into (1.3)
we deduce the following formula
  $$\displaylines{\eqalign{L_{s+j,n-s,n}
&={(\alpha +1)_n (s+j)!\, (\alpha +1)_{s+j} (\beta +1)_n (\alpha +\beta +1)_{2s+j} 
\over (\alpha +\beta +1)_{s+j}(\alpha +1)_s}\cr
&\ {}\times  
{(\alpha +\beta +1+n-s)_{n-s}(\alpha +\beta +1)_j\,n!
\over s!\,j!}\cr
&\ {}\times 
{(s-n)_{j/2}(\alpha +\beta +n+1)_{j/2} \over 
\left(s-n-\displaystyle {\alpha +\beta \over 2}\right)_{\kern-2pt j/2}(\alpha +s+1)_{j/2} }\cr
&\ {}\times 
{(s-n-\alpha )_{j/2}(\beta +n+1)_{j/2}(1/2)_{j/2} \over 
\left(\displaystyle {1\over 2}+s-n-\displaystyle {\alpha +\beta \over 2}\right)_{\kern -2pt j/2}
(s+1)_{j/2}(\alpha +1)_{j/2} }\cr
&\ {}\times 
{}_9F_8\Biggl[
{\alpha ,1+\displaystyle {\alpha \over 2},
\alpha +\displaystyle {1\over 2},\displaystyle {\alpha -\beta \over 2}
\displaystyle {\alpha -\beta +1\over 2},\alpha +\beta +n+1+\displaystyle {j\over 2},  
\atop
\displaystyle {\alpha \over 2},\displaystyle {1\over 2},
\displaystyle {\alpha +\beta \over 2}+1,\displaystyle {\alpha +\beta +1\over 2},
-\beta -n-\displaystyle {j\over 2},}\cr}\hfill\cr
\hfill
{s-n+\displaystyle {j\over 2},-s-\displaystyle {j\over 2},-\displaystyle {j\over 2}
\atop
\alpha +n+1-s-\displaystyle {j\over 2},\alpha +s+1+\displaystyle {j\over 2},\alpha +1+\displaystyle {j\over 2}}
\Biggr],\quad\cr}$$
when $j$ is even. When $j$ is odd, formula (1.8) of
\pc RAHMAN| [Ra] leads to :
  $$\displaylines{\eqalign{L_{s+j,n-s,n}
&={(\alpha +1)_n (s+j)!\, (\alpha +1)_{s+j} 
(\beta +1)_n 
\over (\alpha +\beta +1)_{s+j}(\alpha +1)_s}\cr
&\ {}\times  
{(\alpha +\beta +1)_{2s+j} (\alpha +\beta +1+n-s)_{n-s}
(\alpha +\beta +1)_jn!
\over s!\,j!}\cr
&\ {}\times 
{(s-n)_{(j+1)/2}(\alpha +\beta +n+1)_{(j+1)/2} \over 
\left(s-n-\displaystyle {\alpha +\beta \over 2}\right)_{\kern-2pt (j+1)/2}
(\alpha +s+1)_{(j+1)/2} }\cr
&\ {}\times 
{(s-n-\alpha )_{(j-1)/2}(\beta +n+1)_{(j-1)/2}(3/2)_{(j-1)/2} \over 
\left(\displaystyle {1\over 2}+s-n
-\displaystyle {\alpha +\beta \over 2}\right)_{\kern-2pt (j-1)/2}
(s+1)_{(j-1)j/2}(\alpha +2)_{(j-1)/2} }\cr}\hfill\cr
\hfill{}\times 
{\alpha -\beta \over \alpha +\beta +1}{}_9F_8\Biggl[
{\alpha +1,\displaystyle {\alpha +3\over 2},
\alpha +\displaystyle {1\over 2},\displaystyle {\alpha -\beta \over 2}+1,
\displaystyle {\alpha -\beta +1\over 2},
\atop
\displaystyle {\alpha +1\over 2},\displaystyle {3\over 2},
\displaystyle {\alpha +\beta \over 2}+1,\displaystyle {\alpha +\beta +3\over 2},}\quad\cr
\hfill
{\alpha +\beta +n+\displaystyle {3\over 2}+\displaystyle {j\over 2},  
s-n+\displaystyle {1\over 2}+\displaystyle {j\over 2},
\displaystyle {1\over 2}-s-\displaystyle {j\over 2},\displaystyle {1-j\over 2}
\atop
\displaystyle {1-j\over 2}-\beta -n,
\alpha +n+\displaystyle {3\over 2}-s-\displaystyle {j\over 2},
\alpha +s+\displaystyle {3\over 2}+\displaystyle {j\over 2},
\alpha +\displaystyle {3\over 2}+\displaystyle {j\over 2}}
\Biggr].\quad\cr}$$
It seems that a derivation of \pc RAHMAN|'s formula 
by means of combinatorial methods is out of scope.
It would first require an interpretation of the factor
$(\alpha )_k(1+\alpha /2)_k(\alpha +1/2)_k/(\alpha /2)_k(1/2)_k$ occurring in
the series ${}_9F_8$. But such a factor already occurs
in each classical hypergeometric series identity
involving ${}_pF_{p+1}$ for $p\geq 3$, for instance in
the Dougall, Whipple and Bailey identities (see [Bai, Chap.~4]).

When $\alpha =\beta $ (the case of ultraspheric polynomials), the
factor ${}_9F_8$ vanishes and \pc RAHMAN|'s formula greatly simplifies. 
For instance, for $j$ even we get :
  $$\displaylines{\noalign{\hbox{if $0\leq j\leq n-s$}}
\eqalign{L_{s+j,n-s,n}
&={s+j\choose s,j/2,j/2}s!\,
\left(\displaystyle {j\over 2}\right)!\,
{n\choose s+j/2} (n-s)!\cr
&\qquad{}\times 
(\alpha +1+j/2)_{n-j/2} (\alpha +1+s+j/2)_{j/2}\cr
&\qquad{}\times 
(\alpha +1+n-s-j/2)_{j/2} (\beta +1)_{n+j/2}\cr
&\qquad{}\times 
(\alpha +\beta +1+s+j)_s (\alpha +\beta +1+n-s)_{n-s-j}\cr
&\qquad{}\times 
(\alpha +\beta +1)_j (\alpha +\beta +n+1)_{j/2}\,;\cr}\cr
\noalign{\vskip 5pt
\hbox{if $n-s\leq j\leq 2n-2s$}}
\eqalign{L_{s+j,n-s,n}
&={s+j\choose s,j/2,j/2}s!\,
\left(\displaystyle {j\over 2}\right)!\,
{n\choose s+j/2} (n-s)!\cr
&\qquad{}\times 
(\alpha +1+j/2)_{n-j/2} (\alpha +1+s+j/2)_{j/2}\cr
&\qquad{}\times 
(\alpha +1+n-s-j/2)_{j/2} (\beta +1)_{n+j/2}\cr
&\qquad{}\times 
(\alpha +\beta +1+s+j)_s(\alpha +\beta +1+n-s)_{n-s}\cr
&\qquad{}\times 
(\alpha +\beta +1)_{2n-2s-j}(\alpha +\beta +n+1)_{j/2}.\cr}\cr}$$
In particular, with $j=0$ we get
  $$L_{s,n-s,n}=(\alpha +\beta +s+1)_s
(\alpha +\beta +1+n-s)_{n-s}n!\,(\alpha +1)_n(\beta +1)_n,\leqno(1.5)$$
a formula that will be extended further in the paper.

\goodbreak
The purpose of this article is to give a combinatorial
interpretation to $L_{\bf n}$  and to deduce from it
several analytic consequences (sections 2 and 3). 
As mentioned previously,
we cannot derive \pc RAHMAN|'s formula, but we can, at least,
evaluate an extension of (1.5), that is,
  $$L_{\bf n}=(\alpha +\beta +n_2+1)_{n_2}\cdots (\alpha +\beta +n_m+1)_{n_m}
n_1!\,(\alpha +1)_{n_1}(\beta +1)_{n_1},\leqno(1.6)$$
when $m$ is arbitrary and
$n_1=n_2+\cdots+n_m$. This is presented in section~4.

\section 2. Weighted bipermutations|
Consider formulas (1.1) and (1.2). The expression $L_{\bf n}$
will first be proved to be the generating function for
certain combinatorial objects, called {\it weighted
bipermutations}, as follows. Let $N=N_1+\cdots+N_m$
be an ordered partition of a set $N$ with
$\left|N_i\right|=n_i$ $(i=1,2,\ldots,m)$. If $K$ is
a subset of $N$, let $k_i=K\cap N_i$ and $\left|K_i\right|=k_i$
($i=1,2,\ldots,m$). Next consider a permutation
$\pi $ of the set $N$. An element $x$ of $N$ is said to be
$\pi $-{\it incestuous}, if both $x$ and $\pi (x)$ belong to the same
component $N_i$. Denote by $\Inc \pi $ the set of all
$\pi $-incestuous elements of~$N$. Finally, define
a {\it weighted bipermutation} of $N=N_1+\cdots+N_m$
as being a triple $(\pi _1,\pi _2,K)$, where $\pi _1$ and $\pi _2$
are permutations of $N$ and $K$ is a subset of $N$ that
satisfies the properties :
  $$K\subset \Inc \pi _1\qquad{\rm and}\qquad N\setminus K\subset \Inc \pi _2.$$
Define the {\it weights} of a weighted bipermutation
$(\pi _1,\pi _2,K)$ to be :
  $$\displaylines{w(\alpha ,\beta ;\pi _1,\pi _2,K)=(\alpha +1)^{\cyc \pi _1} (\beta +1)^{\cyc \pi _2}\,;\cr
w'(\alpha ,\beta ;\pi _1,\pi _2,K)=(-1)^{\left|N\setminus K\right|}
(\alpha +1)^{\cyc \pi _1} (\beta +1)^{\cyc \pi _2}\,;\cr}$$
where $\cyc \pi $ designates the number of cycles of the
permutation~$\pi $.

\th Theorem 1|The polynomial $L_{\bf n}$ defined in $(1.2)$
is the generating function for the weighted bipermutations
by the weight $w'$. In other words,
  $$\eqalign{L_{\bf n}(\alpha ,\beta ):=L_{\bf n}&=\sum  w'(\alpha ,\beta ;\pi _1,\pi _2,K)\cr
                  &=\sum (-1)^{\left|N\setminus K\right|}
(\alpha +1)^{\cyc \pi _1} (\beta +1)^{\cyc \pi _2}.\cr}$$\finth

\proof
Let $(\pi _1,\pi _2,K)$ be a weighted bipermutation of 
$N=N_1+\cdots+N_m$.
To the pair $(\pi _1,K)$
we can associate a sequence
$(\pi _{11},\ldots,\pi _{1m},\sigma _1)$, where each $\pi _{1i}$ is an injection
of $K_i$ into $N_i$ $(i=1,2,\ldots,m)$
and $\sigma _1$ is a permutation of the set $N\setminus K=\sum _i(N_i\setminus K_i)$.
Moreover, $\cyc \pi _1=\sum _i\cyc \pi _{1i}+\cyc \sigma _1$
and the mapping $(\pi _1,K)\mapsto  (\pi _{i1},\ldots,\pi _{im},\sigma _1)$
is bijective. Such a mapping has been described
in [Fo-Ze]. Fig.~1 indicates the construction of
such a bijection
In the same manner, we associate a sequence
$(\pi _{21},\ldots,\pi _{2m},\sigma _2)$ to $\pi _2$, where each 
$\pi _{2i}$ is an injection
of $N_i\setminus K_i$ into $N_i$ $(i=1,2,\ldots,m)$
and $\sigma _2$ is a permutation of $K$.



\midinsert
\centerline{\vbox{\offinterlineskip
\halign{\strat\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
\fleche(10,-12)\dir(0,-1)\long{10}
\fleche(12,-22)\dir(0,1)\long{10}
%
\fleche(16.5,-15.5)\dir(1,1)\long{4}
\fleche(22.5,-10)\dir(1,0)\long{7}
\fleche(32,-10)\dir(3,-2)\long{9}
\fleche(41.5,-18.5)\dir(0,-1)\long{10}
\fleche(41.5,-31.5)\dir(-1,-1)\long{4.5}
\fleche(35.5,-38.5)\dir(-1,-1)\long{4.}
\fleche(29.5,-43.5)\dir(-1,0)\long{7}
\fleche(22.5,-41.5)\dir(1,1)\long{8}
\fleche(28.5,-30.5)\dir(-1,1)\long{6}
\fleche(19.5,-22.5)\dir(-1,1)\long{4}
%
\fleche(16,-32)\dir(0,-1)\long{10}
\fleche(15,-42)\dir(-1,1)\long{4}
\fleche(11,-36)\dir(1,1)\long{4}
%
\fleche(18,-57)\dir(1,0)\long{16}
\fleche(36.5,-55.5)\dir(1,2)\long{5}
\fleche(40,-45)\dir(-2,-1)\long{22}
%
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
$K_1$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&$N_1\setminus K_1$\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil{$\atop\displaystyle \bullet$}\hfil\nein\hfil\oui\hfil&\cr
$K_2$&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&$N_2\setminus K_2$\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\oui\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
$K_3$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&$N_3\setminus K_3$\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\pi _1$\hfil&\omit\cr
}}\quad\vbox{\offinterlineskip
%
\halign{\strat\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(10,-12)\dir(0,-1)\long{10}
\fleche(12,-22)\dir(0,1)\long{10}
%
\fleche(16.5,-15.5)\dir(1,1)\long{4}
\fleche(22.5,-10)\dir(1,0)\long{7}
\fleche(32,-10)\dir(3,-2)\long{9}
\fleche(41.5,-18.5)\dir(0,-1)\long{10}
\fleche(41.5,-31.5)\dir(-1,-1)\long{4.5}
\fleche(35.5,-38.5)\dir(-1,-1)\long{4.}
\fleche(30.5,-42.5)\dir(0,1)\long{8}
\fleche(22.5,-41.5)\dir(1,1)\long{8}
\fleche(30.5,-29.5)\dir(0,1)\long{17}
\fleche(19.5,-22.5)\dir(-1,1)\long{4}
%
\fleche(16,-32)\dir(0,-1)\long{10}
\fleche(15,-42)\dir(-1,1)\long{4}
\fleche(11,-36)\dir(1,1)\long{4}
%
\fleche(18,-57)\dir(1,0)\long{16}
\fleche(36.5,-55.5)\dir(1,2)\long{5}
\fleche(40,-45)\dir(-1,-2)\long{5}
%
\kern13pt
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil{$\atop\displaystyle \bullet$}\hfil
\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\oui\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\omit\strut \hfil$\pi _{11},\pi _{12},\pi _{13}$\hfil&
\omit\strut\hfil$\sigma _1$\hfil&\omit\cr}}}
\vskip .5cm
\centerline{Fig. 1}
\endinsert



Therefore, $(\alpha +1)_{\Sigma (n_i-k_i)} \prod _i(\alpha +1+n_i-k_i)_{k_i}$
is the generating function for permutations $\pi _1$ by number
of cycles satisfying $K\subset \Inc \pi _1$. In the same manner,
$(\beta +1)_{\Sigma k_i} \prod _i(\beta +1+k_i)_{n_i-k_i}$
is the generating function for permutations $\pi _2$ by number
of cycles satisfying $N\setminus K\subset \Inc \pi _2$. Thus, to calculate
$L_{\bf n}$ we can first fix ${\bf k}$, then a sequence
${\bf K}=(K_1,\ldots,K_m)$ with $\left|K_i\right|=k_i$
($i=1,2,\ldots,m)$ and finally sum over all weighted
bipermutations $(\pi _1,\pi _2,K)$.\cqfd


As an application of this combinatorial interpretation we can
state the following corollary and also obtain another combinatorial
interpretation in terms of pairs of permutations with prescribed
incestuous element sets.

\th Corollary 1|If $\left|N\right|=n$, 
then $L_{\bf n}(\beta ,\alpha )=(-1)^{|N|}L_{\bf n}(\alpha ,\beta )$. In particular, when $n$ is odd,
$L_{\bf n}(\alpha ,\alpha )=0$.\finth

\proof Consider the transformation
$(\pi _1,\pi _2,K)\mapsto  (\pi _2,\pi _1,N\setminus K)$. Then
  $$\eqalign{w'(\beta ,\alpha ;\pi _2,\pi _1,N\setminus K)&=(-1)^{|K|}(\beta +1)^{\cyc \pi _2}
(\alpha +1)^{\cyc \pi _1}\cr
&=(-1)^{|N|}(-1)^{|N\setminus K|}(\alpha +1)^{\cyc \pi _1}(\beta +1)^{\cyc \pi _2}\cr
&=(-1)^{|N|}w'(\alpha ,\beta ;\pi _1,\pi _2,K).\cr}$$
Thus $L_{\bf n}(\beta ,\alpha )=(-1)^{|N|}L_{\bf n}(\alpha ,\beta )$.\cqfd

\goodbreak
\th Corollary 2 {\rm (Second combinatorial interpretation)}|One has :
  $$L_{\bf n}=\sum (-1)^{|N\setminus K|}(\alpha +1)^{\cyc \pi _1}(\beta +1)^{\cyc \pi _2},$$
where the summation is over all triples $(\pi _1,\pi _2,K)$ 
with $\pi _1$ and $\pi _2$ permutations of $N$, and $K$ a subset
of $N$ with the property that $K=\Inc \pi _1$ and $N\setminus K=\Inc \pi _2$.\finth

\proof Let $(\pi _1,\pi _2,K)$ be a weighted bipermutation. If
$\Inc \pi _1\cap \Inc \pi _2$ is non-empty, look at the smallest element
$\xi $ in that set. Then define
$\phi(\pi _1,\pi _2,K)=(\pi _1,\pi _2,K\setminus \{ \xi \} )$ or $( \pi _1,\pi _2,K+\{ \xi \} )$,
depending on whether $\xi $ is in $K$ or not. In both cases
$\phi(\pi _1,\pi _2,K)$ is a weighted bipermutation and
  $$w'\phi(\alpha ,\beta ;\pi _1,\pi _2,K)=-w'(\alpha ,\beta ;\pi _1,\pi _2,K).$$
Therefore the summation $\sum w'(\alpha ,\beta ;\pi _1,\pi _2,K)$ over all
pairs $(\pi _1,\pi _2)$ such that $\Inc \pi _1\cap \Inc \pi _2=\emptyset $ equals~0.
Now as $K\subset \Inc \pi _1$ and $N\setminus K\subset \Inc \pi _2$, the condition
$\Inc \pi _1\cap \Inc \pi _2=\emptyset $ means that $K=\Inc \pi _1$
and $N\setminus K=\Inc \pi _2$.\cqfd 

\section 3. Weighted derangements|
The polynomial $L_{\bf n}$ can also be expressed in terms of
derangement polynomials as follows. 
Keep the same notations as in the beginning of section~2
for $N$, $K$, $N_i$, $K_i$
and define a
$K$-{\it derangement} to be a permutation $\sigma $ of $K$ such
that for every $x$ in $K$ the elements $x$ and $\sigma (x)$
belong to different components $K_i$ and $K_j$
$(i\not=j)$. Set
  $$D({\bf k};\alpha )=\sum (\alpha +1)^{\cyc \sigma },$$
where $\sigma $ ranges over all $K$-derangements. 

\th Theorem 3 {\rm (third combinatorial interpretation)}|One has :
  $$\displaylines{(3.1)\qquad L_{\bf n}=\smash{\sum _{K\subset N}} (-1)^{|K\setminus N|}
D({\bf n-k};\alpha )D({\bf k};\beta )\hfill\cr
\hfill{}\times \prod _i(\alpha +1+n_i-k_i)_{k_i}
(\beta +1+k_i)_{n_i-k_i}.\qquad\cr}$$
\finth

\proof
Consider a weighted bipermutation
$(\pi _1,\pi _2,K)$ with $K=\Inc \pi _1$ and $N\setminus K=\Inc \pi _2$.
If we use the bijection described in the proof of
\pc THEOREM|~1, the pair $(\pi _1,K)$ is transformed
into a sequence $(\pi _{11},\ldots,\pi _{1m},\sigma _1)$, but this
time $\sigma _1$ is an $(N\setminus K)$-{\it derangement}, as shown in Fig.~2.



\midinsert
\centerline{\vbox{\offinterlineskip
\halign{\strat\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(12,-10)\dir(1,0)\long{28}
\fleche(41.5,-12)\dir(0,-1)\long{50}
\fleche(10.5,-29)\dir(0,1)\long{4}
\fleche(10.5,-21.5)\dir(0,1)\long{9}
%
\fleche(23,-17)\dir(1,0)\long{11}
\fleche(36,-19)\dir(0,-1)\long{16}
\fleche(36,-39)\dir(-1,-2)\long{5}
\fleche(29,-50.5)\dir(-1,1)\long{6.5}
\fleche(20,-42.5)\dir(-1,1)\long{4}
\fleche(17,-36)\dir(2,1)\long{11}
\fleche(29,-29.5)\dir(-2,1)\long{11}
\fleche(16.5,-22)\dir(1,1)\long{4}
%
\fleche(10.5,-62)\dir(0,1)\long{10}
\fleche(11.5,-52)\dir(1,-1)\long{4}
\fleche(15,-58)\dir(-1,-1)\long{4}
%
\segment(36,-58)\dir(-2,1)\long{20}
\segment(15,-48)\dir(-1,3)\long{8}
%
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&\cr
$K_1$&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&$N_1\setminus K_1$\cr
&\omit\vrule\hfil\oui\hfil\oui\hfil\nein\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
$K_2$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&$N_2\setminus K_2$\cr
&\omit\vrule\hfil\ \boucle\kern-3pt{$\atop\displaystyle \bullet$}\hfil
\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
$K_3$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&$N_3\setminus K_3$\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\pi _1$\hfil&\omit\cr
}}\quad\vbox{\offinterlineskip
\halign{\strat\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(12,-10)\dir(1,0)\long{28}
\fleche(42.5,-12)\dir(0,-1)\long{50}
\fleche(40.5,-62)\dir(0,1)\long{50}
\fleche(10.5,-21.5)\dir(0,1)\long{9}
%
\fleche(23,-17)\dir(1,0)\long{11}
\fleche(36,-19)\dir(0,-1)\long{16}
\fleche(36,-39)\dir(-1,-2)\long{5}
\fleche(30.5,-49)\dir(0,1)\long{17}
\fleche(20,-42.5)\dir(-1,1)\long{4}
\fleche(17,-36)\dir(2,1)\long{11}
\fleche(31,-28)\dir(1,2)\long{4}
\fleche(16.5,-22)\dir(1,1)\long{4}
%
\fleche(10.5,-62)\dir(0,1)\long{10}
\fleche(11.5,-52)\dir(1,-1)\long{4}
\fleche(15,-58)\dir(-1,-1)\long{4}
%
\kern13pt
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&\omit\vrule\hfil\oui\hfil\oui\hfil\nein\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&\omit\vrule\hfil\ \boucle\kern-3pt
{$\atop\displaystyle \bullet$}\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\omit\strut \hfil$\pi _{11},\pi _{12},\pi _{13}$\hfil&
\omit\strut\hfil$\sigma _1$\hfil&\omit\cr}}}
\vskip .5cm
\centerline{Fig. 2}
\endinsert


In the same way, $(\pi _2,N\setminus K)$ is transformed into
$(\pi _{21},\ldots,\pi _{2m},\sigma _2)$
with $\sigma _2$ being a $K$-derangement.
Therefore
  $$\displaylines{\qquad L_{\bf n}=\smash{\sum _{K\subset N}} (-1)^{|N\setminus K|}
\sum \smash{\biggl(\prod _i}(\alpha +1)^{\cyc \pi _{1i}}
(\beta +1)^{\cyc \pi _{2i}}\smash{\biggr)}\hfill\cr
\hfill{}\times 
(\alpha +1)^{\cyc \sigma _1} (\beta +1)^{\kern-1pt \cyc \sigma _2}.\qquad\cr}$$
As $\pi _{1i}$ (resp. $\pi _{2i}$) is an injection of 
$K_i$ (resp. $N_i\setminus K_i$) into $N_i$ and
$\sigma _1$ (resp. $\sigma _2$) is an $(N\setminus K)$-derangement
(resp. a $K$-derangement), the summation over
the $\pi _{1i}$'s, the $\pi _{2i}$'s and the
derangements $\sigma _1$ and $\sigma _2$ yields~(3.1).\cqfd

There are several consequences
of this interpretation when $n_1\geq n_2+\cdots+n_m$.
First, study the case of the strict inequality.

\th Lemma 1|If $k_1>k_2+\cdots+k_m$, then $D({\bf k},\alpha )=0$.\finth

\proof If $\pi $ is a $K$-derangement, then
$\pi (K_1)\subset K_2+\cdots +K_m$. But
$|K_i|=k_1>k_2+\cdots+k_m$ and there do not exist any
$K$-derangements under this hypothesis.\cqfd

\th Lemma 2|Suppose $n_1>n_2+\cdots+n_m$ and
let $0\leq k_i\leq n_i$ for $i=1,\ldots,m$. Then
  $${\rm either}\quad k_1>k_2+\cdots+k_m,\quad
{\rm or}\quad (n_1-k_1)>(n_2-k_2)+\cdots+(n_m-k_m).$$
\finth

\proof
If $k_1\leq k_2+\cdots+k_m$, then
$n_1-k_1>n_2+\cdots+n_m-k_1>n_2-k_2+\cdots+n_m-k_m$.\cqfd

\th Proposition 1|If $n_1>n_2+\cdots+n_m$, then $L_{\bf n}=0$.\finth

\proof
With the foregoing hypothesis, either
$k_1>k_2+\cdots+k_m$
or $(n_1-k_1)>(n_2-k_2)+\cdots+(n_m-k_m)$.
Then, either $D({\bf k};\beta )=0$, or
$D({\bf n-k};\alpha )=0$. Therefore, (3.1) shows that
$L_{\bf n}=0$.\cqfd

\th Corollary|If $n_1\not=n_2$, then $L_{n_1,n_2}=0$.\finth

This is precisely the 
{\it orthogonality relation}.

\section 4. The evaluation of $L_{\bf n}$ for $n_1=n_2+\cdots+n_m$|
Consider again the summation (3.1). When
$n_1=n_2+\cdots+n_m$, the inequality
$k_1<k_2+\cdots+k_m$ implies $n_1-k_1>
(n_2-k_2)+\cdots+(n_m-k_m)$. Therefore, the factor
$D({\bf n-k};\alpha )$ vanishes for such a sequence {\bf k}.
In the same manner, if $k_1>k_2+\cdots+k_m$, then
$D({\bf k};\beta )=0$. The summation (3.1) can then be restricted
to those sequences {\bf k} satisfying
  $$0\leq k_1=k_2+\cdots+k_m\leq n_1=n_2+\cdots+n_m.\leqno(4.1)$$
In particular, for $m=2$ and $n_1=n_2=n$ we obtain :
  $$\displaylines{(4.2)\qquad L_{n,n}
=\smash{\sum _{k=0}^n} D(n-k,n-k,\alpha )D(k,k,\beta )\hfill\cr
\hfill{}\times 
\left({n\choose k}(\alpha +1+n-k)_k (\beta +1+k)_{n-k}\right)^{\kern-2pt 2}.
\qquad\cr}$$
We will have a more precise evaluation further in the paper.
For the time being, let us compare (4.2) with the classical
evaluation of the integral :
  $$\eqalign{I_{n,n}&=\int _{-1}^{+1} (1-x)^\alpha (1+x)^\beta 
\Bigl(P_n^{(\alpha ,\beta )}(x)\Bigr)^2dx\cr
&=
{2^{1+\alpha +\beta }\Gamma (1+\alpha +n)\Gamma (1+\beta +n) \over  n!\,(1+\alpha +\beta +2n)\Gamma (1+\alpha +\beta +n) }.\cr}$$
(See, e.g., [Rai, p. 260 (11)].) By comparison with the definition
of $L_{n,n}$ (formula (1.2)),
  $$\leqalignno{I_{n,n}&={2^{1+\alpha +\beta } \over  n!\,n!\,(\alpha +\beta +2)_{2n}}
{\Gamma (\alpha +1)\Gamma (\beta +1) \over  \Gamma (\alpha +\beta +2)} L_{n,n},\cr
\noalign{\hbox{so that}}
L_{n,n}&=(\alpha +\beta +n+1)_n n!\, (\alpha +1)_n (\beta +1)_n.&(4.3)\cr}$$
This formula will be a consequence of the next theorem.

\th Theorem 4|When $n_1=n_2+\cdots+n_m$, then
  $$L_{\bf n}=(\alpha +\beta +n_2+1)_{n_2}\cdots (\alpha +\beta +n_m+1)_{n_m}
n_1!\,(\alpha +1)_{n_1}(\beta +1)_{n_1}.$$
\finth 

\proof
As just noticed, the summation (3.1) can be restricted to
the sequences {\bf k} satisfying (4.1). But if $(\pi _1,\pi _2,K)$
is a triple with $|K_1|=|K_2+\cdots+K_m|$, then
$|N\setminus K|=|N_1+\cdots+N_m\setminus (K_1+\cdots+K_m)|=
|N_1\setminus K_1|+\cdots+|N_m\setminus K_m|=2|N_1\setminus K_1|$,
so that the sign $(-1)^{|N\setminus K|}$ is always equal to~1.
Therefore, 
  $$L_{\bf n}=\sum (\alpha +1)^{\cyc \pi _1}(\beta +1)^{\cyc \pi _2},$$
where $\pi _1$ and $\pi _2$ are permutations of $N$ and
$\pi _1(K_i)\subset N_i$, $\pi _1(N_i\setminus K_i)\subset N\setminus N_i$,
$\pi _2(N_i\setminus K_i)\subset N_i$, $\pi _2(K_i)\subset N\setminus N_i$
for $i=1,2,\ldots,m$.

Let $M_1=K_1+\sum _{j\geq 2}(N_j\setminus K_j)$ and
$M_2=N_1\setminus K_1+\sum _{j\geq 2}K_j$.
Note that 
$|M_1|=|M_2|=|N_1|$.
Our purpose is now to construct
a bijection that will explain the occurrence of each factor
in the right-hand side of the \pc THEOREM|~4
formula. The reader is advised to follow the construction
by looking at the geometric representations of the
mappings in~Fig.~3



\midinsert
\centerline{\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(10.5,-9)\dir(1,-1)\long{4}
\fleche(16,-14)\dir(1,-1)\long{4}
\fleche(23,-17.5)\dir(2,1)\long{6.5}
\fleche(29.5,-16)\dir(-2,-1)\long{13}
\fleche(16,-24)\dir(1,-1)\long{4}
\fleche(23,-28.5)\dir(1,0)\long{11}
\fleche(10,-34)\dir(0,1)\long{24}
%
\fleche(17,-44)\dir(1,0)\long{17}
\fleche(42,-39)\dir(0,1)\long{24}
\fleche(40.5,-34)\dir(-3,-1)\long{24}
%
\segment(40,-12)\dir(0,-1)\long{18.5}
\segment(33,-26)\dir(-6,-1)\long{25.}
\segment(35,-39)\dir(1,1)\long{4}
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
$N_1$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\ouic\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
$N_2$&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
$N_3$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\pi _1$\hfil&\omit\cr
}}\quad\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(7,-10)\dir(1,-4)\long{3}
\fleche(12,-22.5)\dir(1,1)\long{4}
\fleche(17,-20)\dir(-1,-4)\long{5.5}
\fleche(39,-8)\dir(-4,-1)\long{12}
\fleche(24,-11.5)\dir(-4,1)\long{16}
%
\fleche(13,-13)\dir(4,-3)\long{18}
\fleche(29.5,-28.5)\dir(-1,0)\long{11}
\fleche(37,-35)\dir(0,1)\long{21}
\fleche(35,-13)\dir(-1,0)\long{20}
%
\kern-10pt
\segment(22,-26.5)\dir(4,-1)\long{18.5}
%
\segment(15,-39)\dir(5,1)\long{26}
\segment(40,-34)\dir(0,1)\long{30}
%
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil{$\displaystyle \bullet\atop$}\hfil
\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil
\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\raise3pt\hbox{\boucle}\kern-3pt
\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\pi _2$\hfil&\omit\cr}}}

\vskip 3pt plus 2pt
\centerline{\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(16,-24)\dir(1,-1)\long{4}
\fleche(23,-27.5)\dir(1,0)\long{11}
\fleche(34,-29.5)\dir(-1,0)\long{11}
%
\fleche(17,-44)\dir(1,0)\long{17}
%
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
$N_1$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
$N_2$&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
$N_3$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\raise3pt\hbox{\boucle}\kern-3pt\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$f_2$ and $f_3$\hfil&\omit\cr
}}\quad\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(7,-10)\dir(1,-4)\long{3}
\fleche(12,-15)\dir(1,-4)\long{3}
%
\fleche(27,-15)\dir(1,-4)\long{3}
\fleche(37.5,-15)\dir(-1,-4)\long{6}
\fleche(20,-44)\dir(-1,0)\long{7}
%
\kern-8pt
\segment(22,-14.5)\dir(-1,0)\long{3}
\segment(21,-14.5)\dir(0,-1)\long{26}
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\delta $ and $\gamma $\hfil&\omit\cr}}}

\vskip 3pt plus 2pt
\centerline{\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(10.5,-9)\dir(1,-1)\long{4}
\fleche(16,-14)\dir(1,-1)\long{4}
\fleche(21.5,-19)\dir(3,-2)\long{13}
\fleche(35.5,-26)\dir(-4,3)\long{24}
%
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
$N_1$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
$N_2$&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
$N_3$&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\raise3pt\hbox{\boucle}\kern-3pt\oui
\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\sigma _1$\hfil&\omit\cr
}}\quad\vbox{\offinterlineskip
\halign{\strit\hfil#\ &\vrule#\kern2cm&
\vrule#\kern2cm&\vrule\ #\hfill\cr
%
\fleche(16,-26.5)\dir(3,2)\long{19}
\fleche(36,-15.5)\dir(-3,-2)\long{17}
%
\fleche(11,-24.5)\dir(0,-1)\long{18}
\fleche(24,-13)\dir(-4,-3)\long{12}
\fleche(13,-24.5)\dir(4,3)\long{12}
%
\kern-3pt
\segment(14,-21.)\dir(0,-1)\long{18}
&\omit\strut \hfil$K$\hfil&
\omit\strut \hfil$N\setminus K$\hfil&\omit\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\oui\hfil\nein\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\oui\hfil\nein\hfil\oui\hfil&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil
{$\displaystyle \bullet \atop$}\hfil&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&&\cr
&\omit\vrule\hfil\nein\hfil\nein\hfil\oui\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
&&&\cr
&\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&
\omit\vrule\hfil\nein\hfil\oui\hfil\nein\hfil&\cr
&&&\cr
\omit&\multispan2\hrulefill&\omit\cr
\omit&\multispan2\strut \hfil$\sigma _2$\hfil&\omit\cr}}}

\vskip 5pt plus 5pt
\centerline{Fig. 3}
\endinsert

\vskip 5pt
\decale (i)|For each $i=2,\ldots,m$ let $f_i$ be the mapping
of $N_i$ into itself defined by :
  $$f_i\bigm|_{K_i}=\pi _1\bigm|_{K_i}\qquad
{\rm and}\qquad
f_i\bigm|_{N_i\setminus K_i}=\pi _2\bigm|_{N_i\setminus K_i}.$$
As $\pi _1(K_i)\subset N_i$ and $\pi _2(N_i\setminus K_i)\subset N_i$,
the pair $(K_i,f_i)$ is a so-called
{\it Jacobi endofunction} (see [Fo-Le]).
Denote by $a(f_i)$ (resp. $b(f_i)$)
the number of cycles of $f_i$ all vertices of which 
are in $K_i$ (resp. $(N_i\setminus K_i)$ and let the weight
of $(K_i,f_i)$ be defined by
  $$w(K_i,f_i)=(\alpha +1)^{a(f_i)} (\beta +1)^{b(f_i)}.$$
As shown in [Fo-Le, th\'eor\`eme 1]
  $$\sum w(K_i,f_i)=(\alpha +\beta +n_i+1)_{n_i},\leqno(4.4)$$
the summation being over all Jacobi endofunctions on~$N_i$.

\vskip 5pt
\decale (ii)|Consider $x\in  N_1\setminus K_1$. As $\pi _1(N_1\setminus K_1)\subset N_2+\cdots+N_m$
and $\pi _1(K_i)\subset N_i$ ($i=2,\ldots,m$), sooner or later
the iterates $\pi _1^k(x)$ will hit the set
$\sum _{j\geq 2}(N_j\setminus K_j)$. Let $k(x)$ be the smallest integer
satisfying $\pi _1^{k(x)}(x)\in  \sum _{j\geq 2}(N_j\setminus K_j)$
and define $\gamma (x)=\pi _1^{k(x)}(x)$.
Clearly
  $$\gamma :N_1\setminus K_1\rightarrow \sum _{j\geq 2}(N_j\setminus K_j)$$
is a {\it bijection}.
In the same manner, define a {\it bijection}
$\delta :K_1\rightarrow \sum _{j\geq 2}K_j$
by means of~$\pi _2$.

\vskip 5pt
\decale (iii)|With the pair $(\gamma ,\delta )$ 
we can then make up a bijection of
$N_1$ onto the union $\sum _{j\geq 2}N_j$.

\vskip 5pt
\decale (iv)|Consider the cycles of $\pi _1$. All the cycles that intersect
$M_1$ but sometimes leave $M_1$ will be made purely $M_1$
by cancelling all the portions that leave $M_1$. This gives
a permutation $\sigma _1:M_1\rightarrow M_1$.

\vskip 5pt
\decale (v)|In the same manner, obtain a permutation
$\sigma _2:M_2\rightarrow M_2$.

\vskip 5pt
\noindent 
Remembering the definitions of $a(f_i)$
and $b(f_i)$ given in (i) we see that
to each triple $(\pi _1,\pi _2,K)$ there corresponds a sequence
  $$\displaylines{(K_2,f_2,\ldots,K_m,f_m,\gamma ,\delta ,\sigma _1,\sigma _2)\cr
\noalign{\hbox{with}}
\cyc \pi _1=a(f_2)+\cdots+a(f_m)+\cyc \sigma _1\,;\cr
\cyc \pi _2=b(f_2)+\cdots+b(f_m)+\cyc \sigma _2.\cr
\noalign{\hbox{Accordingly,}}
w(\alpha ,\beta ;\pi _1,\pi _2,K)=w(K_2,f_2)\cdots w(K_m,f_m)
(\alpha +1)^{\cyc \sigma _1}(\beta +1)^{\cyc \sigma _2}.\cr}$$
It can be verified that the correspondence between triples
and sequences defined by (i)--(v) is one-to-one. Hence
  $$\displaylines{\sum w(\alpha ,\beta ;\pi _1,\pi _2,K)\hfill\cr
\quad{}=
\sum w(K_2,f_2)\cdots\sum w(K_m,f_m)\sum _{\gamma ,\delta }1
\sum _{\sigma _1}(\alpha +1)^{\cyc \sigma _1}
\sum _{\sigma _2}(\beta +1)^{\cyc \sigma _2}\hfill\cr
\quad{}=(\alpha +\beta +n_2+1)_{n_2}\cdots 
(\alpha +\beta +n_m+1)_{n_m}\,n_1!\,
(\alpha +1)_{n_1} (\beta +1)_{n_1}.\qed\hfill\cr}$$

\rem Remark|
Note that for $m=2$ and $n_1=n_2=n$
\pc THEOREM|~4 yields identity~(4.3).

\section 5. Concluding remarks|
The problem of the linearization
of the classical orthogonal polynomials has been studied
again recently by means of combinatorial methods.
\pd ASKEY and his coauthors [As-Is, As-Is-Ko]
have already obtained several significant results
concerning the Hermite, Laguerre and Meixner polynomials.
\pc AZOR|, \pd GILLIS and \pc VICTOR|
[Az-Gi-Vi] found an elegant set-up for the Hermite polynomials.
The two authors of the present paper [Fo-Ze] have completed
the work of \pc ASKEY| and his coauthors as far as the
(generalized) Laguerre polynomials are concerned
by exploiting a $\beta $-extension of the
MacMahon Master Theorem. \pd ZENG [Ze] has further
extended the works of \pd ASKEY and the two authors and
proved new positivity results concerning the Meixner,
Krawtchouk and Charlier polynomials.   
\pd GILLIS and his coauthors [Gi-Je-Ze] reproved
several positivity results on the Legendre polynomials.
Some of their arguments have been implicitly used in
the present paper. \pc RAHMAN|'s formula, as said in the
introduction, should discourage several researchers.
Formula (3.1) seems to indicate that a new algebraic
tool has to be found to handle the product of
two derangement polynomials. There is also a
linearization coefficient formula for the ultraspheric
polynomials found by \pc HS\"U| [Hs], more compact than
\pc RAHMAN|'s formula for $\alpha =\beta $, but not so easy to be
tackled by combinatorial methods. The only hope for the time
being seems to be the symmetric function approach due
to \pc ZENG|. He has already got an explicit formula
for a single derangement polynomial that led to the
positivity result for the Krawtchouk polynomials.  

\rem Note added in $1994$|The article [Ze]  has been updated in
the reference list. Notice that the linearization coefficients for
the class of Sheffer polynomials has been thoroughly studied by
Zeng [Ze92]. An interesting connection between linearization
coefficeints for Jacobi polynomials and permutation pair
counting has been derived in [Ze91]. The Rahman formula
remains untamed in the combinatorial environment.


\bigskip\bigskip
{\eightpoint

\divers Ze91|\pd ZENG (Jiang)|Counting a pair of permutations
and the linearization coefficients for Jacobi polynomials,
{\sl Actes de l'Atelier de Combinatoire franco-qu\'ebecois},
Publ. LACIM, no.~10, Universit\'e du Qu\'ebec \`a Montr\'eal,
{\oldstyle 1991}|
\article Ze92|\pd ZENG (Jiang)|Weighted derangements and
Sheffer polynomials|Proc. London Math. Soc.|65|1992|1--22|

}

 \vfill\eject



\null
\vfill
\eightpoint
\centerline{REFERENCES}
\vskip 10pt
\nobreak
\article As-Is|\pd ASKEY (Richard) and \pd ISMAIL (Mourad E.H.)|Permutation
problems and special functions|Canad. J. Math.|28|1976|853--874|
\article As-Is-Ko|\pd ASKEY (Richard), \pd ISMAIL (Mourad E.H.)
and \pd KOORNWINDER (T.)|Weighted permutation problems and
Laguerre polynomials|J. Combinatorial Theory, Ser.~A|25|1978|277--287|
\article Az-Gi-Vi|\pd AZOR (R.), \pd GILLIS (J.) and \pd VICTOR 
(J.D.)|Combinatorial application of Hermite polynomials|SIAM
J. Math. Anal.|13|1982|879--890|
\livre Bai|\pd BAILEY (W.N.)|Generalized Hypergeometric Series|Cambridge
Univ. Press, $\oldstyle 1936$|
\divers Er|\pd ERD\'ELYI (A.) et al|{\sl Higher Transcendental Functions}
(Bateman Manuscript Project),
3~vol\pointir New York, McGraw-Hill, $\oldstyle 1953$|
\article Fo-Le|\pd FOATA (Dominique) et \pd LEROUX
(Pierre)|Polyn\^omes de Jacobi, interpr\'etation
combinatoire et fonction
g\'en\'eratrice|Proc. Amer. Math. Soc.|87|1983|47--53|
\divers Fo-Ze|\pd FOATA (Dominique) and \pd ZEILBERGER
(Doron)|Weighted derangements and Laguerre polynomials, in
{\sl S\'eminaire Lotharingien de combinatoire
(Bayreuth, Erlangen, Strasbourg)}, 8\emini\ session
[D. Foata, \'ed. ; Sainte-Croix-aux-Mines. 23--28
mai $\oldstyle 1983$], p.~17--25\pointir
Publ. IRMA Strasbourg, 229/S--08, $\oldstyle 1984$|
\divers Gi-Je-Ze|\pd GILLIS (J.), \pd JEDWAB (J.) and \pd ZEILBERGER
(D.)|A combinatorial interpretation of the integral of the
product of Legendre polynomials, manuscrit, Weizmann
Inst., $\oldstyle 1987$|
\article Hs|\pd HS\"U (Hsien-Y\"u)|Certain integrals and infinite
series involving ultraspheric polynomials and Bessel 
functions|Duke Math. J.|4|1938|374--383|
\article Ra|\pd RAHMAN (Mizan)|A non-negative representation
of the linearization coefficients of the product of Jacobi
polynomials|Canad. J. Math.|33|1981|915--928|
\livre Rai|\pd RAINVILLE (E.D.)|Special Functions|New York,
Chelsea, $\oldstyle 1960$|
\livre Sz|\pd SZEG\"O (Gabor)|Orthogonal Polynomials|Providence, R.I.,
Amer. Math. Soc., $\oldstyle 1939$ ({\sl Amer. Math.
Soc. Colloq. Publ.}, {\bf 23}) [second printing of the
fourth edition : $\oldstyle 1978$]|
\article Ze|\pd ZENG (Jiang)|Lin\'earisation de produits de
polyn\^omes de Meixner, Kraw\-tchouk et Charlier|S.I.A.M. J.
Math. Anal.|21|1989|1349--1368|

\bigskip\bigskip
\line{\vtop{\halign{#\hfil\cr
Dominique {\petcap Foata},\cr
D\'epartement de math\'ematique,\cr
Universit\'e Louis-Pasteur,\cr
7, rue Ren\'e-Descartes,\cr
F-67084 Strasbourg, France.\cr}}\hfil
\vtop{\halign{#\hfil\cr
Doron {\petcap Zeilberger},\cr
Department of Mathematics,\cr
Drexel University,\cr
Philadelphia, Pennsylvania 19104, U.S.A.\cr
\noalign{\smallskip}
now at Temple University,\cr
Philadelphia, Pennsylvania 19122, U.S.A. \cr}}}

\fin
\eject



\bye
