%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<i_n} x_{i_1} x_{i_2}\cdots x_{i_n}.$$
If $\l=\l_1\l_2\cdots\l_k$ is a partition, we define
$e_\l=e_{\l_1}e_{\l_2}\cdots e_{\l_k}$.


The {\it complete} symmetric function $h_n$ is defined by
$$h_n=\sum_{i_1\le i_2\le\cdots\le i_n} x_{i_1} x_{i_2}\cdots x_{i_n}.$$ It is
convenient to define $h_\l$ to be $h_{\l_1}h_{\l_2}\cdots h_{\l_k}$
for any sequence $\l=\l_1\l_2\cdots\l_k$ of nonnegative integers, not
necessarily a partition. We set $h=\suminf n h_n$ and $e=\suminf n
e_n$, where $h_0=e_0=1$.
 
The {\it monomial} symmetric function $m_\l$ is the sum of all
distinct monomials of the form $x_{i_1}^{\l_1}\cdots x_{i_k}^{\l_k}$,
where $i_1,\ldots, i_k$ are distinct.



It is known that each of the sets $\{e_\l\}$, $\{h_\l\}$, $\{p_\l\}$,
and $\{m_\l\}$, where $\l$ ranges over all partitions of $n$,
is a basis for the vector space of symmetric functions  homogeneous of
degree $n$.

If $\l$ has $r_i$ parts equal to $i$ for each $i$, then we define
$z_\l$ to be $1^{r_1}2^{r_2}\cdots k^{r_k}\,r_1!\,r_2!\cdots r_k!\,$.

There is a symmetric scalar product $\langle\,\ ,\ \rangle$ defined
on symmetric functions that has the following properties:
$$\langle m_\l,h_\m\rangle=\d_{\l\m}\eqno(1)$$
and
$$\langle p_\l,p_\m\rangle=z_\l\d_{\l\m}\eqno(2)$$    
where $\d_{\l\m}$ is 1 if $\l=\m$ and 0 otherwise.  
  
This scalar product was introduced by \pd REDFIELD \[redfield] in 1927
in his then-ignored but now-famous paper on what later became known as
P\'olya theory. Redfield called it the ``cap product.''  The scalar
product was rediscovered by \pd HALL \[hall] in 1957 and is often
attributed to him.  It is equivalent to the usual scalar product
on characters of symmetric groups.

Note that \(1) implies that if $f$
is a symmetric function, then the coefficient of
$x_{i_1}^{\l_1}x_{i_2}^{\l_2}${}$\cdots ${}$x_{i_k}^{\l_k}$ in $f$ is
$\langle f, h_\l\rangle$.  
To evaluate scalar products of symmetric functions,
we  shall express them in terms of power sum symmetric functions and
use \(2).  Thus, we need to express the complete
homogeneous symmetric functions in terms of
power sum symmetric functions, and this is accomplished by the
formula
$$\sum_{n=0}^\infty
h_n=\exp\biggl(\sum_{k=1}^\infty{p_k\over k}\biggr), \eqno(3)$$ 
which implies that 
$$h_n=\sum_\l {p_\l\over z_\l}$$
where the sum is over all partitions $\l$ of $n$.


Next we recall the operation of {\it internal} (also called {\it
inner}) product on symmetric functions which is defined by
$${p_\l}*{p_\m}= \d_{\l\m}z_\l p_\l  \eqno(10)$$
and extended by linearity to all symmetric functions. The internal
product was  discovered by \pd REDFIELD \[redfield] in 1927, who
called it the ``cup product,'' and it was rediscovered by 
\pd LITTLEWOOD \[little] in 1956. It is equivalent to pointwise
multiplication of characters of symmetric groups, which corresponds to
the tensor (or Kronecker) product of representations.


\section D-finite symmetric functions|
We shall say that a symmetric function is D-finite if it is D-finite
when considered as a power series in the $p_n$. We shall show that
functions obtained from coefficients of D-finite symmetric functions
are P-recursive.

\th Theorem 3|Suppose that $f$ and $g$ are symmetric functions which are
D-finite in the $p_i$ and possibly in some other variables.
Then $f*g$ is D-finite in these variables.\finth

\proof  Note that $f*g=f\odot g \odot u$, where $\odot$ is the
Hadamard product in the $p_i$ and $u$ is the symmetric function given by
$$u=\sum_\l z_\l p_\l,$$
where the sum is over all partitions $\l$.
Now
$$\eqalign{
u&=\sum_{r_1,r_2,\ldots}1^{r_1}2^{r_2}\cdots r_1!\,r_2!\cdots
p_1^{r_1}p_2^{r_2}\cdots
\cr
&=\left(\sum_{r_1}r_1!\,(1p_1)^{r_1}\right)
\left(\sum_{r_2}r_2!\,(2p_2)^{r_2}\right)\cdots\cr
&=A(1p_1)A(2p_2)\cdots,\cr}$$
where $A(y)=\suminf n n!\,y^n$.
Since $u$ is easily seen to be D-finite, $f*g$ is a Hadamard product of three
D-finite power series, and is thus D-finite by Lipshitz's theorem.


\th Corollary 4|Let $f$ and $g$ be symmetric
functions which are  D-finite in the $p_i$ and in another variable $t$,
and suppose that $g$ involves only finitely many of the $p_i$. Then
$\langle f,g\rangle $ is D-finite in $t$ as long as it is well-defined
as a formal power series.\finth

\proof By the previous theorem, $f*g$ is D-finite in the $p_i$ and in
$t$, and involves only finitely many of the $p_i$. 
Then $\langle
f,g\rangle$ is obtained from $f*g$ by setting each  $p_i$ equal to 1,
and thus the conclusion follows from Lemma 1(iii).

Note that without the restriction on $g$ the theorem would not be
true: according to our definitions, $\suminf n c_np_n$ is D-finite
for any coefficients $c_n$ and thus any power series in $t$ can be
obtained as a scalar product of two D-finite symmetric functions.

\th Corollary 5|
Let $f$ be a D-finite symmetric function and let $S$ be a
finite set of integers.  Define integers $b_n$ as follows: $b_n$ is
the sum over all $n$-tuples $(\l_1,\l_2, \ldots,  \l_n)\in S^n$ of the coefficient of
$x_1^{\l_1}\cdots x_n^{\l_n}$
in $f$. Then $b(t)=\suminf n b_nt^n$ is
D-finite.\finth

\proof  The coefficient of $x_1^{\l_1}\cdots x_n^{\l_n}$ in $f$ is
$\langle f, h_\l\rangle$, and so  
$b(t)=\langle f, g\rangle$,
where  
$$ g=\suminf n\left(t\sum_{i\in S}h_i\right)^n
=\left(1-t\sum_{i\in S}h_i\right)^{-1}$$ 
and the assertion follows from the previous corollary.

In particular, it will follow that the generating functions for
various types of graphs and hypergraphs on $n$ vertices whose degrees
are constrained to a finite set are D-finite. This proves a conjecture
of \pd GOULDEN and \pd JACKSON \[goul2].

Next we need to consider the operation of {\it composition} (also
called {\it plethysm}) for symmetric functions. First, suppose that
$g$ is a symmetric function which can can be expressed in the form
$t_1+t_2+\cdots\,$, where each $t_i$ is of the form
$x_1^{i_1}x_2^{i_2}\cdots x_k^{i_k}$. (The terms $t_i$ need not be distinct.)
Then for any symmetric function $f=f(x_1,x_2,\ldots\,)$ the
composition $f(g)$ is defined to be $f(t_1,t_2,\ldots\,)$. 

In the general case, composition  may be defined
as follows: If $f_1$ and
$f_2$ are symmetric functions then $(f_1+f_2)(g)=f_1(g)+f_2(g)$ and
$(f_1f_2)(g)=f_1(g)f_2(g)$ so it is sufficient to define $p_n(g)$.
This is accomplished by the formula $p_n(g)=g(p_n)$, where
$g(p_n)$ is determined by the special case given in the previous  paragraph,
or by the formula $p_m(p_n)=p_{mn}$.

\th Theorem 6|Suppose that $g$ is a polynomial in the $p_n$.
Then $h(g)$ is D-finite. \finth
           
\proof 
To show that $h(g)$ is D-finite we need only show that $h(g)$ is
D-finite in the variables  $p_1$, $p_2$, \dots, $p_n$  for each $n$.

By \(3) we have 
$$\eqalign{h(g)&=\exp\biggl(\sum_{k=1}^\infty{p_k(g)\over k}\biggr)
=\exp\biggl(\sum_{k=1}^\infty{g(p_k)\over k}\biggr)\cr
&=\exp\biggl(\sum_{k=1}^n{g(p_k)\over
k}\biggr)\exp\biggl(\sum_{k=n+1}^\infty{g(p_k)\over k}\biggr),\cr}$$
where the second factor on the right does not involve $p_1$,
$p_2$, \dots, $p_n$.  Then by Lemma 1(iv),  $h(g)$ is D-finite in
$p_1$, $p_2$, \dots, $p_n$.

The same reasoning shows that 
$e(g)$ is also D-finite, where $e=\suminf n e_n$.

Let us now give some examples of Theorem 6. Consider the products
%
$$\eqalignno{
h(h_2)&=\prod_{i\le j} {1\over 1-x_ix_j}&(6)\cr
h(e_2)&=\prod_{i< j} {1\over 1-x_ix_j}&(7)\cr
e(h_2)&=\prod_{i\le j} (1+x_ix_j)&(8)\cr
e(e_2)&=\prod_{i< j}  (1+x_ix_j).&(9)\cr}$$

By Theorem 6, they are all D-finite. Each counts a class of
graphs.  Thus the coefficient of $x_1^{\l_1}x_2^{\l_2}\cdots$ in \(6)
is the number of graphs on the vertex set $\{1,2,\ldots\}$, with
multiple edges and loops allowed, such that the degree of vertex $i$
is $\l_i$, where a loop contributes 2 to the degree of its vertex.
Similarly, \(7) counts graphs with multiple edges but no loops, \(8)
counts graphs with loops allowed, but not multiple edges, and \(9)
counts graphs without loops or multiple edges. Graphs with loops in
which a loop contributes only 1 to the degree of its vertex are
counted by $h(e_1+e_2)$ (multiple edges allowed) and $e(e_1+e_2)$
(multiple edges not allowed).  Similarly, $k$-uniform hypergraphs are
counted by $e(e_k)$, and so on.



\section Symmetric functions in several sets of variables|
In some applications it is necessary to work with symmetric functions
in two or more sets of variables. For simplicity, we consider here only
the case of two sets of variables,  which we use to count
nonnegative integer matrices with prescribed row and column sums (or
equivalently, digraphs with prescribed indegrees and outdegrees  or
two-colored graphs with prescribed degrees).


Let $x_1$, $x_2$, \dots and $y_1$, $y_2$, \dots be two disjoint sets of
variables. We shall consider power series in these variables which
are symmetric in the  $x$'s and symmetric in the $y$'s. It is easy to
see that such a symmetric function can be expressed in the form
$$\sum_{\l,\,\m}a_{\l\m}p_\l(x)p_\m(y)$$
where $p_\l(x)$ means $p_\l(x_1,x_2,\ldots)$ and similarly for
$p_\m(y)$. We call these series D-finite if they are D-finite in the
$p_i(x)$ and $p_j(y)$.


We may extend the scalar product $\langle\,\ ,\ \rangle$ to symmetric
functions in two sets of variables by setting 
$$\langle
f_1(x)f_2(y),g_1(x)g_2(y)\rangle=\langle f_1(x),g_1(x)\rangle\langle
f_2(y),g_2(y)\rangle.$$
If $f$ is a symmetric function, by $f(xy)$ we mean
$f(x_1y_1,x_1y_2,\ldots,x_iy_j,\ldots\,)$. Thus, for example, we have
$$h(xy)=\prod_{i,j}{1\over 1-x_iy_j}.$$ This product is easily seen
to be D-finite using the fact that $p_n(xy)=p_n(x)p_n(y)$. It is 
clear that the coefficient of $x_1^{\l_1}\cdots x_n^{\l_n}
y_1^{\m_1}\cdots y_n^{\m_n}$ in $h(xy)$ is the number of digraphs on
$\{1, 2,\cdots, n\}$, with multiple edges allowed,
in which vertex $i$ has outdegree $\l_i$ and
indegree $\m_i$, or equivalently, the
number of $n\times n$ matrices of nonnegative integers in which the
sum of the $i$th row is $\l_i$ and the sum of the $j$th column is
$\m_j$.  This coefficient is easily seen to be  equal to $\langle
h(xy), h_\l(x)h_\m(y)\rangle$, which is also equal to $\<h_\l(x), h_\m(x)\>$.



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 $\<h_k^n,h_k^n\>$, 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_{i<j}
x_i y_i x_j y_j.\cr }$$ 
Note that $m_{(1,1)(1,1)}$ is not equal to
$\sum_{i\ne j}x_iy_i x_jy_j$ since the latter sum contains every
monomial twice.  It is clear that the  $m_\l$ over all bipartite
partitions $\l$ of $(a,b)$ constitute a basis for the
vector space of all MacMahon symmetric functions of degree $(a,b)$.

Next we define the three ``multiplicative bases'': the {\it elementary\/} 
symmetric functions $e_\l$, the {\it complete\/} symmetric functions $h_\l$,
and the {\it power sum\/} symmetric functions $p_{\l}$. These bases are
multiplicative in the sense that if $\l=(a_1,b_1)(a_2,b_2)\cdots$ then
$e_\l=e_{(a_1,b_1)}e_{(a_2,b_2)}\cdots$ and similarly for the other
bases.  We define $e_{(a,b)}$ by 
$$1+\sum_{a,\,b}e_{(a,b)}
s^at^b=\prod_{i}(1+x_is+y_it),$$ 
so that
$e_{(a,b)}=m_{(1,0)^a(0,1)^b}$, and  we define $h_{(a,b)}$ by
$$1+\sum_{a,\,b}h_{(a,b)} s^at^b=\prod_{i}{1\over 1-x_is-y_it }.$$ Note
that in general $h_{(a,b)}$ is not a sum of $m_\l$'s with unit
coefficients. For example,
$$h_{(1,1)}=x_1y_1+y_1x_1+x_1y_2+y_1x_2+\cdots=2m_{(1,1)}+m_{(1,0)(0,1)}.$$
We define $p_{(a,b)}$ by $$p_{(a,b)}=\sum_{i}x_i^a y_i^b=m_{(a,b)}.$$
By taking logarithms and exponentiating we obtain
$$1+\sum_{a,b}e_{(a,b)}
s^at^b=\exp\biggl(\sum_{k+l>0}(-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
$\<h_\l, m_\m\>=\delta_{\l\m}$. Equivalently, for any symmetric
function $f$, $\<h_\l, 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 $\<h_\l,h_\m\>=\<h_\m,h_\l\>$, which implies
that $\<\ ,\ \>$ is symmetric.
It follows from \(6) by a standard linear algebra argument that
$\<p_\l, p_\m\>=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\>=\<g,fh\>$$ 
for all symmetric functions $g$ and $h$. Thus in particular,
$\<f,g\>=\<f\cdot1,g\>=\<1,\theta_f(g)\>$, so if $f$ and $g$ are
homogeneous of the same degree, $\<f,g\>=\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
$\<h_{(u_1,v_1)(u_2,v_2)\cdots},f\>$, 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
$$\<p_\l, f\>=(-1)^i (i+j+k)!\eqno(7)$$
and $\<p_\l,f\>=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$,
$$\<g,f\>=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
$$\<h_{(1,1)}^n,f\>=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




