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