{\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}

\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}

\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 }

\catcode`\@=12
\pageno=17
\def\Per{\mathop{\rm Per}\nolimits}
\def\cyc{\mathop{\rm cyc}\nolimits}
\def\Inc{\mathop{\rm Inc}\nolimits}
\def\card{\mathop{\rm card}\nolimits}
\auteurcourant={D. FOATA AND D. ZEILBERGER}
\titrecourant={WEIGHTED DERANGEMENTS}

\eightpoint

\leftline{S\'eminaire Lotharingien de Combinatoire, 
B08c (1984) 9 pp.} 
\leftline{[Formerly: Publ. I.R.M.A. Strasbourg, $\oldstyle
1984$, 229/S--08, p. 17--25.]}

\tenpoint
\let\it=\sl

\vskip 1.5cm
\centerline{{\bf WEIGHTED DERANGEMENTS}}
\vskip 5pt
\centerline{{\bf AND LAGUERRE POLYNOMIALS}}
\vskip 2.8mm
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{{\petcap Dominique} FOATA {\sevenrm AND}
{\petcap Doron} ZEILBERGER}
\vskip 3mm
\section 1. Introduction|One of the harbingers of the current combinatorization
of the theory of special functions was a remarkable result of
\pd GILLIS and \pd EVEN [7] that gave a certain combinatorial interpretation
to the linearization coefficients of the {\sl simple} Laguerre
polynomials $L_n(x)$. 
Let $\bigl(L^{(\alpha )}_n(x)\bigr)$ be the sequence of the 
(general) Laguerre polynomials that may be defined by their 
generating function 
  $$\sum _{n=0}^\infty  L^{(\alpha  )}_n(x) u^n
=(1-u)^{-\alpha  -1}\exp{-xu \over  1-u},\leqno(1.1)$$
the simple Laguerre polynomials being defined by
$L_n(x)=L_n^{0}(x)$ ($\alpha  =0$).
Furthermore, for each positive integer $m$ and each sequence $(n_1,\ldots,n_m)$
of nonnegative integers let
  $$A(n_1,\ldots,n_m;\alpha  )=(-1)^{n_1+\cdots+n_m}
\int _0 ^\infty  \Bigl(\prod _{i=1}^m L^{(\alpha  )}_{n_i}(x)\Bigr)\, 
x^\alpha   e^{-x}\,dx\leqno(1.2)$$
and
  $$I(n_1,\ldots,n_m;\alpha  )
={1 \over  \Gamma (\alpha  +1)}
n_1!\,\ldots\,n_m!\, A(n_1,\ldots,n_m;\alpha  ).\leqno(1.3)$$
Then \pd GILLIS and \pd EVEN [7] found a combinatorial
interpretation for $I(n_1,\ldots,n_m;0)$ ($\alpha  =0$)
and deduced from that interpretation
the fact that $I(n_1,\ldots,n_m;0)$ was positive. The positivity
property was immediately reproved by \pd ASKEY and his
followers [1, 2, 3, 8] by means of analytical methods and
reincluded in a more general special function set-up. As they
noticed, the generating function (1.1) yields the identity :
  $$\sum A(n_1,\ldots,n_m;\alpha  )x_1^{n_1}\ldots x_m^{n_m}=
{\Gamma (\alpha  +1) \over  (1 - \sigma _2 - 2\sigma _3 - 
\cdots -(m-1)\sigma _m)^{\alpha  +1} },\leqno(1.4)$$
where $n_1,\ldots,n_m$ runs over all nonnegative integers 
and $\sigma _j$ denotes the
$j$-th elementary symmetric function in $x_1,\ldots,x_m$.
As it was shown by \pd ASKEY and his coauthors, the positivity
of $I(n_1,\ldots,n_m;\alpha  )$ is an immediate
consequence of (1.4) and it holds for $\alpha  >-1$.
In [1, p. 857--858] the authors were very close to finding
a combinatorial interpretation of $I(n_1,\ldots,n_m;\alpha  )$
for an arbitrary $\alpha  $. It is the purpose of this paper 
to provide one by taking up again the combinatorial model introduced
by \pd GILLIS and \pd EVEN [7] and ``$\alpha  $-extending''~it.
Let ${\cal P}(n_1,\ldots,n_m)$ be
the set of permutations on the $n_1+\cdots+n_m$ elements 
  $$a_{1,1},\ldots,a_{1,n_1};
\ldots ; a_{m,1},\ldots,a_{m,n_m}$$
and denote by ${\cal D}(n_1,\ldots,n_m)$
the subset of ${\cal P}(n_1,\ldots,n_m)$ consisting 
of what we will call $(a_1,\ldots,a_m)$-derangements. These are
permutations where no element is allowed to go to one
of its kind ; in other words, columns of the form
  $$\matrix{a_{1,i}&\ldots&a_{m,i}\cr
            a_{1,j}&\ldots&a_{m,j}\cr}$$
are forbidden in the two-line representation of the permutation.
The following identity is due to \pd GILLIS and \pd EVENS [7] : 
  $$I(n_1,\ldots,n_m;0)={\rm card}\,{\cal D}(n_1,\ldots,n_m).\leqno(1.5)$$
In order to have an extension for {\it any} $\alpha  $ 
introduce for each permutation $\pi $ its number of cycles $\cyc \pi $ 
and define its {\sl weight} by
  $$w(\pi )=(\alpha  +1)^{\cyc \pi }.\leqno(1.6)$$
The polynomial
  $$D(n_1,\ldots,n_m;\alpha  )=\sum _\pi  w(\pi )\qquad
\bigl(\pi \in {\cal D}(n_1,\ldots,n_m)\bigr)$$
reduces to ${\rm card}\,{\cal D}(n_1,\ldots,n_m)$ when 
$\alpha  =0$.
Our $\alpha  $-analog of the Gillis-Even result now reads :

\th Theorem 1|For each indeterminate $\alpha  $ one has :
  $$I(n_1,\ldots,n_m;\alpha  )=D(n_1,\ldots,n_m;\alpha  ).\leqno(1.7)$$
\finth

As all the weights in $D(n_1,\ldots,n_m;\alpha  )$
are nonnegative whenever $\alpha  >-1$, then
the forementioned theorem implies that
$I(n_1,\ldots,n_m;\alpha  )$ is also nonnegative, as was proved
by \pc ASKEY| et al. [1,~2].

We give two proofs of \pd THEOREM 1. The first one is
based on the combinatorial interpretation of the Laguerre
polynomials. The product (1.3) is expanded and the
various terms interpreted in terms of generating
polynomials for permutations and injections (see sections~2
and~3). The second one relies on an $\beta $-analog
of the celebrated \pc MACMAHON|'s Master Theorem [9, p.~97].
This $\beta $-analog has an interest of its own and will be
discussed in section~4. The second proof is then
completed in section~5.

\section 2. Cycles|We will need two results that are fundamental in the
current combinatorial interpretation of special functions.
First, the generating function for the set ${\cal P}(n)$ 
of all the permutations on $n$ elements by
number of cycles is given by (see, e.g., [10, p.~78])
  $$w\bigl({\cal P}(n)\bigr)
=\sum _\pi \,w(\pi )=(\alpha  +1)_n=(\alpha  +1)(\alpha  +2)\ldots(\alpha  +n)
\qquad\bigl(\pi \in {\cal P}(n)\bigr).\leqno(2.1)$$

Let $1\le k\le n$ and $S$ be a $(n-k)$-element subset of the
$n$-element $[n]$. The set of {\sl injections} from
$S$ into $[n]$ will be denoted by ${\rm Inj}(S,n)$.
An injection from $S$ to $[n]$ consists of a (possibly empty)
collection of cycles within $S$ and some paths that 
wander in $S$, but terminate at a point outside $S$.
Similarly, denote by $\cyc \pi $ the number of cycles
of $\pi $ and define its {\sl weight} by 
 $w(\pi )=(\alpha  +1)^{\cyc \pi }$.

For example, if $S=\{1,2,3,4,5,6\}$ and $n=9$, then
$(1,3)$, $(2)$, $4\rightarrow 5\rightarrow 7$, $6\rightarrow 8$ is 
an injection with weight
$(\alpha  +1)^2$. 

The result analogous to (1.1) reads (see [6, lemma~2.1]) :
if ${\rm card}\,S=n-k$, then
  $$w\bigl({\rm Inj}(S,n)\bigr)=\sum _\pi  w(\pi )=(\alpha  +1+k)_{n-k}\qquad
(\pi \in {\rm Inj}(S,n)).\leqno(2.2)$$

\section 3. Proof of theorem 1|By the definition
of the Laguerre polynomials
  $$n_i!\,L_{n_i}^{(\alpha  )}(x)
=\sum _{k_i=0}^{n_i} (-1)^{k_i} {n_i\choose k_i}
(\alpha  +1+k_i)_{n_i-k_i}\, x^{k_i}\qquad (i=1,\ldots,m).$$
In (1.2) and (1.3) expand each Laguerre polynomial and
integrate term by term using the fact that
$(1/\Gamma (\alpha  +1))\int _0^\infty  e^{-x} x^{n+\alpha  }\, dx
= (\alpha  +1)_n$. This leads to :
  $$\displaylines{(3.1)\quad I(n_1,\ldots,n_m;\alpha  )\hfill\cr
\hfill{}=
\sum _{k_1=0}^{n_1}\!\cdots\!\sum _{k_m=0}^{n_m}
(\alpha  +1)_{k_1+\cdots+k_m}
\prod _{i=1}^m (-1)^{n_i-k_i}
{n_i\choose k_i}
(\alpha  +1+k_i)_{n_i-k_i}.\quad\cr}$$
Consider now {\it any} permutation in ${\cal P}(n_1,\ldots,n_m)$
and write it in {\it cycle form}. An element will
be called {\it incestuous}, if it is sent
to one of its own kind. Denote by $\Inc \pi $ the set
of all incestuous elements of $\pi $.

For example, in the permutation
belonging to ${\cal P}(4,5,5)$ 
  $$(a_1b_1b_2c_3a_2)(c_2c_1b_3a_3)(c_4b_4a_4c_5)$$
the elements $b_1$, $a_2$, $c_2$, $c_5$ are the incestuous
elements. 

Now call {\it marked permutation} an ordered pair
$(\pi ,S)$ with $\pi $ a permutation and $S$ a
subset of $\Inc \pi $ and denote by ${\cal M}(n_1,\ldots,n_m)$
the set of {\it marked permutations}.

For example, 
  $$(a_1\overline{b_1}b_2c_3a_2)(\overline{c_2}c_1b_3a_3)
(c_4b_4a_4\overline{c_5})$$
is the marked permutation where the incestuous elements
$b_1$, $c_2$, $c_5$ are marked ($S=\{b_1,c_2,c_5\}$) 
while the incestuous element
$a_2$ is not marked. 

Define the {\it weight} of each marked permutation $(\pi ,S)$ by
  $$w'(\pi ,S)=(-1)^{\card S}(\alpha  +1)^{\cyc \pi }$$
and consider the generating polynomial for marked permutations :
  $$M(n_1,\ldots,n_m;\alpha  )=\sum _\pi  w'(\pi )\qquad
\bigl(\pi \in {\cal M}(n_1,\ldots,n_m)\bigr).$$
This generating polynomial will be computed in two 
different ways. One of these ways yields 
  $$M(n_1,\ldots,n_m;\alpha  )=D(n_1,\ldots,n_m;\alpha  ).\leqno(3.2)$$
The other way will give :
  $$M(n_1,\ldots,n_m;\alpha  )=I(n_1,\ldots,n_m;\alpha  ).\leqno(3.3)$$

Consider the following weight preserving sign changing involution
on marked permutations. Look at the first incestuous element. 
If it is marked, unmark it ; if it is unmarked, mark it. Of course,
the number of cycles of the permutation does not change (since there
is no change in the underlying permutation !). Only the parity
of the number of marks changes, reversing the sign of the weight.
Accordingly, all the terms in $M(n_1,\ldots,n_m;\alpha  )$ corresponding
to permutations with incestuous elements can be arranged in
mutually cancelling pairs and their sum is therefore zero.
All that remains in $M(n_1,\ldots,n_m;\alpha  )$ are the terms
corresponding to those marked permutations
$(\pi ,S)$ containing no incestuous elements and so $S=\emptyset $. 
But those marked permutations are simply the pairs $(\pi ,\emptyset )$
with $\pi \in {\cal D}(n_1,\ldots,n_m)$ and they satisfy :
$w'(\pi ,\emptyset )=w(\pi )$. Therefore (3.2) holds.

Now compute $M(n_1,\ldots,n_m;\alpha  )$ in a different way.
For each $i=1,\ldots,m$ let $S_i$ be a certain subset of
$\{a_{i,1},\ldots,a_{i,n_i}\}$ of cardinality $n_i-k_i$
and denote by ${\cal M}({\bf S})$ the subset of
${\cal M}(n_1,\ldots,n_n)$ consisting of marked permutations
$(\pi ,S)$ with $S=S_1\cup \cdots\cup S_m$.
Also let ${\cal P}({\bf S})$ the set of all $\pi $ in
${\cal P}(n_1,\ldots,n_m)$ such that
$(\pi ,S)\in {\cal M}({\bf S})$. Clearly,
  $$w'\bigl({\cal M}({\bf S})\bigr)=
(-1)^{n_1-k_1+\cdots+n_m-k_m}
w\bigl({\cal P}({\bf S})\bigr).\leqno(3.4)$$

\th Lemma|One has
  $$w\bigl({\cal P}({\bf S})\bigr)
=(\alpha  +1)_{k_1+\cdots+k_m}
\prod _{i=1}^m (\alpha  +1+k_i)_{n_i-k_i}.\leqno(3.5)$$
\finth

{\it Proof}\pointir From (2.1) and (2.2) it follows that
the right-hand side of (3.5) is the
generating function for the product
  $${\cal P}(k_1,\ldots,k_m)\times \prod _{i=1}^m {\rm Inj}(S_i,n_i)$$
by $w$. To prove the lemma it then suffices to
construct a $w$-weight preserving bijection 
$\pi \mapsto (\pi _1,\ldots,\pi _m,\sigma )$ of
${\cal P}({\bf S})$ onto that product.
Write $\pi $ in cycle form. Then in each
cycle of $\pi $ delete all the elements of 
$S=S_1\cup \cdots\cup S_m$.
What remains is a permutation written in cycle form. 
Call it $\sigma $.

To get $\pi _i$ take all the cycles of $\pi $ 
consisting {\it only} of elements of $S_i$. Take also
the connected portions of $S_i$ lying in other cycles.
Doing this will result in a certain number of {\it paths}
that wander through $S_i$ but terminate in an element
not in $S_i$. 

Clearly, $\sigma $ belongs to ${\cal P}(k_1,\ldots,k_m)$ and each
$\pi _i$ is an injection of $S_i$ into $\{a_{i,1},\ldots,a_{i,n_i}\}$.
Moreover, the total number of cycles of $\sigma ,\pi _1,\ldots,\pi _m$
is equal to $\cyc \pi $. Thus, the mapping is $w$-preserving. 
The reverse construction is immediate.\qed 

\rem Example|Take 
  $$\vbox{\halign{$#$\hfil&\quad $#$\hfil&\quad $#$\hfil\cr 
n_1=6&n_2=6&n_3=6\cr
\noalign{\vskip 3pt}
k_1=3&k_2=3&k_3=3\cr
\noalign{\vskip 3pt }
S_1=\{a_1,a_2,a_3\}&S_2=\{b_1,b_2,b_3\}&S_3=\{c_1,c_2,c_3\}\cr
\multispan3\hfil$\pi =(a_1a_2)(a_4b_1b_5a_5a_3)(b_2b_4c_1c_4c_3c_2c_6)
(c_5a_6)(b_3)(b_6)$\hfil\cr}}$$
Then 
  $$\vbox{\halign{$#$\hfil\cr
\sigma =(a_4b_5a_5)(b_4c_4c_6)(c_5c_6)(b_6)\cr
\noalign{\vskip 3pt }
\pi _1=(a_1a_2),\quad a_3\rightarrow a_4\cr
\noalign{\vskip 3pt }
\pi _2=(b_3),\quad b_1\rightarrow b_5,\quad b_2\rightarrow  b_4\cr
\noalign{\vskip 3pt }
\pi _3=c_1\rightarrow c_4,\quad c_3\rightarrow c_2\rightarrow c_6\cr}}$$

It follows from (3.4) and (3.5) that
  $$w'\bigl({\cal M}({\bf S})\bigr)
=(-1)^{n_1-k_1+\cdots+n_m-k_m}
(\alpha  +1)_{k_1+\cdots+k_m}\prod _{i=1}^m 
(\alpha  +1+k_i)_{n_i-k_i}.$$
Hence
  $$\eqalign{M(n_1,\ldots,n_m;\alpha  )&=\sum w'\bigl({\cal M}
({\bf S})\bigr)\cr
&=\sum _{k_1=0}^{n_1}\!\cdots\!\sum _{k_m=0}^{n_m}
\prod _{i=1}^m{n_i\choose k_i}\sum w'\bigl({\cal M}
({\bf S})\bigr)\cr
&=\sum _{k_1=0}^{n_1}\!\cdots\!\sum _{k_m=0}^{n_m}
(\alpha  +1)_{k_1+\cdots+k_m}\cr
&\qquad\qquad{}\times \prod _{i=1}^m (-1)^{n_i-k_i}
{n_i\choose k_i}
(\alpha  +1+k_i)_{n_i-k_i},\cr}$$
which is the expression found for 
$I(n_1,\ldots,n_m;\alpha  )$ in (3.1). Therefore,
(3.3) is proved and also \pc THEOREM|~1.

\section 4. The $\beta $-analog of the MacMahon Master 
Theorem|Let $D$ be the determinant ${\rm det}(\delta _{ij}-b(i,j)x_j)$
$(1\le i,j\le m)$. The MacMahon Master Theorem asserts that the
coefficient of $x_1^{n_1}\ldots x_m^{n_m}$ in the expansion of
$D^{-1}$ is equal to the coefficient of
$x_1^{n_1}\ldots x_m^{n_m}$ in 
the product
  $$\bigl(b(1,1)x_1+\cdots+b(1,m)x_m\bigr)^{n_1}\ldots
\bigl(b(m,1)x_1+\cdots+b(m,m)x_m\bigr)^{n_m}.\leqno(4.1)$$

It will be convenient to restate this statement in
a slightly different form. Let
${\cal R}(n_1,\ldots,n_m)$ denote the set of all the rearrangements
  $$r=r(1,1)\ldots r(1,n_1)\ldots r(m,1)\ldots r(m,n_m)$$
of the word $1^{n_1}\ldots m^{n_m}$ and let
  $$v(r)=\prod _{i,j} b(i,r(i,j))\qquad(1\le i\le m;\;1\le j\le n_i).$$
Clearly, the coefficient of
$x_1^{n_1}\ldots x_m^{n_m}$ in 
(4.1) is equal to the sum of all the $v(r)$
with $r$ running over all the rearrangements of
$1^{n_1}\ldots m^{n_m}$.

Next, consider a permutation $\pi $ belonging to
${\cal P}(n_1,\ldots,n_m)$ (defined
in section~1). If $\pi $ sends $(i,j)$ over $(i',j')$,
write $i'=c\pi (i,j)$. Furthermore, define
  $$v(\pi )=\prod _{i,j} b(i,c\pi (i,j))
\qquad(1\le i\le m;\;1\le j\le n_i).$$
To each rearrangement $r$ in ${\cal R}(n_1,\ldots,n_m)$
there correspond exactly $n_1!\,\ldots\,n_m!$
permutations $\pi $ in ${\cal P}(n_1,\ldots,n_m)$
with the property that $v(\pi )=v(r)$. Therefore,
{\it the coefficient of
$x_1^{n_1}\ldots x_m^{n_m}$ in 
{\rm (4.1)} is also equal to}
  $$n_1!\,\ldots\,n_m!\,\sum _\pi  v(\pi )\qquad
(\pi \in {\cal P}(n_1,\ldots,n_m).
\leqno(4.2)$$
The MacMahon Master identity can then be restated as
  $$\sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl({\cal P}(n_1,\ldots,n_m)\bigr)
=D^{-1}.\leqno(4.3)$$

Next define the $\beta $-weight $v(\beta ;\pi )$ of
each permutation $\pi $ in ${\cal P}(n_1,\ldots,n_m)$ by
  $$v(\beta ;\pi )=\beta ^{\cyc \pi }v(\pi ).$$

\th Theorem {\rm ($\beta $-analog of the MacMahon Master 
Theorem)}|The following identity holds :
  $$\sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl(\beta ;{\cal P}(n_1,\ldots,n_m)\bigr)
=D^{-\beta }.\leqno(4.4)$$
\finth

{\it Proof}\pointir Consider the partitional complex 
(see, e.g., [4, 5]) of the permutations and denote by
${\cal CP}(n_1,\ldots,n_m)$ the subset
of the {\it connected} permutations in ${\cal P}(n_1,\ldots,n_m)$. 
As the weight $v(\beta ;\cdot)$ is {\it multiplicative}
[4,~5], the following identity holds :
  $$\displaylines{(4.5)\quad \sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl(\beta ;{\cal P}(n_1,\ldots,n_m)\bigr)\hfill\cr
\hfill{}=\exp\sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl(\beta ;{\cal CP}(n_1,\ldots,n_m)\bigr).\quad\cr}$$
From (4.3) and (4.5) with $\beta =1$
  $$\sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl({\cal CP}(n_1,\ldots,n_m)\bigr)
=-{\rm Log}\,D.$$
But $v(\beta ;\pi )=\beta v(\pi )$ for every connected
permutation, so that
  $$\sum {x_1^{n_1}\over n_1!} \ldots
{x_m^{n_m}\over n_m!}\,
v\bigl(\beta ;{\cal CP}(n_1,\ldots,n_m)\bigr)
=-\beta {\rm Log}\,D,$$
and finally (4.4) holds because of (4.5).\qed

\section 5. Second proof of theorem 1|As was noted by
\pc ASKEY| [1,~2], (1.4) is an immediate consequence
of (1.1). Rewriting (1.4) for $\alpha  =0$ using 
\pc GILLIS|-\pc EVEN|'s result (1.5) yields :
  $$\sum \card {\cal D}(n_1,\ldots,n_m)
{x_1^{n_1}\over n_1!}\ldots {x_m^{n_m}\over n_m!}=
\bigl(1 - \sigma _2 - 2\sigma _3 - \cdots -(m-1)
\sigma _m\bigr)^{-1}.\leqno(5.1)$$
Take again the $v$-weight of section~4 with
$b(i,j)=\delta _{ij}$. Then,
  $$\card{\cal D}(n_1,\ldots,n_m)
=v\bigl({\cal P}(n_1,\ldots,n_m)\bigr).
\leqno(5.2)$$
Thus for this particular $v$ identity (4.4) holds with
$\beta =\alpha  +1$ and
  $$D=\bigl(1 - \sigma _2 - 2\sigma _3 - \cdots (m-1)\sigma _m\bigr).$$
On the account of (1.2), (1.3), (1.4) and (4.4) with this
particular weight $v$ we conclude that (1.7) also holds.

\vskip 44pt
\goodbreak
\eightpoint
\centerline{REFERENCES}
\vskip 10pt
\article 1|\pd ASKEY (Richard) and \pd ISMAIL (Mourad E.H.)|Permutation
problems and special functions|Canad. J. Math.|28|1976|853--874|
\article 2|\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 3|\pd ASKEY (Richard) and \pd GASPER (G.)|Convolution
structures for Laguerre polynomials|J. d'Anal. Math.|31|1977|46--48|
\livre 4|\pd FOATA (Dominique)|La s\'erie g\'en\'eratrice exponentielle
dans les probl\`emes d'\'enum\'eration|Montr\'eal, Presses de
l'Universit\'e de Montr\'eal, $\oldstyle 1974$|
\livre 5|\pd FOATA (Dominique) et \pd SCH\"UTZENBERGER 
(Marcel-Paul)|Th\'eorie g\'eo\-m\'e\-tri\-que des polyn\^omes
eul\'eriens|Berlin, Springer-Verlag, $\oldstyle1970$ ({\it
Lecture Notes in Math.}, {\bf 138})| 
\divers 6|\pd FOATA (Dominique) and \pd STREHL
(Volker)|Combinatorics of Laguerre polynomials, {\sl Enumeration
and Design} [Waterloo. June--July $\oldstyle 1982$ : D.M.
Jackson and S.A. Vanstone, eds.], p.~123--140\pointir Toronto,
Academic Press, $\oldstyle 1984$| 
\article 7|\pd GILLIS (J.) and \pd EVEN (S.)|Derangements and
Laguerre polynomials|Proc. Cambridge
Phil. Soc.|79|1976|135--143|   
\article 8|\pd ISMAIL (Mourad E.H.)
and \pd TAMHANKAR (M.V.)|A combinatorial approach to some
positivity problems|S.I.A.M. J. Math. Anal.|10|1979|478--485|  
\livre 9|{\pc MAC|\pc MAHON|} (Percy Alexander)|Combinatory
Analysis, {\rm vol.~1}|Cambridge, Univ. Press, $\oldstyle 1915$.
(Reprinted by Chelsea, New York, $\oldstyle 1955$)|  
\livre 10|\pd RIORDAN (John)|An Introduction to Combinatorial
Analysis|New York, John Wiley, $\oldstyle 1959$|

\tenpoint
\bigskip\bigskip
The present paper has been completed and updated to become :

\medskip
\noindent
Dominique Foata and Doron Zeilberger,
Laguerre polynomials, weighted derangements 
and positivity, {\sl SIAM J. Discrete 
Math.}, vol.~{\bf 1}, $\oldstyle 1988$,
p.~425--433.

\adresse
Dominique {\petcap Foata},
D\'epartement de math\'ematique,
Universit\'e Louis-Pasteur,
7, rue Ren\'e-Descartes,
F-67084 Strasbourg, France.

and

Doron {\petcap Zeilberger},
Department of Mathematics,
Drexel University,
Philadelphia, Pennsylvania 19104, U.S.A.
now at the address :
Temple University,
Philadelphia, Pennsylvania 19122, U.S.A.

\fin

\bye
