%This is a plain tex file %\batchmode {\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 \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=eufm7 at 8pt \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.5cm plus .5cm minus .1cm\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} \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\vskip1cm 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 } \newcount\eqnumber \eqnumber=0 \def\assigneqno(#1){\global\advance\eqnumber by1 \expandafter\xdef\csname#1\endcsname {\the \sectionnumber.\the\eqnumber}} \def\eqno(#1){\assigneqno(#1) \leqno(\the \sectionnumber.\the\eqnumber)} \def\(#1){(\csname#1\endcsname)} % \def\eqalignno#1{ \displ@y \tabskip \centering \halign to\displaywidth {\hfil $\displaystyle {##}$\tabskip \z@skip &$\displaystyle {{}##}$\hfil \tabskip \centering &\kern-\displaywidth %new part--replaces \rlap{$##$} in original \leqalignno \def\next{##} \ifx\next\empty\else\expandafter\assigneqno\next \rlap{$(\the \sectionnumber.\the\eqnumber)$}\fi %return to original version \tabskip\displaywidth \crcr #1\crcr }} \newcount\sectionnumber \sectionnumber=0 \def \section #1| {\par\vskip .3cm \eqnumber=0 \advance \sectionnumber by1 {\bf \the\sectionnumber. #1}\pointir} \newcount \refno \refno=0 \def\inewcount{\alloc@ 0\count \countdef \insc@unt} %inner \newcount \def\\#1|#2\par{\global\advance\refno by 1 \expandafter\inewcount\csname #1\endcsname \global\csname #1\endcsname=\refno} \catcode`\@=12 %I'm sure these \expandafters wouldn't be necessary %if I did this right, but at least it works this way. \begingroup\def\article{} \def \livre{} \def\divers{} \expandafter\livre \\c-f|\pd CARTIER (P.) and \pd FOATA (D.)|Probl\`emes combinatoire de commutation et r\'earrangements|Springer-Verlag, $\oldstyle1969$ ({\it Lecture Notes in Math.\/}, {\bf 85})| \expandafter\article \\e&s|\pd EVERETT (C.J.) and \pd STEIN (P.R.)|The asymptotic number of integer stochastic matrices|Discrete Math.|1|1971|55--72| \expandafter\article \\gessel|\pd GESSEL (I.M.)|Two theorems on rational power series|Utilitas Math.|19|1981|247--254| \expandafter\article\\latin|\pd GESSEL (I.M.)|Counting Latin rectangles|Bull. Amer. Math. Soc.|16|1987|79--82| \expandafter\livre \\gjbook|\pd GOULDEN (I.P.) and \pd JACKSON (D.M.)|Combinatorial Enumeration|Wiley, $\oldstyle1983$| \expandafter\article \\goul2|\pd GOULDEN (I.P.) and \pd JACKSON (D.M.)|Labelled graphs with small vertex degrees and P-recursiveness|SIAM J. Alg. Disc. Meth.|7|1986|60--66| \expandafter\article \\goul1|\pd GOULDEN (I.P.), \pd JACKSON (D.M.), and \pd REILLY (J. W.)|The Hammond series of a symmetric function and its application to P-recursiveness|SIAM J. Alg. Disc. Meth.|4|1983|179--193| \expandafter\divers \\hall|\pd HALL (P.)|The algebra of partitions, {\sl Proc. 4th Canadian Math. Cong.} [Banff. $\oldstyle1957$], p.~147--159\pointir $\oldstyle1959$| \expandafter\divers \\lip|\pd LIPSHITZ (L.)|The diagonal of a D-finite power series is D-finite, {\sl J. Algebra}, to be published| \expandafter\divers \\lip2|\pd LIPSHITZ (L.)|D-finite power series, preprint| \expandafter\article \\little|\pd LITTLEWOOD (D.E.)|The Kronecker product of symmetric group representations|J. London Math. Soc.|31|1956|89--93| \expandafter\livre \\mac|\pd MACDONALD (I.G.)|Symmetric Functions and Hall Polynomials|Oxford University Press, $\oldstyle1979$| \expandafter\article \\macm2|{\pc MAC|\pc MAHON|} (P.A.)|Combinatory Analysis. The foundations of a new theory|Phil. Trans.|194|1900|361--386| \expandafter\livre \\macbook|{\pc MAC|\pc MAHON|} (P.A.)|Combinatory Analysis|Chelsea, $\oldstyle1960$. (Originally published by Cambridge University Press, $\oldstyle1915, 1916$)| \expandafter\article\\read0|\pd READ (R.C.)|The enumeration of locally restricted graphs (I)|J. London Math. Soc.|34|1959|417--436| \expandafter\article\\read1|\pd READ (R.C.)|The enumeration of locally restricted graphs (II)|J. London Math. Soc.|35|1960|334--351| \expandafter\article \\read3|\pd READ (R.C.)|The use of S-functions in combinatorial analysis|Canad. J. Math.|20|1968|808--841| \expandafter\article \\read2|\pd READ (R.C.) and \pd WORMALD (N.C.)|Number of labelled 4-regular graphs|J. Graph Theory|4|1980|203--212| \expandafter\article \\redfield|\pd REDFIELD (J.H.)|The theory of group reduced distributions|American J. Math.|49|1927|433--455| \expandafter\article \\stan|\pd STANLEY (R.P.)|Differentiably finite power series|European J. Combin.|1|1980|175--188| \expandafter\livre \\stanbook|\pd STANLEY (R.P.)|Enumerative Combinatorics, Volume I|Wadsworth, $\oldstyle1986$| \expandafter\article\\zeil|\pd ZEILBERGER (D.)|Sister Celine's technique and its generalizations|J. Math. Anal. Appl.|85|1982|114--145| \endgroup \def \ref#1{\the\csname#1\endcsname} \def \[#1]{[\the\csname #1\endcsname]} \def \proof {{\it Proof}\pointir} \def\N{{\bf N}} \let \l \lambda \let \m\mu \def\<{\left\langle} \def\>{\right\rangle} \def \x{{\bf x}} \def \n{{\bf n}} \def \l{\lambda} \def\d{\delta} \def\m{\mu}\def\n{\nu} \def \suminf#1{\sum_{#1=0}^\infty} \pageno=5 \auteurcourant={I.M. GESSEL} \titrecourant={SYMMETRIC FUNCTIONS} \eightpoint \leftline{Publ. I.R.M.A. Strasbourg, $\oldstyle 1987$, 229/S--08} \leftline{Actes 17\emini\ S\'eminaire Lotharingien, p. 5-21} \tenpoint \vskip 1.5cm \centerline{{\bf ENUMERATIVE APPLICATIONS }} \vskip 5pt \centerline{{\bf OF SYMMETRIC FUNCTIONS}} \vskip 2.8mm \centerline{\sevenrm BY} \vskip 2.8mm \centerline{{\petcap Ira M.} GESSEL\footnote {$^1$}{\kern -.3em partially supported by NSF grant DMS-8504134}} \vskip 1cm \section Introduction| This paper consists of two related parts. In the first part the theory of D-finite power series in several variables and the theory of symmetric functions are used to prove P-recursiveness for regular graphs and digraphs and related objects, that is, that their counting sequences satisfy linear homogeneous recurrences with polynomial coefficients. Previously this has been accomplished only for small degrees. See, for example, \pc GOULDEN|, \pd JACKSON, and \pd REILLY \[goul1], \pd GOULDEN and \pd JACKSON \[goul2], and \pd READ [\ref{read1}, \ref{read2}]. These authors found the recurrences satisfied by the sequences in question. Although the methods used here are in principle constructive, we are concerned here only with the question of existence of these recurrences and we do not find them. In the second part we consider a generalization of symmetric functions in several sets of variables, first studied by \pc MAC|\pc MAHON| [\ref{macm2}; \ref{macbook}, Vol. 2, pp. 280--326]. MacMahon's generalized symmetric functions can be used to find explicit formulas and prove P-recursiveness for some objects to which the theory of ordinary symmetric functions does not apply, such as Latin rectangles and 0-1 matrices with zeros on the diagonal and given row and column sums. \titre I. Symmetric functions and P-recursiveness| \section {D-finite power series and P-recursive functions}| A formal power series $f(x)$ is said to be {\it D-finite} (or {\it differentiably finite}) if $f$ satisfies a linear homogeneous differential equation with polynomial coefficients. An equivalent condition is that the set of derivatives of $f$ spans a finite-dimensional vector space over the field of rational functions in $x$. A function $a(n)$ defined on the nonnegative integers is said to be {\it P-recursive} (or {\it polynomially recursive}) if there exist polynomials \hbox{$p_0(n)$, $p_1(n)$, \dots, $p_k(n)$} such that $$\sum_{i=0}^k p_i(n)a(n+i)=0$$ for all nonnegative integers $n$. The fundamental fact relating these two concepts is that $a(n)$ is P-recursive if and only if its generating function $\suminf n a(n)x^n$ is D-finite. We refer the reader to \pd STANLEY \[stan] for the proof of this and other basic facts. In this paper we show that counting sequences for certain combinatorial problems which can be expressed as coefficients of symmetric functions are P-recursive. To do this we need a multivariable generalization of the theory of D-finiteness and P-recursiveness. Such a generalization was first given by \pd ZEILBERGER \[zeil]. However, Zeilberger's definition of multivariable P-recursiveness is not suitable for our purposes. A more useful definition of multivariable P-recursiveness has been given by \pd LIPSHITZ \[lip2], but we shall work only with multivariable D-finiteness. The theory of D-finiteness generalizes easily to the multivariable case. In the next section we define multivariable D-finiteness and describe some of its properties. \section {D-finite power series in several variables}| First we discuss the theory of D-finite power series. Let $I$ be an integral domain and let $F$ be the quotient field of $I[x_1,x_2,\ldots, x_n]$. Let $f(x_1,x_2,\ldots, x_n)$ be a formal power series in $I[[x_1, x_2,\ldots, x_n]]$. We say that $f(x)$ is {\it D-finite} in the variables $x_1$, $x_2$, \dots, $x_n$ if the set of all partial derivatives $\displaystyle{\partial^{i_1+\cdots+i_n}f \over \partial x_1^{i_1}\cdots \partial x_n^{i_n}} $ spans a finite-dimensional vector space over $F$ (as a subspace of the tensor product $F\otimes_{I[x_1,\ldots,x_n]}I[[x_1,x_2,\ldots, x_n]]$). The following lemma contains some of the basic facts about D-finite power series in several variables that we will need: \tha Lemma 1| \item {\rm(i)} The set of D-finite power series forms an $I$-subalgebra of $I[[x_1,\ldots, x_n]]$. \item{\rm(ii)} If $f$ is D-finite in $x_1,x_2,\ldots,x_n$ then $f$ is D-finite in any subset of $x_1,x_2,\ldots,x_n$. \item{\rm(iii)} If $f(x_1,x_2,\ldots,x_n)$ is D-finite in $x_1,x_2,\ldots,x_n$ and for each $i$, $r_i$ is a polynomial in the variables $y_1$, $y_2$, \dots, $y_m$, (which may include some or all of the $x_i$) then $f(r_1, r_2, \ldots, r_n)$ is D-finite in $y_1$, $y_2$, \dots, $y_m$, as long as it is well-defined as a formal power series. \item{\rm(iv)} If $P(x)$ is a polynomial in $x_1,x_2,\ldots,x_n$ then $e^{P(x)}$ is D-finite. \fintha The proofs of these statements are straightforward, and are similar to proofs for the one-variable case given by \pd STANLEY \[stan]. (See also \pd LIPSHITZ \[lip2].) We need one further fact about D-finite power series in several variables, due to \pd LIPSHITZ \[lip], which is somewhat harder to prove. If $A(x)=\sum a(i_1,\ldots, i_n)x_1^{i_1}\cdots x_n^{i_n}$ and $B(x)=\sum b(i_1,\ldots, i_n)x_1^{i_1}\cdots x_n^{i_n}$, then the Hadamard product $A(x)\odot B(x)$ with respect to the variables $x_1,x_2,\ldots,x_n$ is defined to be $$\sum a(i_1,\ldots, i_n) b(i_1,\ldots, i_n)x_1^{i_1}\cdots x_n^{i_n}.$$ Note that the $a$'s and $b$'s may involve other variables. \th Lemma 2 {\rm(\pd LIPSHITZ \[lip])}|Suppose that $A$ and $B$ are D-finite in the variables $x_1$,$x_2$, \dots, $x_{m+n}$. Then the Hadamard product $A\odot B$ with respect to the variables $x_1,x_2,\ldots,x_n$ is D-finite in $x_1,x_2,\ldots, x_{m+n}$.\finth Now suppose that $f$ is a formal power series in an infinite set $X$ of variables. For any subset $S$ of $X$ let $f_S$ be the formal power series in the variables in $S$ obtained by setting to zero all the variables in $X-S$. We shall say that $f$ is D-finite in $X$ if $f_S$ is D-finite in $S$ for every finite subset $S$ of $X$. With this definition, all the properties of D-finite series in finitely many variables are easily seen to remain valid, except that in Lemma 1(iii) we may only substitute for finitely many variables. \section {Symmetric functions}| We recall some facts about symmetric functions. We refer the reader to \pd MACDONALD \[mac] for proofs and details. We work with symmetric functions in the infinitely many variables $x_1, x_2, \ldots$ with coefficients in a field of characteristic zero. We will be concerned with the following particular symmetric functions: The {\it power sum} symmetric function $p_n$ is defined by $$p_n=\sum_i x_i^n.$$ More generally, if $\l=\l_1\l_2\cdots\l_k$ is a partition, we define $p_\l=p_{\l_1}p_{\l_2}\cdots p_{\l_k}$. The {\it elementary} symmetric function $e_n$ is defined by $$e_n=\sum_{i_1< i_2<\cdots$. Now let $b_n$ be the number of $n\times n$ nonnegative integer matrices with every row and column sum equal to $k$. It follows that $$b(t)=\suminf n b_nt^n=\langle h(xy), g(x,y)\rangle,\eqno(11)$$ where $g(x,y)$ is given by $g(x,y)=\bigl(1-th_k(x)h_k(y)\bigr)^{-1}$, and by reasoning as before, $b(t)$ is D-finite. Similarly, $e(xy)$ counts 0-\kern -.2ex 1 matrices with prescribed row and column sums, or equivalently, digraphs without multiple edges with prescribed indegrees and outdegrees. \section Explicit formulas and asymptotics| In all of our examples, we have actually shown something stronger than P-re\-cur\-sive\-ness---we have shown that there exists an explicit formula for the numbers in question as a sum of fixed multiplicity. (In the terminology of Zeilberger, these sums are ``multi-hypergeometric.'') Although these formulas are complicated, they can be used to derive asymptotic approximations. For example, the number of $n\times n$ nonnegative integer matrices with every row and column sum two is % $$\eqalign{ \langle h(xy),h_2^n(x)h_2^n(y)\rangle& =\langle h_2^n,h_2^n\rangle =\left\langle \left({p_1^2+p_2\over2}\right)^{\!n}\!\!\!\!, \left({p_1^2+p_2\over2}\right)^{\!n}\right\rangle \cr &=2^{-2n}\sum_{i,j}{n\choose i}{n\choose j}\langle p_1^{2n-2i}p_2^{i}, p_1^{2n-2j}p_2^{j}\rangle\cr &=2^{-2n}\sum_i {n\choose i}^{\!2} \langle p_1^{2n-2i}p_2^{i},p_1^{2n-2i}p_2^{i}\rangle\cr &=\sum_i 2^{-(2n-i)}{n\choose i}^{\!2} (2n-2i)!\,i!\,.\cr}$$ % It can be shown that asymptotically we may replace each summand by its limit as $n\to\infty$, and thus the sum is asymptotic to $$2^{-2n}(2n)!\sum_{i=0}^\infty{2^i\over i!}\left(1\over2\right)^{2i} =2^{-2n}(2n)!\,e^{1/2}.$$ A more detailed analysis yields a complete asymptotic expansion. More generally, the number of $n\times n$ nonnegative integer matrices with every row and column sum $k$ is $\$, and it can be shown that the major contribution to this scalar product comes from the terms in % $$\displaylines{\quad \left\langle \left({p_1^k\over k!}+{p_1^{k-2}\over (k-2)!}{p_2\over2}\right)^n, \left({p_1^k\over k!}+{p_1^{k-2}\over (k-2)!}{p_2\over2}\right)^n \right\rangle \hfill\cr \hfill= {(kn)!\over k!^{2n}}\sum_{i=0}^n{\bigl(k(k-1)\bigr)^{2i}\over i!\,2^i} {\bigl(n(n-1)\cdots(n-i+1)\bigr)^2\over kn(kn-1)\cdots (kn-2i+1)}. \quad\cr}$$ % The sum is asymptotic to $$ {(kn)!\over k!^{2n}}\sum_{i=0}^\infty{\bigl(k^2(k-1)^2/2\bigr)^i \over i!}\left(1\over k\right)^{2i} = {(kn)!\over k!^{2n}}e^{(k-1)^2/2},$$ as found by \pd EVERETT and \pd STEIN \[e&s], who also used symmetric functions. A similar analysis can be used to obtain asymptotic expansions for related problems, since although in general the formulas have many terms, nearly all are asymptotically insignificant. \titrea II. MacMahon's symmetric functions|of several systems of quantities| \section MacMahon's symmetric functions| Some enumeration problems involve generating functions which are almost, but not quite, symmetric. Here are three examples: \rem Example $1$|The number of $n\times n$ 0-1 matrices with zeros on the diagonal with row sums $r_1$, $r_2$, \dots, $r_m$ and column sums $c_1$, $c_2$, \dots, $c_n$ is the coefficient of $x_1^{r_1}\cdots x_m^{r_m} y_1^{c_1}\cdots y_n^{c_n}$ in $$\prod_{i\ne j}(1+x_iy_j).$$ \rem Example $2$|The number of $3\times n$ Latin rectangles is the coefficient of $x_1x_2\cdots x_n y_1y_2\cdots y_n z_1z_2\cdots z_n$ in $$ \biggl(\sum_{i,j,k}x_iy_jz_k\biggr)^n, $$ where the sum is over all triples of distinct integers $i$, $j$, $k$. \rem Example $3$|Consider the monoid freely generating by the letters $a_1$, $a_2$, \dots, $a_n$, $b_1$, $b_2$, \dots, $b_n$, subject only to the commutation relations $a_ib_i=b_ia_i$. By the \pc CARTIER|-\pd FOATA theory of free partially commutative monoids \[c-f], the number of equivalence classes of words in this monoid with $u_i$ occurrences of $a_i$ and $v_i$ occurrences of $b_i$ is the coefficient of $x_1^{u_1}\dots x_n^{u_n} y_1^{v_1}\dots y_n^{v_n}$ in $$(1-x_1-\cdots x_n-y_1-\cdots - y_n+x_1y_1+\cdots +x_ny_n)^{-1}.$$ One can show that this coefficient is also the number of words in the letters $a_1$, $a_2$, \dots, $a_n$, $b_1$, $b_2$, \dots, $b_n$, with $u_i$ occurrences of $a_i$ and $v_i$ occurrences of $b_i$, containing no consecutive $a_ib_i$. %Similarly, if $a_i$ commutes with $b_j$ whenever $i\ne j$ but no other %commutation relations hold, then the generating function is %$$\biggl(1-x_1-\cdots -x_n -y_1 -\cdots y_n + \sum_{i\ne j} %x_iy_j\biggr)^{-1}=\dots.$$ These generating functions all have the property that they are symmetric under any permutation of the subscripts which acts the same on $x$'s and $y$'s, i.e., the coefficient of $x_1^u y_2^v$ is equal to the coefficient of $x_a^u y_b^v$ as long as $a\ne b$, but need not be equal to the coefficient of $x_1^uy_1^v$. (The usual theory of symmetric functions in two sets of variables applies to symmetric functions which are symmetric independently in the $x$'s and the $y$'s.) These more general symmetric functions were studied by \pc MAC|\pc MAHON| [\ref{macm2}; \ref{macbook}, Vol. 2, pp. 280--326] who called them ``symmetric functions of several systems of quantities.'' MacMahon applied to them his favorite tool for manipulating symmetric functions, Hammond operators, and claimed to have solved the problem of counting Latin rectangles with these operators. His work on these symmetric functions seems to have been ignored, and his claimed solution to the problem of counting Latin rectangles dismissed as impractical and useless. In previous sections we showed how the theory of symmetric functions can be applied to get ``useful'' formulas from symmetric function generating functions, and in particular, to show that certain sequences are $P$-recursive. We now do the same for MacMahon's symmetric functions of several systems of quantities, which we henceforth call MacMahon symmetric functions. First we discuss the fundamental bases for MacMahon symmetric functions and the formulas relating them, which are straightforward generalizations of those for ordinary symmetric functions. For simplicity, we discuss here only MacMahon symmetric functions in two sets of variables. The generalization to more than two presents no difficulties. \section Bases| We take two sets of variables, $x_1$, $x_2$, \dots and $y_1$, $y_2$, \dots. A formal power series $f$ in these variables is a {\it MacMahon symmetric function\/} if whenever $i_1$, $i_2$, \dots, $i_n$ are distinct positive integers, and $a_1$, $a_2$, \dots, $a_n$ and $b_1$, $b_2$, \dots, $b_n$ are nonnegative integers, the coefficient of $x_{i_1}^{a_1}y_{i_1}^{b_1} x_{i_2}^{a_2}y_{i_2}^{b_2}\cdots$ in $f$ is equal to the coefficient of $x_{1}^{a_1}y_{1}^{b_1} x_{2}^{a_2}y_{2}^{b_2}\cdots$ in $f$. Just as bases for ordinary partitions are indexed by partitions of integers, bases for the MacMahon symmetric functions are indexed by bipartite partitions. A {\it bipartite number\/} is an element of $\N\times \N -\{(0,0)\}$, where $\N$ is the set of nonnegative integers. A {\it bipartite partition\/} of the bipartite number $(a,b)$ is a multiset of bipartite numbers with (componentwise) sum $(a,b)$. Thus $\{(0,1),(0,1),(1,0)\}$ is a bipartite partition of $(1,2)$. For simplicity we write $\{(0,1),(0,1),(1,0)\}$ as $(0,1)(0,1)(1,0)$ or as $(0,1)^2(1,0)$. Now if $\l=(a_1,b_1)(a_2,b_2)\cdots$ is a bipartite partition, we define the {\it monomial\/} symmetric function $m_\l$ to be the sum of all monomials of the form $$x_{i_1}^{a_1} y_{i_1}^{b_1} x_{i_2}^{a_2} y_{i_2}^{b_2}\cdots$$ where $i_1$, $i_2$, \dots are distinct. For example, $$\eqalign{ m_{(1,0)(0,1)}&=\sum_{i\ne j}x_iy_j\cr m_{(1,1)}&=\sum_i x_i y_i\cr m_{(1,1)(1,1)}&=\sum_{i0}(-1)^{k+l-1}{1\over k+l}{k+l \choose l} p_{(k,l)}s^kt^l\biggr) \eqno(3)$$ and $$1+\sum_{a,b}h_{(a,b)} s^at^b=\exp\biggl(\sum_{k+l>0}{1\over k+l}{k+l \choose l} p_{(k,l)}s^kt^l\biggr). \eqno(4)$$ We now show that $\{e_\l\}$, $\{h_\l\}$, and $\{p_\l\}$ are in fact bases. Since they have the right cardinality, it is sufficient to show that they span, and in view of \(3) and \(4) it is sufficient to show that the $p_\l$ span. We may define a partial order on the bipartite partitions of $(a,b)$ by saying that $\mu$ covers $\lambda$ if $\lambda$ can be obtained from $\mu$ by replacing two parts of $\mu$ by their sum. Thus $(2,0)(1,3)<(1,0)(1,0)(1,0)(0,3)$ since $(2,0)=(1,0)+(1,0)$ and $(1,3)=(1,0)+(0,3)$. It is easy to see that $$p_{\mu}=\sum_{\lambda\le \mu}c_\l m_\l$$ for some integers $c_\l$, with $c_\mu\ne0$. Thus, for example, $$\eqalign{ p_{(1,1)(1,1)}&=\Bigl(\sum_i x_i y_i \Bigr) \Bigl(\sum_j x_j y_j \Bigr)\cr &=\sum_{i\ne j}x_i y_i x_j y_j +\sum_i x_i^2y_i^2\cr &=2m_{(1,1)(1,1)}+m_{(2,2)}\cr }$$ It follows that these equations can be solved to express the $m_\l$ as linear combinations of the $p_\l$, and thus the $p_\l$ form a basis. If every part of $\l$ is of the form $(a_i,0)$, then all of these MacMahon symmetric functions reduce to the corresponding ordinary symmetric functions. Now let $\bar x_1,\bar x_2,\dots, \bar y_1,\bar y_2,\dots$ be new variables. If $f$ is a MacMahon symmetric function let us write $f(x,y)$ for $f$ and $f(\bar x, \bar y)$ for $f$ with $\bar x_i$ replacing $x_i$ and $\bar y_i$ replacing $y_i$. Suppose that $\l$ has $r_{ij}$ parts equal to $(i,j)$ for each $i$ and $j$. Then set $$z_\l=\prod_{i,j} r_{ij}!\left( i!\, j!\over (i+j-1)!\right)^{r_{ij}}.$$ Note that unlike the case of ordinary symmetric functions, the $z_\l$ are not in general integers; for example, $z_{(2,2)}=2/3$. The following formulas are proved similarly to their analogs for ordinary symmetric functions: $$\eqalignno{ \prod_{i,j}{1\over 1-x_i\bar x_j -y_i\bar y_j}&=\sum_\l h_\l(x,y) m_\l(\bar x,\bar y) &(5)\cr &=\sum_\l z_\l^{-1} p_\l(x,y) p_\l(\bar x,\bar y)&(6)\cr }$$ \pc MAC|\pc MAHON| [\ref{macbook}, Vol. 2, pp. 286--291] proved the following ``law of symmetry'': The coefficient of $x_1^{a_1} y_1^{b_1} x_2^{a_2} y_2^{b_2}\cdots$ in $h_{(c_1,d_1)(c_2,d_2)\cdots}$ is equal to the coefficient of $x_1^{c_1} y_1^{d_1} x_2^{c_2} y_2^{d_2}\cdots$ in $h_{(a_1,b_1)(a_2,b_2)\cdots}$ . MacMahon's law of symmetry follows easily from \(5). Just as in the case of ordinary symmetric functions, we may define a scalar product on MacMahon symmetric functions by $\=\delta_{\l\m}$. Equivalently, for any symmetric function $f$, $\$ is the coefficient of $x_1^{a_1}y_1^{b_1} x_2^{a_2}y_2^{b_2}\cdots$ in $f$. MacMahon's law of symmetry is then equivalent to the formula $\=\$, which implies that $\<\ ,\ \>$ is symmetric. It follows from \(6) by a standard linear algebra argument that $\=z_\l\delta_{\l\m}$. In the author's opinion MacMahon's work on symmetric functions failed to achieve what it might have because of his ignorance of the scalar product, which is understandable, since linear algebra was not well-known in MacMahon's day. Instead of the scalar product, MacMahon used what he called ``Hammond operators,'' which can be used for the same purposes. Hammond operators, as explained elegantly and concisely by \pd MACDONALD [\ref{mac}, p. 45], are adjoints of multiplication operators: if $f$ is a symmetric function then the Hammond operator $\theta_f$ is defined by $$\<\theta_f(g),h\>=\$$ for all symmetric functions $g$ and $h$. Thus in particular, $\=\=\<1,\theta_f(g)\>$, so if $f$ and $g$ are homogeneous of the same degree, $\=\theta_f(g)$. But Hammond operators are undesirable for two reasons. First they disguise the symmetry of the scalar product. Second, they can be represented as differential operators. Although this might seem like an advantage, it seems to be of little use, but misleads by directing attention in the wrong direction. \section D-finiteness and P-recursiveness| The theory of D-finiteness for symmetric functions generalizes easily to MacMahon symmetric functions. We call a MacMahon symmetric function D-finite if it is D-finite in the $p_{(a,b)}$. For example, $$\prod_{i\ne j}(1+x_iy_j)$$ is D-finite because it is equal to $$\exp\biggl(\sum_{j=1}^\infty {(-1)^{j-1}\over j} (p_{(j,0)}p_{(0,j)}-p_{(j,j)})\biggr).$$ It follows that for fixed $k$, the number of $n\times n$ 0-1 matrices with zeros on the diagonal and every row and column sum $k$ is P-recursive as as a function of $n$. By using MacMahon symmetric functions in $k$ sets of variables, one can show that for fixed $k$, the number of $k\times n$ Latin rectangles is P-recursive as a function of $n$. In \pd GESSEL \[latin] a combinatorial derivation is given of a formula for $k\times n$ Latin rectangles which implies P-recursiveness. This formula can also be obtained from MacMahon symmetric functions. \section Explicit formulas| We now give two simple examples of the use of MacMahon symmetric functions to derive explicit formulas. First we find the number of $2\times n$ Latin rectangles. This number is easily seen to be the coefficient of $x_1\cdots x_n y_1\cdots y_n$ in $\left(\sum_{i\ne j}x_i y_j\right)^n=e_{(1,1)}^n$. Thus the desired number is $\bigl\langle h_{(1,1)}^n,e_{(1,1)}^n\bigr\rangle$. We have $$ h_{(1,1)}=p_{(1,0)(0,1)}+p_{(1,1)}\qquad{\rm and}\qquad e_{(1,1)}=p_{(1,0)(0,1)}-p_{(1,1)}. $$ Therefore, the number of $2\times n$ Latin rectangles is $$\eqalignno{ \bigl\langle h_{(1,1)}^n,e_{(1,1)}^n\bigr\rangle &=\bigl\langle(p_{(1,0)(0,1)}+p_{(1,1)})^n, (p_{(1,0)(0,1)}-p_{(1,1)})^n\bigr\rangle\cr &=\biggl\langle\sum_{i=0}^n{n\choose i} p_{(1,0)}^i p_{(0,1)}^i p_{(1,1)}^{n-i},\cr &\qquad\qquad\sum_{j=0}^n{n\choose j} p_{(1,0)}^j p_{(0,1)}^j (-1)^{n-j} p_{(1,1)}^{n-j}\biggr\rangle\cr &=\sum_{i=0}^n {n\choose i}^2 (-1)^{n-i} \bigl\langle p_{(1,0)}^i p_{(0,1)}^i p_{(1,1)}^{n-i}, p_{(1,0)}^i p_{(0,1)}^i p_{(1,1)}^{n-i}\bigr\rangle\cr &=\sum_{i=0}^n {n\choose i}^2 (-1)^{n-i} i!\, i!\, (n-i)!\cr &=n!\sum_{i=0}^n (-1)^{n-i}{n!\over (n-i)!}=n!\,D_n,\cr }$$ where $D_n$ is the $n$th derangement number. Next we consider Example 3 of Section 7, which involves the coefficient of $x_1^{u_1}\dots x_n^{u_n} y_1^{v_1}\dots y_n^{v_n}$ in $$(1-x_1-\cdots x_n-y_1-\cdots - y_n+x_1y_1+\cdots +x_ny_n)^{-1}.$$ This coefficient is then $\$, where $$\eqalign{ f&=\bigl(1-p_{(1,0)}-p_{(0,1)}+p_{(1,1)}\bigr)^{-1}\cr &=\sum_{i,j,k}(-1)^i p_{(1,1)^i (1,0)^j(0,1)^k} {(i+j+k)!\over i!\,j!\, k!}\cr }$$ It follows that if $\l=(1,1)^i(1,0)^j(0,1)^k$ then $$\=(-1)^i (i+j+k)!\eqno(7)$$ and $\=0$ for $\l$ not of this form. Now let $\theta$ be the homomorphism from the MacMahon symmetric functions to polynomials in $z$ defined by $$\theta(p_{(1,1)})=-z,\quad\theta(p_{(1,0)})=\theta(p_{(0,1)})=z,$$ and $\theta(p_{(a,b)})=0$ for other $(a,b)$. Let $L$ be the linear functional on polyomials in $z$ defined by $L(z^n)=n!$, so that $L$ has the integral representation $$L\bigl(r(z)\bigr)=\int_0^\infty\! e^{-z}r(z)\,dz.$$ It follows from \(7) that for any symmetric function $g$, $$\=L\bigl(\theta(g)\bigr).$$ % Now let $$r_{u,v}(z)=\theta(h_{(u,v)})=\sum_{i=0}^{\min{\{u,v\}}}(-1)^i {z^{u+v-i}\over i!\, (u-i)!\, (v-i)!}.$$ Then the coefficient we want is $$L\biggl(\prod_{j=1}^n r_{u_j,v_j}(z)\biggr).\eqno(L1)$$ We note that this result can also be obtained by an argument like that used in the theory of rook polynomials. For the special case $u_i=v_i=1$ we obtain $$\=L\bigl((z^2-z)^n\bigr)=\sum_{i=0}^n(-1)^i {n\choose i}(2n-i)!,$$ as is well-known. (See, for example, \pd STANLEY [\ref{stanbook}, Exercise 10, p. 89; Solution, p. 93].) \vskip 44pt \goodbreak \eightpoint \centerline{REFERENCES} \vskip 10pt \def\\#1|{\ref{#1}|} \expandafter\livre \\c-f|\pd CARTIER (P.) and \pd FOATA (D.)|Probl\`emes combinatoire de commutation et r\'earrangements|Springer-Verlag, $\oldstyle1969$ ({\it Lecture Notes in Math.\/}, {\bf 85})| \expandafter\article \\e&s|\pd EVERETT (C.J.) and \pd STEIN (P.R.)|The asymptotic number of integer stochastic matrices|Discrete Math.|1|1971|55--72| \expandafter\article \\gessel|\pd GESSEL (I.M.)|Two theorems on rational power series|Utilitas Math.|19|1981|247--254| \expandafter\article\\latin|\pd GESSEL (I.M.)|Counting Latin rectangles|Bull. Amer. Math. Soc.|16|1987|79--82| \expandafter\livre \\gjbook|\pd GOULDEN (I.P.) and \pd JACKSON (D.M.)|Combinatorial Enumeration|Wiley, $\oldstyle1983$| \expandafter\article \\goul2|\pd GOULDEN (I.P.) and \pd JACKSON (D.M.)|Labelled graphs with small vertex degrees and P-recursiveness|SIAM J. Alg. Disc. Meth.|7|1986|60--66| \expandafter\article \\goul1|\pd GOULDEN (I.P.), \pd JACKSON (D.M.), and \pd REILLY (J. W.)|The Hammond series of a symmetric function and its application to P-recursiveness|SIAM J. Alg. Disc. Meth.|4|1983|179--193| \expandafter\divers \\hall|\pd HALL (P.)|The algebra of partitions, {\sl Proc. 4th Canadian Math. Cong.} [Banff. $\oldstyle1957$], p.~147--159\pointir $\oldstyle1959$| \expandafter\divers \\lip|\pd LIPSHITZ (L.)|The diagonal of a D-finite power series is D-finite, {\sl J. Algebra}, to be published| \expandafter\divers \\lip2|\pd LIPSHITZ (L.)|D-finite power series, preprint| \expandafter\article \\little|\pd LITTLEWOOD (D.E.)|The Kronecker product of symmetric group representations|J. London Math. Soc.|31|1956|89--93| \expandafter\livre \\mac|\pd MACDONALD (I.G.)|Symmetric Functions and Hall Polynomials|Oxford University Press, $\oldstyle1979$| \expandafter\article \\macm2|{\pc MAC|\pc MAHON|} (P.A.)|Combinatory Analysis. The foundations of a new theory|Phil. Trans.|194|1900|361--386| \expandafter\livre \\macbook|{\pc MAC|\pc MAHON|} (P.A.)|Combinatory Analysis|Chelsea, $\oldstyle1960$. (Originally published by Cambridge University Press, $\oldstyle1915, 1916$)| \expandafter\article\\read0|\pd READ (R.C.)|The enumeration of locally restricted graphs (I)|J. London Math. Soc.|34|1959|417--436| \expandafter\article\\read1|\pd READ (R.C.)|The enumeration of locally restricted graphs (II)|J. London Math. Soc.|35|1960|334--351| \expandafter\article \\read3|\pd READ (R.C.)|The use of S-functions in combinatorial analysis|Canad. J. Math.|20|1968|808--841| \expandafter\article \\read2|\pd READ (R.C.) and \pd WORMALD (N.C.)|Number of labelled 4-regular graphs|J. Graph Theory|4|1980|203--212| \expandafter\article \\redfield|\pd REDFIELD (J.H.)|The theory of group reduced distributions|American J. Math.|49|1927|433--455| \expandafter\article \\stan|\pd STANLEY (R.P.)|Differentiably finite power series|European J. Combin.|1|1980|175--188| \expandafter\livre \\stanbook|\pd STANLEY (R.P.)|Enumerative Combinatorics, Volume I|Wadsworth, $\oldstyle1986$| \expandafter\article\\zeil|\pd ZEILBERGER (D.)|Sister Celine's technique and its generalizations|J. Math. Anal. Appl.|85|1982|114--145| \par \tenpoint \adresse Ira M. {\petcap Gessel} Department of Mathematics Brandeis University Waltham, MA 02254 USA \fin \end