
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


                    \magnification=1200 
                    \overfullrule=0pt 
                    


%%%%%%%%%%%%%%%
%\catcode`@=11


%---> FOURTEENPOINT
%\newfam\gothfam
%\newfam\gothbfam
%\newfam\bbfam
%\newskip\ttglue
%\def\twelvepoint{\def\rm{\fam0\twelverm}%
%\textfont0=\fourteenrm    \scriptfont0=\twelverm    \scriptscriptfont0=\ninerm
%\textfont1=\fourteeni    \scriptfont1=\twelvei    \scriptscriptfont1=\ninei
%\textfont2=\fourteensy    \scriptfont2=\twelvesy    \scriptscriptfont2=\ninesy
%\textfont3=\tenex    \scriptfont3=\tenex    \scriptscriptfont3=\tenex
%\textfont\itfam=\fourteenit    \def\it{\fam\itfam\fourteenit}%
%\textfont\slfam=\fourteensl    \def\sl{\fam\slfam\fourteensl}%
%\textfont\ttfam=\fourteentt    \def\tt{\fam\ttfam\fourteentt}%
%\textfont\bffam=\fourteenbf    \scriptfont\bffam=\twelvebf    \scriptscriptfont\bffam=\ninebf
%    \def\bf{\fam\bffam\fourteenbf}%
%\textfont\gothfam=\fourteeneufm    \scriptfont\gothfam=\twelveeufm    \scriptscriptfont\gothfam=\nineeufm
%    \def\goth{\fam\gothfam\fourteeneufm}%
%\textfont\gothbfam=\fourteeneufb    \scriptfont\gothbfam=\twelveeufb    \scriptscriptfont\gothbfam=\nineeufb
%    \def\gthb{\fam\gothbfam\fourteeneufb}%
%\textfont\bbfam=\fourteenbb    \scriptfont\bbfam=\twelvebb    \scriptscriptfont\bbfam=\ninebb
%    \def\bb{\fam\bbfam\fourteenbb}%
%\tt\ttglue=0.8em plus .5em minus .3em
%\normalbaselineskip=18pt
%\setbox\strutbox=\hbox{\vrule height15pt depth6pt width0pt}%
%\font\sc=cmcsc10 scaled\magstep2
%\normalbaselines\rm}%\fourteenpoint
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% MACRO

% \font\eighttt=cmtt8             
% \font\eightsl=cmsl8             
% \font\eightex=cmex10 at 8pt

%%%%%%%%%%%%%%%%
%%  FONT CMR  %%
%%%%%%%%%%%%%%%%

% \font\fiverm=cmr5
% \font\sixrm=cmr6
\font\seventeenrm=cmr17
\font\fourteenrm=cmr12 at 14pt
\font\twelverm=cmr12
\font\ninerm=cmr10 at 9pt
\font\eightrm=cmr8
\font\sixrm=cmr10 at 6pt
%
\textfont0=\tenrm
\scriptfont0=\sevenrm
\scriptscriptfont0=\fiverm
\def\rm{\fam0\tenrm}


%%%%%%%%%%%%%%%%
%%  FONT CMM  %%
%%%%%%%%%%%%%%%%
%
% \font\sixi=cmmi6
% \font\eighti=cmmi8
% \font\ninei=cmmi9
% \font\twelvei=cmmi12
% \font\fourteeni=cmmi10 at 14pt
%
\font\teni=cmmi10
\font\seveni=cmmi7
\font\fivei=cmmi5
\textfont1=\teni
\scriptfont1=\seveni
\scriptscriptfont1=\fivei
\def\mit{\fam1}
\def\oldstyle{\fam1\teni}

%%%%%%%%%%%%%%%%%
%%  FONT CMSY  %%
%%%%%%%%%%%%%%%%%
%
\font\fivesy=cmsy6 at 5pt
\font\sixsy=cmsy6
\font\sevensy=cmsy7
\font\eightsy=cmsy8
\font\ninesy=cmsy9
\font\tensy=cmsy10
\font\twelvesy=cmsy10 at 12pt
\font\fourteensy=cmsy10 at 14pt

%%%%%%%%%%%%%%%%%
%%  FONT CMTI  %%
%%%%%%%%%%%%%%%%%
%
\font\nineit=cmti10 at 9pt
\font\eightit=cmti8 
\font\sevenit=cmti7

%%%%%%%%%%%%%%%%%%%
%%  FONT CMBFTI  %%
%%%%%%%%%%%%%%%%%%%
%
\font\eightbfti=cmbxti10 at 8pt
\font\bfti=cmbxti10
\font\twelvebfti=cmbxti10 at 12pt
\font\fourteenbfti=cmbxti10 at 14pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  FONT CMCSC (Petites capitales) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\font\sc=cmcsc10

%%%%%%%%%%%%%%%%%
%%  FONT MSBM  %%
%%%%%%%%%%%%%%%%%

\font\sixbboard=msbm7 at 6pt

% \font\ninebb=msbm9  % msbm10 at 9pt
% \font\eightbb=msbm8 % msbm10 at 8pt
% \font\sixbb=msbm6   % msbm10 at 6pt
% \font\sixbboard=msbm7 at 6pt
%
\font\tenbb=msbm10
\font\sevenbb=msbm7
\font\fivebb=msbm5
\newfam\bbfam
\textfont\bbfam=\tenbb
\scriptfont\bbfam=\sevenbb
\scriptscriptfont\bbfam=\fivebb
\def\bb{\fam\bbfam\tenbb}
\let\oldbb=\bb
\def\bb #1{{\oldbb #1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  FONT EUFM  (Gothique)  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\font\sixgoth=eufm5 at 6pt  
\font\eightgoth=eufm7 at 8pt
%
\font\tengoth=eufm10
\font\sevengoth=eufm7
\font\fivegoth=eufm5
\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}
%

%%%%%%%%%%%%%%%%%
%%  FONT CMBX  %%
%%%%%%%%%%%%%%%%%
%              
% \font\eightbf=cmbx10 at 8pt
\font\twelvebf=cmbx12
\font\fourteenbf=cmbx10 at 14pt
%

\font\ninebf=cmbx9
\font\eightbf=cmbx8
% \font\sevenbf=cmbx10 at 7pt
\font\sixbf=cmbx5 at 6pt 
% \font\sixbf=cmbx5
% \font\fivebf=cmbx10 at 5pt

\font\tenbf=cmbx10
\font\sevenbf=cmbx7
\font\fivebf=cmbx5
\newfam\bffam
\textfont\bffam=\tenbf
\scriptfont\bffam=\sevenbf
\scriptscriptfont\bffam=\fivebf
\def\bf{\fam\bffam\tenbf}
%
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  HAUT-DE-PAGE (EX. : AUTEUR COURANT ET TITRE COURANT)  %%
%%  BAS-DE-BAGE                                           %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newif\ifpagetitre           \pagetitretrue
\newtoks\hautpagetitre       \hautpagetitre={\hfil}
\newtoks\baspagetitre        \baspagetitre={\hfil}

\newtoks\auteurcourant       \auteurcourant={\hfil}
\newtoks\titrecourant        \titrecourant={\hfil}

\newtoks\hautpagegauche
         \hautpagegauche={\hfil\the\auteurcourant\hfil}
\newtoks\hautpagedroite
         \hautpagedroite={\hfil\the\titrecourant\hfil}

\newtoks\baspagegauche
         \baspagegauche={\hfil\tenrm\folio\hfil}
\newtoks\baspagedroite
         \baspagedroite={\hfil\tenrm\folio\hfil}

\headline={\ifpagetitre\the\hautpagetitre
\else\ifodd\pageno\the\hautpagedroite
\else\the\hautpagegauche\fi\fi }

\footline={\ifpagetitre\the\baspagetitre
\global\pagetitrefalse
\else\ifodd\pageno\the\baspagedroite
\else\the\baspagegauche\fi\fi }

\def\nopagenumbers{\def\folio{\hfil}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


           %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
           %%  UN SEMBLANT DES GUILLEMETS FRANCAIS  %%
           %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\og{\leavevmode\raise.3ex
     \hbox{$\scriptscriptstyle\langle\!\langle$~}}
\def\fg{\leavevmode\raise.3ex
     \hbox{~$\!\scriptscriptstyle\,\rangle\!\rangle$}}
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      %%  TRUC AVEC MACHIN AU-DESSUS ET BIDULE AU-DESSOUS %%
      %%                (MODE MATHEMATIQUE)               %%
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\build #1_#2^#3{\mathrel{\mathop{\kern 0pt #1}
     \limits_{#2}^{#3}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\scs{\scriptstyle}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% FLECHES HORIZONTALES ET VERTICALES AVEC TRUC  %%
         %%   AU-DESSUS ET MACHIN AU-DESSOUS (MODE MATH)  %%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\hfl[#1][#2][#3]#4#5{\kern -#1
 \sumdim=#2 \advance\sumdim by #1 \advance\sumdim by #3
  \smash{\mathop{\hbox to \sumdim {\rightarrowfill}}
   \limits^{\scriptstyle#4}_{\scriptstyle#5}}
    \kern-#3}

\def\vfl[#1][#2][#3]#4#5%
 {\sumdim=#1 \advance\sumdim by #2 \advance\sumdim by #3
  \setbox1=\hbox{$\left\downarrow\vbox to .5\sumdim {}\right.$}
   \setbox1=\hbox{\llap{$\scriptstyle #4$}\box1
    \rlap{$\scriptstyle #5$}}
     \vcenter{\kern -#1\box1\kern -#3}}

\def\Hfl #1#2{\hfl[0mm][12mm][0mm]{#1}{#2}}
\def\Vfl #1#2{\vfl[0mm][12mm][0mm]{#1}{#2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

                   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                   %% DIAGRAMMES COMMUTATIFS  %%
                   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newdimen\sumdim
\def\diagram#1\enddiagram
    {\vcenter{\offinterlineskip
      \def\tvi{\vrule height 10pt depth 10pt width 0pt}
       \halign{&\tvi\kern 5pt\hfil$\displaystyle##$\hfil\kern 5pt
        \crcr #1\crcr}}}

%% SYNTAXE

%%  $$
%%  \diagram
%%   ... & & ... & \cr
%%   ... & & ... & \cr
%%   .................
%%   ... & & ... & \cr
%%  \enddiagram
%%  $$        


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\def\Doteq{\build{=}_{\scriptscriptstyle\bullet}^{\scriptscriptstyle\bullet}}
\def\Doteq{\build{=}_{\hbox{\bf .}}^{\hbox{\bf .}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
               %% ESPACE VERTICAL EN MODE MATH  %%
               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\vspace[#1]{\noalign{\vskip #1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

                      %%%%%%%%%%%%%%%%%%%
                      %%  ENCADREMENT  %%
                      %%%%%%%%%%%%%%%%%%%

\def\boxit [#1]#2{\vbox{\hrule\hbox{\vrule
     \vbox spread #1{\vss\hbox spread #1{\hss #2\hss}\vss}%
      \vrule}\hrule}}

\def\carre{\boxit[5pt]{}} %% INDIQUE LA FIN D'UNE PREUVE

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\catcode`\@=11
\def\Eqalign #1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$
\hfil\crcr #1\crcr}}\,}
\catcode`\@=12

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\font\tengoth=eufm10            \font\tenbboard=msbm10
%\font\eightrm=cmr8              \font\eighti=cmmi8 
%\font\eightsy=cmsy8             \font\eightbf=cmbx8 
% \font\eighttt=cmtt8             \font\eightit=cmti8
% \font\eightsl=cmsl8             \font\eightgoth=eufm7
% \font\eightbboard=msbm7         \font\eightex=cmex10 at 8pt

%\font\eightgoth=eufm7           \font\sevenbboard=msbm7

% \font\sixrm=cmr6                \font\sixi=cmmi6
%\font\sixsy=cmsy6               \font\sixbf=cmbx6
% \font\sixgoth=eufm5 at 6pt      \font\sixbboard=msbm7 at 6pt

%\font\fivegoth=eufm5            \font\fivebboard=msbm5


                    
                    



                    \vsize= 18.5cm 
                    \hsize= 12.5cm 
                    \hoffset=3mm 
                    \voffset=3mm 


                    %%%%%%%%%%%%%%%%% 
                    %% DEFINITIONS %% 
                    %%%%%%%%%%%%%%%%% 


                    \def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt 
                    \vfill\hrule}\vrule}} 

                    \def\qeda{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule 
                    width 4pt height9pt 
                    \vfill\hrule}\vrule}} 


                    \def\arti#1#2{\setbox50=\null\ht50=#1\dp50=#2\box50} 
                    \def\tend_#1^#2{\mathrel{ 
                    \mathop{\kern 0pt\hbox to 1cm{\rightarrowfill}} 
                    \limits_{#1}^{#2}}} 
                    \def\tendps{\tend_{n\to\infty}^{\hbox{p.s.}}} 


                    \def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle 
                    \langle\!\langle$}\thinspace} 
                    \def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle 
                    \rangle\!\rangle$}} 


                    \font\msamten=msam10 
                    \font\msamseven=msam7 
                    \newfam\msamfam 

                    \textfont\msamfam=\msamten 
                    \scriptfont\msamfam=\msamseven 

                    \def\ams {\fam\msamfam\msamten} 

                    \def\hexnumber #1% 
                    {\ifcase #1 0\or 1\or 2\or 3\or 4\or 5 
                    \or 6\or 7\or 8\or 9\or A\or B\or C\or D\or E\or F 
                    \fi} 

                    \mathchardef\leadsto="3\hexnumber\msamfam 20 

                    \def\frac #1#2{{#1\over #2}} 

                    %%%%%%%%%%%%%%%%%%%%%%%% 
                    %% END OF DEFINITIONS %% 
                    %%%%%%%%%%%%%%%%%%%%%%%% 

                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


                    %%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                    %% AUTHOR ON EVEN PAGES %% 
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%% 

                    \auteurcourant{\eightbf BODO LASS \hfill} 

                    %%%%%%%%%%%%%%%%%%%%%%%%%% 
                    %% TITLE ON ODD PAGES %% 
                    %%%%%%%%%%%%%%%%%%%%%%%%%% 

                    \titrecourant{\hfill\eightbf MATCHING POLYNOMIALS AND DUALITY} 


                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

                    {\parindent=0pt\eightbf 
                    COMBINATORICA 24 (3) (2004) 427-440 


                    \vskip 1.5cm 

                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

                    %%%%%%%%%%%%% 
                    %% TITEL %% 
                    %%%%%%%%%%%%% 

                    \centerline{\fourteenbf 
                    MATCHING POLYNOMIALS AND DUALITY 
                    } 
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                    %% Subject Classification %% 
                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                    \parindent=-1mm\footnote{}{ 
                    Mathematics Subject Classification (1991): 05 C 70; 05 A 15, 05 A 20, 12 D 10 
                    } 

                    \vskip 15pt 

                    %%%%%%%%%%% 
                    %% NAME %% 
                    %%%%%%%%%%% 

                    \centerline{\twelvebf BODO LASS} 

                    \vskip 10pt 

                    \medskip 

                    %%%%%%%%%%%%%%%% 
                    %% RECEIVED %% 
                    %%%%%%%%%%%%%%%% 

                    \centerline{(Received February 20, 2001; Accepted November 29, 2001)} 
                    } 

                    \vskip10pt 

                    \vskip3pt 

                    %%%%%%%%%%%%%%%% 
                    %% ABSTRACT %% 
                    %%%%%%%%%%%%%%%% 

                    {\eightrm Let $\scs G$ be a simple graph on $\scs n$ vertices. An $\scs r$-matching in 
                    $\scs G$ is a set of $\scs r$ independent edges. The number of $\scs r$-matchings in $\scs G$ 
                    will be denoted by $\scs p(G,r)$. We set $\scs p(G,0) = 1$ and 
                    define the matching polynomial of $\scs G$ by 
                    $\scs 
                    \mu(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \cdot p(G,r) \cdot x^{n-2r} 
                    $ 
                    and the signless matching polynomial of $\scs G$ by 
                    $\scs 
                    \overline{\mu}(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot x^{n-2r}. 
                    $ 

                    It is classical that the matching polynomials of a graph $\scs G$ determine the matching 
                    polynomials of its complement $\scs \overline{G}$. We make this statement more explicit by 
                    proving new duality theorems by the generating function method for set functions. 
                    In particular, we show that the matching functions $\scs e^{-x^2/2}\mu(G,x)$ and 
                    $\scs e^{-x^2/2}\mu(\overline{G},x)$ are, up to a sign, real Fourier transforms of each other. 

                    Moreover, we generalize Foata's combinatorial proof of the Mehler formula for Hermite polynomials 
                    to matching polynomials. This provides a new short proof of the classical fact that 
                    all zeros of $\scs \mu(G,x)$ are real. The same statement is also proved for a common generalization 
                    of the matching polynomial and the rook polynomial. 
                    } 


                    \vskip1.5pt 
                    \medskip 

                    \parindent=3mm 
                    \vskip 5mm 

                    %%%%%%%%%%%% 
                    %% TEXT %% 
                    %%%%%%%%%%%% 


                    \centerline{\bf 1. Introduction} 

                    \medskip 

                    Let $V$ be a finite set of vertices, $n := |V|$; and let $G = (V,E)$ be a simple graph, 
                    i.e.~$E$, the set of edges, is a subset of ${V \choose 2}$, the family of all 2-element 
                    subsets of $V$. The {\it complement} of $G$ is the graph $\overline{G} = (V, \overline{E})$ 
                    with $\overline{E} = {V \choose 2} \backslash E$. 

                    An {\it $r$-matching} in $G$ is a set of $r$ edges of $G$, no two of which have a vertex in common. 
                    Clearly, $r \le {\lfloor n/2 \rfloor}$. If $r = {\lfloor n/2 \rfloor}$, then an $r$-matching 
                    of $G$ is called {\it perfect} if $n$ is even and {\it quasi-perfect} if $n$ is odd. 
                    Let $p(G,r)$ be the number of $r$-matchings in $G$, with the convention that $p(G,0) := 1.$ 
                    The matching polynomial of $G$ is (see~[3], chapter 1) 
                    $$ 
                    \mu(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \cdot p(G,r) \cdot x^{n-2r}, 
                    $$ 
                    while the signless matching polynomial reads 
                    $$ 
                    \overline{\mu}(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot x^{n-2r}. 
                    $$ 
                    In particular, $\overline{\mu}(G,0)$ counts the number of perfect matchings of $G$ and 
                    $\overline{\mu}(G,1)$ counts the number of arbitrary matchings of $G$. 

                    These polynomials were introduced by Heilmann and Lieb~[5], who, motivated by statistical physics, 
                    mainly studied their zeros. They obtained many estimations on the locations of 
                    those zeros and provided several different proofs for their main theorem that all zeros of 
                    $\mu(G,x)$ are real. Another proof of this theorem was obtained by Godsil, which he reproduced in his 
                    recent book~[3] together with all the classical proofs. However, all those proofs rely on a recursive 
                    approach (via the deletion of a special vertex) towards the matching polynomial. One of the purposes 
                    of this paper is to give a short proof that avoids this traditional deletion technique. 

                    We generalize the combinatorial proof of the Mehler formula for Hermite polynomials 
                    imagined by Foata (see~[2]). To state and derive our extension of the Mehler formula we need an 
                    adequate algebraic tool, the algebra of generating functions for set functions. This algebra is 
                    developed in the next section. In section 4 we show that our generalization of the Mehler formula 
                    immediately implies that $|\mu(G,x)|^2 \; \ge \; [(\Im m \; x)^2]^n + 2|E|\cdot[(\Im m \; x)^2]^{n-1}$ 
                    for every $x \in {\bb C}$, i.e.~that all the zeros of $\mu(G,x)$ are real. Moreover, this fact holds 
                    for a common generalization of the matching polynomial and the rook polynomial. 

                    \medskip 

                    Section 3 is entirely devoted to questions of duality. It is evident that $\mu(G,x)$ and 
                    $\overline{\mu}(G,x)$ contain the same information, a convenient relation between those 
                    polynomials being 
                    $$ 
                    \mu(G,x) = (-i)^n \cdot \overline{\mu}(G,xi), \qquad |V| = n, \quad i = \sqrt{-1}. 
                    $$ 
                    The observation that $\mu(G,x)$ and $\overline{\mu}(G,x)$ determine $\mu(\overline{G},x)$ and 
                    $\overline{\mu}(\overline{G},x)$, however, seems to have first been made by Lov\'asz,~[8]~5.18. 
                    His proof, based on the inclusion-exclusion principle, does not seem to be too difficult although 
                    it is marked with an asterisk in his book. We prefer to give an explicit calculation involving 
                    several new duality theorems. In particular, we show that the matching functions $\scs e^{-x^2/2}\mu(G,x)$ 
                    and $\scs e^{-x^2/2}\mu(\overline{G},x)$ are, up to a sign, real Fourier transforms of each other. 

                    Matching polynomials generalize many classical orthogonal polynomials, namely Hermite polynomials 
                    (the matching polynomials of complete graphs), Tchebycheff polynomials of both kinds (paths and cycles) 
                    and Laguerre polynomials (complete bipartite graphs), see~[9] chapter~6. The complete graph $K_n$ on 
                    $n$ vertices can be defined as the complement of the edgeless graph $\overline{K_n}$ on those vertices. 
                    Clearly, $\mu(\overline{K_n},x) = \overline{\mu}(\overline{K_n},x) = x^n$. The Hermite polynomials will 
                    be (by definition) the matching polynomials of the complete graphs, i.e.~$He_n(x) := \mu(K_n,x)$. The reader 
                    will recognize the classical definition of the Hermite polynomials as a special case of the second equality 
                    in our duality theorem ($d/dx$), replacing $\overline{G}$ by $K_n$. 

                    \medskip 

                    The first step towards the duality theory developed here was the combinatorial interpretation of integrals 
                    over products of Hermite polynomials (see~[9], VI-34, remark 21, or the recent book [1], chapter 6.9): 
                    $$ 
                    \overline{\mu}(\overline{ K_{n_1} \uplus \dots \uplus K_{n_k} },0) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(K_{n_1},x) \cdots \mu(K_{n_k},x) \cdot dx, 
                    $$ 
                    where $K_{n_1} \uplus \dots \uplus K_{n_k}$ denotes the vertex disjoint union of the complete graphs 
                    $K_{n_1},\dots,K_{n_k}$. 
                    Even this formula has been neglected in physics (for instance, in [5] there is no consideration of duality 
                    at all) as can be seen from the fact that Itzykson and Zuber~[6] need a whole page to solve their 
                    integral~(3.5), the result being evident from the previous formula. 

                    The second step was the realization, due to Godsil~[4], that, more generally, 
                    $$ 
                    \overline{\mu}(\overline{G},0) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(G,x) \cdot dx, 
                    $$ 
                    the equation $\mu(K_{n_1},x) \cdots \mu(K_{n_k},x) = \mu(K_{n_1} \uplus \dots \uplus K_{n_k},x)$ 
                    being evident. 

                    Finally, the last step of duality theory is the derivation of direct formulas for the matching polynomials 
                    of the complementary graph. In this context Godsil mainly proposed 
                    $$ 
                    \mu(\overline{G},x) \; = \; \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot \mu(K_{n-2r},x), 
                    $$ 
                    but also the more explicit formula 
                    $$ 
                    \overline{\mu}(\overline{G},y) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(G,x+y) \cdot dx 
                    $$ 
                    is a specialization of theorem~2.4 in~[4], that Godsil did not reproduce in his book~[3]. 

                    \medskip 

                    We propose two new duality theorems by means of differential operators, a slight 
                    modification of Godsil's last theorem together with a scalar product formula and, 
                    finally, the Fourier transform interpretation. 


                    Our proofs of section 3 make use of generating functions for set functions. 
                    We must say that the set function machinery developed in the next section 
                    has been the adequate tool for deriving those duality theorems. 


                    %%%%%%%%%%%%%%%%%%%%% 
                    % %% 
                    % Algebraic tools %% 
                    % % 
                    %%%%%%%%%%%%%%%%%%%%% 

                    \bigskip 

                    \centerline{\bf 2. Algebraic tools} 

                    \medskip 

                    \noindent 
                    Let $V$ be a finite set and 
                    $$\openup2pt\eqalign{ 
                    f: 2^V & \to A \cr 
                    V' \subseteq V & \mapsto f(V') \in A \cr 
                    }$$ 
                    be a set function, where $A$ is a commutative ring with $1$. Consider the generating function 
                    $$ 
                    F_f(\nu) := \sum_{V' \subseteq V} f(V') \cdot \nu^{V'}, \qquad \nu^{\emptyset} := 1, 
                    $$ 
                    subject to the following multiplication rules ($V',V'' \subseteq V$): 
                    $$ 
                    \nu^{V'} \cdot \nu^{V''} := \nu^{V'+V''}, \quad \hbox{where} 
                    $$ 
                    $$ 
                    V'+V'' := 
                    \openup 2pt\left\{\eqalign{ 
                    V' \cup V'', \quad & \hbox{if} \quad V' \cap V'' = \emptyset, \cr 
                    \dag, \; \; \quad \quad & \hbox{if} \quad V' \cap V'' \ne \emptyset, \quad \hbox{where} \cr 
                    }\right. 
                    $$ 
                    $$ 
                    \dag + V' := \dag, \quad \dag + \dag := \dag, \qquad \hbox{and} \qquad \nu^{\dag} := 0. 
                    $$ 
                    The algebra $A[V]$ of those generating functions is not unknown. In fact, we have the isomorphism 
                    $$ 
                    A[V] \simeq A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle, 
                    $$ 
                    if $V$ contains $n$ elements. 

                    \medskip 

                    \noindent 
                    {\bf Example.} For $V' \subseteq V$ put 
                    $$ 
                    (fg)(V') := \sum_{V' = V'' \uplus V'''} f(V'') \cdot g(V''') 
                    $$ 
                    ($f,g,fg: 2^V \to A$). Then 
                    $$ 
                    F_{fg} (\nu) = F_f (\nu) \cdot F_g (\nu). 
                    $$ 

                    \medskip 

                    For $|V| = \infty$ let $F(V)$ be the partially ordered set of finite subsets of $V$. We have the canonical 
                    projections $p_{V',V''}: A[V'] \to A[V'']$ ($V',V'' \in F(V), V' \supseteq V''$) and define 
                    $$ 
                    A[V] := \lim_{\longleftarrow} A[V'], \quad V' \in F(V) 
                    $$ 
                    in order to work with generating functions of the form 
                    $$ 
                    F_f (\nu) = \sum_{V' \in F(V)} f(V') \cdot \nu^{V'}. 
                    $$ 
                    Let 
                    $$ 
                    V := \sum_{v \in V} \nu^{\{v\}} 
                    $$ 
                    be the generating function for the indicator function of the subsets of $V$ of cardinality~$1$ 
                    (the double use of $V$ for the set itself on the one hand and for an element of $A[V]$ 
                    on the other hand will never cause confusion). In the product $V^n$ each subset of cardinality~$n$ 
                    occurs $n!$~times, so that $V^n/n!$ represents the indicator function of the subsets of the set $V$ 
                    of cardinality $n$. The identity 
                    $$ 
                    \sum_{n=0}^{\infty} f(n) \cdot V^n/n! \; = \sum_{V' \in F(V)} f(|V'|) \cdot \nu^{V'}, 
                    \quad f: {\bb N} \to A, 
                    $$ 
                    provides an imbedding of the ring $A![[V]]$ of generating functions of exponential type 
                    (usually the variable is called $x$ instead of $V$) into our ring $A[V]$. 
                    It is at the origin of (almost?) all applications of $A![[V]]$ into combinatorics, but 
                    requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, 
                    $A[V]$ gives more flexibility and closeness to combinatorics. In addition, $A[V]$ is ideally 
                    suited for computer calculations (for more details and lots of different applications see~[7]). 

                    \medskip 

                    \noindent 
                    {\bf Remark.} The ring ${\bb Z}![[V]]$ is not noetherian, but it contains the important functions 
                    $\exp(V)$ and $\log(1+V)$. 

                    \medskip 

                    \noindent 
                    {\bf Example.} If $char \; A = 2$, then we have 
                    $$\openup2pt\eqalign{ 
                    (1+V)^{-1} \; & = \; \sum_{n=0}^{\infty} (-1)^n n! \cdot V^n/n! \cr 
                    & \equiv \; 1+V \quad \hbox{and} \cr 
                    \log(1+V) \; & = \; \sum_{n=1}^{\infty} (-1)^{n-1} (n-1)! \cdot V^n/n! \cr 
                    & \equiv \; V+V^2/2 \cr 
                    }$$ 
                    in the ring $A![[V]]$. These identities are at the origin of lots of results of parity in combinatorics. 

                    \medskip 

                    \noindent 
                    For all $t \in A$ we put $(t\nu)^{V'} \; := \; t^{|V'|} \cdot \nu^{V'}$, $\; V' \subseteq V$, and 
                    therefore 
                    $$ 
                    F_f(t\nu) \; = \; \sum_{\emptyset \subseteq V' \subseteq V} f(V') \; t^{|V'|} \cdot \nu^{V'}. 
                    $$ 
                    It is evident that this definition is compatible with the addition and the multiplication. Most important 
                    are the special cases $t = -1$ and $t = 0$: $F_f(0) = F_f(0 \cdot \nu) = f(\emptyset)$. If $F_f (0) = 0$, 
                    then $F_f(\nu)^n/n!$ is defined for any ring $A$, because a partition into $n$ nonempty subsets can be 
                    ordered in $n!$ different ways. Thus we have an operation of $A![[V]]$ on $A[V]$ via the substitution 
                    $G(F_f (\nu))$ defined for any $G \in A![[V]]$. 

                    \medskip 

                    \noindent 
                    Finally, define for any $f,g: 2^V \to A$ the function $f*g: 2^V \to A$ by 
                    $$ 
                    (f*g)(V') := f(V') \cdot g(V') 
                    $$ 
                    for each $V' \subseteq V$ and define the Hadamard product to be 
                    $$ 
                    F_f (\nu) * F_g (\nu) := F_{f*g} (\nu). 
                    $$ 

                    \eject 

                    %%%%%%%%%%%%%%%%%%%%%% 
                    % % 
                    % Duality theorems % 
                    % %% 
                    %%%%%%%%%%%%%%%%%%%%%% 


                    \centerline{\bf 3. Duality theorems} 

                    \medskip 

                    Let $G = (V,E)$ be a finite simple graph and let $\overline{G} = (V,\overline{E})$ be its complement. 
                    We have identified $V$ with the generating function of the indicator function of the one-element subsets 
                    of $V$, and we have realized that $V^2/2$ corresponds to the indicator function of the two-element 
                    subsets of $V$. Similarly, we identify $E$ and $\overline{E}$ with the generating functions 
                    of the indicator functions of $E,\overline{E} \subseteq 2^V$. Since every two-element subset of $V$ 
                    either belongs to $E$ or to $\overline{E}$, we have the following fundamental identity, valid in 
                    the ring $A[V]$: 
                    $$\bf 
                    E + \overline{E} \; = \; V^2/2. 
                    $$ 

                    Let $p(G)$ be the number of perfect matchings (if $|V| \equiv 0 \bmod 2$) or quasi-perfect matchings 
                    (if $|V| \equiv 1 \bmod 2$), and let $c(G)$ be the number of arbitrary matchings of $G$. We denote by 
                    $G[V']$ the subgraph of $G$ induced by $V' \subseteq V$, i.e.~its vertices are the elements of $V'$ 
                    and its edges are the edges of $G$ having both endpoints in $V'$. Then the perfect matchings are 
                    counted by $\exp[E]$, the quasi-perfect matchings by $V \cdot \exp[E]$, and altogether 
                    we have the identities 
                    $$\openup2pt\eqalign{ 
                    1+\sum_{\emptyset \subset V' \subseteq V} p(G[V']) \cdot \nu^{V'} \; & = \; (1+V) \cdot \exp [E], \cr 
                    1+\sum_{\emptyset \subset V' \subseteq V} c(G[V']) \cdot \nu^{V'} \; & = \; \exp [V+E]. 
                    }$$ 
                    The following proposition was proved in~[8],~5.18, for the case of perfect matchings. 

                    \medskip 

                    \noindent 
                    {\bf Proposition.} \quad $c(\overline{G}) \; \equiv \; p(G) \; \bmod 2$. 

                    \medskip 

                    \noindent 
                    {\bf Proof.} Using the previous three identities we have 
                    $$ 
                    \exp [V+\overline{E}] \; = \; \exp [V+V^2/2-E] \; \equiv \; 
                    \exp [\log (1+V) + E] \; = \; (1+V) \cdot \exp [E].\qeda 
                    $$ 

                    \medskip 

                    From the very definitions of the matching polynomials we have the following generating functions: 
                    $$\openup2pt\eqalign{ 
                    1+\sum_{\emptyset \subset V' \subseteq V} \mu(G[V'],x) \cdot \nu^{V'} \; & = \; 
                    \exp [xV-E], \cr 
                    1+\sum_{\emptyset \subset V' \subseteq V} \overline{\mu}(G[V'],x) \cdot \nu^{V'} \; & = \; 
                    \exp [xV+E]. \cr 
                    }$$ 

                    Considering the first equality for the complete graph $K_\infty$ on an infinite set of vertices 
                    yields the classical generating function of exponential type for Hermite polynomials: 
                    $$ 
                    1+\sum_{n=1}^{\infty} \mu(K_n,x) \cdot V^n/n! \; = \; 
                    \exp [xV-V^2/2]. 
                    $$ 

                    \medskip 

                    We are now in a position to provide a very short proof of Godsil's duality theorem.

                    \medskip 

                    \noindent 
                    {\bf Duality theorem (Godsil).} 
                    $$ 
                    \mu(\overline{G},x) \; = \; \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot \mu(K_{n-2r},x). 
                    $$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} Using the set function algebra developed in section 2 we have: 
                    $$ 
                    \exp[xV-\overline{E}] \; = \; \exp[xV-V^2/2+E] \; = \; \exp[E] \cdot \exp[xV-V^2/2].\qeda 
                    $$ 

                    \bigskip 

                    We can further establish the following new identities. 

                    \medskip 

                    \noindent 
                    {\bf Duality theorem for the matching polynomials ($\frac{d^2}{dx^2}$).} 
                    $$\openup2pt\eqalign{ 
                    \overline{\mu}(\overline{G},x) \; & = \; \exp \bigl[\hbox{$\frac{d^2}{dx^2}$}/2 \bigr] \cdot \mu(G,x), \cr 
                    \mu(\overline{G},x) \; & = \; \exp \bigl[- \hbox{$\frac{d^2}{dx^2}$}/2 \bigr] \cdot \overline{\mu}(G,x). \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} As in the preceding proof, 
                    $$\openup2pt\eqalign{ 
                    \exp[xV+\overline{E}] \; & = \; \exp[V^2/2] \cdot \exp[xV-E] \cr 
                    & = \; \exp[\hbox{$\frac{d^2}{dx^2}$}/2] \cdot \exp[xV-E], \cr 
                    }$$ 
                    because $\frac{d}{dx} \exp[xV-E] \; = \; V \cdot \exp[xV-E]$. The differential operator 
                    $\exp \bigl[-\frac{d^2}{dx^2}/2 \bigr]$ is the inverse of $\exp \bigl[\frac{d^2}{dx^2}/2 \bigr]$.\qeda 

                    \bigskip 

                    \noindent 
                    {\bf Duality theorem for the matching polynomials ($\frac{d}{dx}$).} 
                    $$\openup2pt\eqalign{ 
                    \overline{\mu}(\overline{G},x) \; & = \; 
                    e^{-x^2/2} \cdot \mu(G,\hbox{$\frac{d}{dx}$}) \cdot e^{x^2/2}, \cr 
                    \mu(\overline{G},x) \; & = \; 
                    e^{x^2/2} \cdot \overline{\mu}(G,- \hbox{$\frac{d}{dx}$}) \cdot e^{-x^2/2}. \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} By the Taylor formula we know that 
                    $$ 
                    f(x+a) \; = \; \exp[\hbox{$\frac{d}{dx}$} a] \cdot f(x) 
                    $$ 
                    for variables $x,a$ and a formal power series $f$. It follows that 
                    $$\openup2pt\eqalign{ 
                    & \exp[-x^2/2] \cdot \exp[\hbox{$\frac{d}{dx}$} V - E] \cdot \exp[x^2/2] \cr 
                    & = \; \exp[-x^2/2] \cdot \exp[-E] \cdot \exp[\hbox{$\frac{d}{dx}$} V] \cdot \exp[x^2/2] \cr 
                    & = \; \exp[-x^2/2] \cdot \exp[-E] \cdot \exp[(x+V)^2/2] \cr 
                    & = \; \exp[xV + \overline{E}]. \cr 
                    }$$ 
                    The second equality is proved in the same way.\qeda 

                    \bigskip 

                    Specializing the second equality of the preceding theorem to Hermite polynomials, i.e.~replacing 
                    $\overline{G}$ by $K_n$, provides the classical definition of Hermite polynomials. However, we 
                    could not find the specialization to Hermite polynomials of the first equality, 
                    i.e.~the differential operator $He_n(d/dx)$, in the literature. 

                    \eject 

                    Finally, we can prove several integral formulae. 

                    \medskip 

                    \noindent 
                    {\bf Duality theorem for the matching polynomials ($\int$).} 
                    $$ 
                    \overline{\mu}(\overline{G},y) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{-(x-y)^2/2} \cdot \mu(G,x) \cdot dx. 
                    $$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} Using the invariance of the integral with respect to translations we get: 
                    $$\openup2pt\eqalign{ 
                    & \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-(x-y)^2/2] \cdot \exp[xV-E] \cdot dx \cr 
                    & = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-s^2/2] \cdot \exp[(s+y)V-E] \cdot ds \cr 
                    & = \; \exp[yV+\overline{E}] \cdot \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} \exp[-(s-V)^2/2] \cdot ds \cr 
                    & = \; \exp[yV+\overline{E}] \cdot \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} \exp[-t^2/2] \cdot dt \cr 
                    & = \; \exp[yV+\overline{E}].\qeda \cr 
                    }$$ 

                    \bigskip 

                    For graphs $G' = (V',E')$ and $G'' = (V'',E'')$ we have the following result.

                    \medskip 

                    \noindent 
                    {\bf Scalar product formula.} 
                    $$\openup2pt\eqalign{ 
                    \overline{\mu}(\overline{G' \uplus G''},0) \; & = \; 
                    \hbox{$\frac{1}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} \mu(G',x) \cdot \mu(G'',x) \cdot e^{-x^2/2} \cdot dx \cr 
                    & = \; \overline{\mu}(\overline{G'},\hbox{$\frac{d}{dx}$}) \cdot 
                    \overline{\mu}(\overline{G''},x) \Bigr|_{x=0}. \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} The first equality being evident from the previous theorem, we just have to prove the 
                    second one: 
                    $$\openup2pt\eqalign{ 
                    & \exp [ \hbox{$\frac{d}{dx}$} V' + \overline{E'} ] \cdot 
                    \exp [ x V'' + \overline{E''} ] \Bigr|_{x=0} \cr 
                    & = \; \exp [ \overline{E'} ] \cdot 
                    \exp [ (x+V') V'' + \overline{E''} ] \Bigr|_{x=0} \cr 
                    & = \; \exp [ V'V'' + \overline{E'} + \overline{E''} ].\qeda \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Remark.} If $G' = K_n$ and $G'' = K_m$, then the scalar product formula counts the number of perfect 
                    matchings of the complete bipartite graph $\overline{K_n \uplus K_m}$, which is equal to zero, if 
                    $n \ne m$, and equal to $n!$, if $n = m$. This is the orthogonality of the Hermite polynomials. 

                    \bigskip 

                    \noindent 
                    The previous duality theorem implies 
                    $ 
                    \mu(\overline{G},y) = \hbox{$\frac{(-i)^n}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{-(x-yi)^2/2} \cdot \mu(G,x) \cdot dx. 
                    $ 
                    This proves the following theorem. 

                    \medskip 

                    \noindent 
                    {\bf Duality theorem for the matching polynomial (${\bb C}$).} 
                    $$ 
                    e^{-y^2/2} \mu(\overline{G},y) \; = \; \hbox{$\frac{(-i)^n}{\sqrt{2\pi}}$} 
                    \int_{-\infty}^{\infty} e^{xyi} \cdot e^{-x^2/2}\mu(G,x) \cdot dx.\qeda 
                    $$ 

                    \medskip 

                    If we call $e^{-x^2/2}\mu(G,x)$ matching function of $G$, then this matching function is even 
                    for $n$ even and odd for $n$ odd.  

                    \bigskip 

                    \noindent 
                    {\bf Duality theorem for the matching polynomial (${\bb R}$).} 
                    $$\openup2pt\eqalign{ 
                    & e^{-y^2/2}\mu(\overline{G},y) \cdot (-1)^{n/2} \cr 
                    \; & = \; \hbox{$\sqrt{\frac{2}{\pi}}$} \cdot 
                    \int_{0}^{\infty} \cos(xy) \cdot e^{-x^2/2}\mu(G,x) \cdot dx, \qquad n \quad even, \cr 
                    & \cr 
                    & e^{-y^2/2}\mu(\overline{G},y) \cdot (-1)^{(n-1)/2} \cr 
                    \; & = \; \hbox{$\sqrt{\frac{2}{\pi}}$} \cdot 
                    \int_{0}^{\infty} \sin(xy) \cdot e^{-x^2/2}\mu(G,x) \cdot dx, \qquad n \quad odd. \cr 
                    }$$ 
                    {\it Thus the matching functions of $\overline{G}$ and $G$ are, up to an eventual multiplication 
                    by $-1$, real Fourier transforms of one another.\qeda} 

                    \bigskip 


                    %%%%%%%%%%% 
                    % % 
                    % Zeros % 
                    % %% 
                    %%%%%%%%%%% 

                    \bigskip 

                    \centerline{\bf 4. Zeros} 

                    \medskip 

                    From now on every edge $\{u,v\} \in E$ of our graph $G = (V,E)$ will get a positive real 
                    weight~$w_{\{u,v\}}$ (we can assume that the two-element subsets of $V$ which are not edges 
                    get the weight zero). 
                    This weighted graph will be denoted by $G_w = (V,E_w)$. In particular, $E_w$ will be identified with the 
                    generating function of the set function which attributes the value $0$ to all subsets of $V$ with the 
                    only exception of the edges of $G$, which get their own weights. 
                    The (weighted) matching polynomial can be defined with the help of its generating function: 
                    $$ 
                    1+\sum_{\emptyset \subset V' \subseteq V} \mu(G_w[V'],x) \cdot \nu^{V'} \; = \; \exp [xV-E_w]. 
                    $$ 
                    We see that every matching is counted with respect to its weight: the product of the weights of its 
                    edges. 

                    \medskip 

                    A Hamiltonian cycle of $G_w$ is a cyclic order of $V$ and its weight is the product of the weights of 
                    its $n = |V|$ edges corresponding to two consecutive vertices in the cyclic order. In particular, if 
                    the edge corresponding to two consecutive vertices in the cyclic order does not belong to the graph 
                    (equivalently, has weight zero), then the weight of that ``Hamiltonian cycle'' is equal to zero. 
                    Let cyc$(G_w)$ be the sum of the weights of all Hamiltonian cycles of $G_w$, with the convention that 
                    cyc$(G_w) = 1$ if $n = 1$. We assume that the weight of each edge in the complete graph $K_n$ is 
                    equal to $1$, so that cyc$(K_n) = (n-1)!$. 

                    A Hamiltonian path of $G_w$ is a linear order of $V$ and its weight is the product of the weights of 
                    its $n-1$ edges corresponding to two consecutive vertices in the linear order. 
                    Let lin$(G_w)$ be the sum of the weights of all Hamiltonian paths of $G_w$, with the convention that 
                    lin$(G_w) = 1$ if $n = 1$. Clearly, lin$(K_n) = n!$. 

                    \medskip 

                    \noindent 
                    Let us put 
                    $$ 
                    \hbox{cyc}_{G_w}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \hbox{cyc}(G_w[V']) \cdot \nu^{V'}, \quad 
                    \hbox{lin}_{G_w}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \hbox{lin}(G_w[V']) \cdot \nu^{V'}. 
                    $$ 
                    Considering the infinite graph $K_{\infty}$ yields 
                    $$ 
                    \sum_{n=1}^{\infty} \hbox{cyc}(K_n) \cdot V^n/n! \; = \; -\log (1-V), \quad 
                    \sum_{n=1}^{\infty} \hbox{lin}(K_n) \cdot V^n/n! \; = \; \frac{V}{1-V}. 
                    $$ 
                    Usually (in undirected graphs) one does not distinguish between the two different directions 
                    of Hamiltonian cycles or paths. In this sense cyc$_{G_w}(\nu)$ and lin$_{G_w}(\nu)$ count 
                    them ``twice''. Now we can prove our generalization of the Mehler formula. 

                    \medskip 

                    \noindent 
                    {\bf Theorem.} Using the Hadamard product $*$ we have: 
                    $$\openup2pt\eqalign{ 
                    &\exp \bigl[ xV-E_w \bigr] \; * \; \exp \bigl[ yV-E_w \bigr] \cr 
                    &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + 
                    \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[ \hbox{$-(\frac{x-y}{2})^2$} \cdot \hbox{lin}_{G_w}(\nu) 
                    \hbox{$-(\frac{x+y}{2})^2$} \cdot \hbox{lin}_{G_w}(-\nu) \bigr]. \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} Two matchings of $G_w$ to be considered in the left hand side of the theorem provide 
                    a partition of $V$ into even Hamiltonian cycles (to be counted ``twice'', because the matchings can 
                    be interchanged), even (according to the number of vertices) Hamiltonian paths (to be counted with 
                    the factor $-x^2$ or $-y^2$, because the number of edges of the paths is odd) and odd Hamiltonian 
                    paths (to be counted with the factor $2xy$). Thus the left hand side is equal to 
                    $$\openup2pt\eqalign{ 
                    &\exp \biggl[\frac{\hbox{cyc}_{G_w}(\nu) + \hbox{cyc}_{G_w}(-\nu)}{4} \cdot 2 \biggr] \; \cdot \cr 
                    &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) + \hbox{lin}_{G_w}(-\nu)}{4} \cdot (-x^2-y^2) \biggr] \; \cdot \cr 
                    &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) - \hbox{lin}_{G_w}(-\nu)}{4} \cdot 2xy \biggr]. \cr 
                    }$$ 
                    But this is precisely the right hand side of the theorem.\qeda 

                    \eject 

                    \noindent 
                    Specializing to $K_{\infty}$ yields the Mehler formula. 

                    \medskip 

                    \noindent 
                    {\bf Corollary (Mehler).} 
                    $$ 
                    1+\sum_{n=1}^{\infty} \mu(K_n,x)\mu(K_n,y) \cdot V^n/n! \; = \; 
                    \hbox{$\frac{1}{\sqrt{1-V^2}}$} \cdot 
                    \exp \bigl[ \hbox{$(\frac{x+y}{2})^2$} \cdot \hbox{$\frac{V}{1+V}$} - 
                    \hbox{$(\frac{x-y}{2})^2$} \cdot \hbox{$\frac{V}{1-V}$} \bigr].\qeda 
                    $$ 

                    \bigskip 

                    \noindent 
                    Replacing $y$ in the previous theorem by the complex conjugate number $\overline{x}$ yields
                    the following corollary.

                    \medskip 

                    \noindent 
                    {\bf Corollary.} 
                    $$\openup2pt\eqalign{ 
                    &\exp \bigl[ xV-E_w \bigr] \; * \; \exp \bigl[ \overline{x}V-E_w \bigr] \cr 
                    &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + 
                    \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) 
                    -(\Re e \; x)^2 \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \cr 
                    &= \; \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) \bigr] \; \cdot \; 
                    \Bigl( \exp \bigl[ (\Re e \; x)V-E_w \bigr] \; * \; \exp \bigl[ (\Re e \; x)V-E_w \bigr] \Bigr). \cr 
                    }$$ 
                    {\it Therefore $|\mu(G_w,x)|^2 \; \ge \; [(\Im m \; x)^2]^n + 2W\cdot[(\Im m \; x)^2]^{n-1}$ for every 
                    $x \in {\bb C}$, where $W$ is the sum of the weights of all edges of $G_w$. In particular, all zeros of 
                    $\mu(G_w,x)$ are real.\qeda} 

                    \bigskip 

                    We finish this article by considering a common generalization of the matching polynomial and the 
                    classical rook polynomial. Thus we do not just have our weighted graph $G'_w = (V',E'_w)$, but also 
                    a bipartite graph $G''_w = (V',V'';E''_w)$. In other words, we have a graph $G_w = (V,E_w)$ with vertex 
                    set $V := V' \uplus V''$, edge set $E_w := E'_w \uplus E''_w$ and, in particular, no edges between 
                    vertices of $V''$. The weights of the edges of $G'_w$ are still assumed to be positive, whereas 
                    the weights of the edges of $G''_w$ are supposed to be such that for each $v'' \in V''$ the 
                    weights of the edges incident with $v''$ all have the same sign, i.e.~they are all 
                    positive or all negative. 

                    Let $\exp[xV'+V''-E'_w-E''_w]$ be the generating function of our generalized matching polynomials, and 
                    let cyc$_{G_w}(\nu)$ count the Hamiltonian cycles ``twice''. Moreover, let lin$_{G_w}(\nu)$, 
                    lin'$_{G_w}(\nu)$, lin''$_{G_w}(\nu)$ count the Hamiltonian paths ``twice'' which have both endpoints 
                    in $V'$, one endpoint in $V'$ and one endpoint in $V''$, both endpoints in $V''$, respectively. 
                    (Note that lin$_{G_w}(\nu)$ is nonnegative by our restrictions on the weights.) 
                    

                    \medskip 

                    \noindent 
                    {\bf Theorem.} 
                    $$\openup2pt\eqalign{ 
                    &\exp \bigl[ xV'+V''-E'_w-E''_w \bigr] \; * \; \exp \bigl[ yV'+V''-E'_w-E''_w \bigr] \cr 
                    &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + 
                    \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[ \hbox{$-(\frac{x-y}{2})^2$} \cdot \hbox{lin}_{G_w}(\nu) 
                    \hbox{$-(\frac{x+y}{2})^2$} \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[ \hbox{$-\frac{x+y}{2}$} \cdot \hbox{lin'}_{G_w}(-\nu) \bigr] \; \cdot \; 
                    \exp \bigl[-\hbox{lin''}_{G_w}(-\nu) \bigr]. \cr 
                    }$$ 

                    \medskip 

                    \noindent 
                    {\bf Proof.} Clearly, both sides of the equality are equal to 
                    $$\openup2pt\eqalign{ 
                    &\exp \biggl[\frac{\hbox{cyc}_{G_w}(\nu) + \hbox{cyc}_{G_w}(-\nu)}{4} \cdot 2 \biggr] \; \cdot \cr 
                    &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) + \hbox{lin}_{G_w}(-\nu)}{4} \cdot (-x^2-y^2) \biggr] \; \cdot \; 
                    \exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) - \hbox{lin}_{G_w}(-\nu)}{4} \cdot 2xy \biggr] \; \cdot \; \cr 
                    &\exp \biggl[\frac{\hbox{lin'}_{G_w}(\nu) + \hbox{lin'}_{G_w}(-\nu)}{4} (-x-y) \biggr] \; \cdot \; 
                    \exp \biggl[\frac{\hbox{lin'}_{G_w}(\nu) - \hbox{lin'}_{G_w}(-\nu)}{4} (x+y) \biggr] \; \cdot \; \cr 
                    &\exp \biggl[\frac{\hbox{lin''}_{G_w}(\nu) + \hbox{lin''}_{G_w}(-\nu)}{4} \cdot (-2) \biggr] \; \cdot \; 
                    \exp \biggl[\frac{\hbox{lin''}_{G_w}(\nu) - \hbox{lin''}_{G_w}(-\nu)}{4} \cdot 2 \biggr].\qeda \cr 
                    }$$ 

                    \bigskip 

                    \medskip 

                    \noindent 
                    {\bf Corollary.} 
                    $$\openup2pt\eqalign{ 
                    &\exp \bigl[ xV'+V''-E'_w-E''_w \bigr] \; * \; \exp \bigl[ \overline{x}V'+V''-E'_w-E''_w \bigr] \cr 
                    &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + 
                    \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) 
                    -(\Re e \; x)^2 \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\, \exp \bigl[-(\Re e \; x) \cdot \hbox{lin'}_{G_w}(-\nu) \bigr] \; \cdot \; 
                    \exp \bigl[-\hbox{lin''}_{G_w}(-\nu) \bigr] \cr 
                    &= \; \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) \bigr] \; \cdot \; \cr 
                    & \quad \;\; \Bigl( \exp \bigl[ (\Re e \; x)V'+V''-E'_w-E''_w \bigr] \; * \; 
                    \exp \bigl[ (\Re e \; x)V'+V''-E'_w-E''_w \bigr] \Bigr). \cr 
                    }$$ 
                    {\it Since} $\hbox{lin}_{G_w}(\nu)$ {\it is nonnegative, all zeros of our generalized matching polynomial 
                    are real.\qeda} 

                    \bigskip 
                    \bigskip 

                    \noindent 
                    {\it Acknoledgements:} \quad 
                    First of all, I should like to thank cordially D.~Foata to have made the redaction of this article possible 
                    by inviting me to the IRMA in Strasbourg and by explaining to me his combinatorial proof of the 
                    Mehler formula. His help and support are undescribable. 
                    I also want to express my gratitude to A.~Frank for his recommendation of the beautiful book [3] 
                    (otherwise [7], chapter 3.1, would not exist), and especially to E.~Triesch (without him [7] would not 
                    exist). 

                    \vfill

                    \eject 

                    %%%%%%%%%%%%%%%%%%%%%%% 
                    %% BIBLIOGRAPHIE %% 
                    %%%%%%%%%%%%%%%%%%%%%%% 

                    \centerline{\tenbf References} 

                    \bigskip 
                    \medskip 

                    {\baselineskip=9pt\tenrm 
                    \item{[1]} {\sc G.~E.~Andrews, R.~Askey, R.~Roy:} 
                    {\it Special Functions,} 
                    Encyclopedia of mathematics and its applications, Vol.~71, 
                    Cambridge University Press, 1999. 
                    \smallskip 

                    \item{[2]} {\sc D.~Foata:} 
                    A combinatorial proof of the Mehler formula, 
                    {\it J.~Combinatorial Theory Ser.~A,} 
                    {\bf 24} (1978), 367-376. 
                    \smallskip 

                    \item{[3]} {\sc C.~D.~Godsil:} 
                    {\it Algebraic Combinatorics,} 
                    Chapman \& Hall, 1993. 
                    \smallskip 

                    \item{[4]} {\sc C.~D.~Godsil:} 
                    Hermite polynomials and a duality relation for matchings polynomials, 
                    {\it Combinatorica,} 
                    {\bf 1} (1981), 257-262. 
                    \smallskip 

                    \item{[5]} {\sc O.~J.~Heilmann, E.~H.~Lieb:} 
                    Theory of monomer-dimer systems, 
                    {\it Comm. Math.~Physics,} 
                    {\bf 25} (1972), 190-232. 
                    \smallskip 

                    \item{[6]} {\sc C.~Itzykson, J.-B.~Zuber:} 
                    Matrix integration and combinatorics of modular groups, 
                    {\it Comm.~Math.~Physics,} 
                    {\bf 134} (1990), 197-207. 
                    \smallskip 

                    \item{[7]} {\sc B.~Lass:} 
                    {\it Funktionen z\"{a}hlen,} 
                    Diplomarbeit, 1997. 
                    \smallskip 

                    \item{[8]} {\sc L.~Lov\'asz:} 
                    {\it Combinatorial Problems and Exercises,} 
                    Akad\'emiai Kiad\'o, 1993. 
                    \smallskip 

                    \item{[9]} {\sc G.~Viennot:} 
                    {\it Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux,} 
                    Notes de con\-f\'erences donn\'ees \`a l'Universit\'e du Qu\'ebec \`a Montr\'eal, 1983. 
                    \smallskip 
                    } 

                    \bigskip 
                    \bigskip 
                    \bigskip 

                    \noindent{\bf Bodo Lass} 

                    \vskip 6pt 

                    {\parindent=0mm 
                    {\it Lehrstuhl II f\"{u}r Mathematik, 

                    RWTH Aachen, 

                    Templergraben 55, 

                    D-52062 Aachen, 

                    Germany} 

                    \medskip 

                    lass@math2.rwth-aachen.de 
                    \par} 

                    \end 