\documentclass[11pt, a4paper]{article}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt} \setlength{\headsep}{0pt}
\setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Th\'eor\`eme}%[section]
\newtheorem{thm}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{prop}{Proposition}
\newtheorem{corollary}{Corollaire}%[section]
\newtheorem{coro}{Corollary}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{fact}{Fact}%[section]
%\newtheorem{definition}{Definition}%[section]
%\newtheorem{example}{Example}
\newcommand\cyc{\mathop{\rm cyc}}
%\newenvironment{proof}{{\em Proof.}}{\mbox{}\hfill $\Box$\medskip}
\newenvironment{example}    {\smallskip\noindent{\bf Example.}} {\smallskip}
\newenvironment{remark}     {\smallskip\noindent{\bf Remark.}} {\smallskip}
\newenvironment{definition} {\smallskip\noindent{\bf Definition.}} {\smallskip}
%binomial coefficients:\bi{#1}{#2}
\newcommand\bi[2]{{{#1}\atopwithdelims(){#2}}}
%q-binomial coefficients:\qbi{#1}{#2}{#3}
\newcommand\qbi[3]{{{#1}\atopwithdelims[]{#2}}_{#3}}
\pagestyle{plain}
\newtheorem*{theo}{Th\'eor\`eme}
\newtheorem{conj}{Conjecture}
\newtheorem{lem}{Lemme}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\numberwithin{equation}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\refname{References}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{The Algebra of Set Functions II~: \\
An Enumerative Analogue of Hall's Theorem for Bipartite Graphs}
\author{Bodo Lass\\
\small Universit\'e de Lyon ; Universit\'e Lyon 1 ; \\[-0.8ex]
\small INSA de Lyon, F-69621 ; Ecole Centrale de Lyon ; \\[-0.8ex]
\small CNRS, UMR5208, Institut Camille Jordan, \\[-0.8ex]
\small 43 blvd du 11 novembre 1918, \\[-0.8ex]
\small F-69622 Villeurbanne-Cedex, France \\[-0.8ex]
\small \texttt{lass} @ \texttt{math.univ-lyon1.fr}\\[-0.8ex]
}
\date{}
%\small 2000 Mathematics Subject Classification : 05}

\maketitle

\centerline{\emph{Dedicated to Eberhard Triesch}}
\bigskip

\begin{abstract}
Triesch~\cite{T} conjectured that Hall's classical theorem on matchings in bipartite graphs
is a special case of a phenomenon of monotonicity for the number of matchings in such graphs.
We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit
monotonic formula counting matchings in bipartite graphs.

This formula follows from a general duality theory which we develop for counting matchings.
Moreover, we make use of generating functions for set functions as introduced in~\cite{L5},
and we show how they are useful for counting matchings in bipartite graphs in many different ways.
\end{abstract}

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

\section{Introduction}

The bipartite graphs studied in this paper are described as triples
\begin{equation}
G \; = \; (X,Y;E), \qquad E \subseteq X \times Y,
\end{equation}
where $X$ and $Y$ are the two {\it vertex sets}, and~$E$ is the {\it edge set}.
It is always assumed that~$X$, called the {\it first vertex set}, is finite and
$|X|=n$. The {\it second vertex set} $Y$ is also finite, but variable.
As the edge set $E$ is a subset of $X \times Y$, all the graphs are simple~:
they have no loops, and no multiple edges.
For each nonempty subset $X'$ of~$X$ define the {\it set of neighbours} of~$X'$ by
\begin{equation}
\Gamma_G(X') \; := \; \{ y \in Y \; | \; \exists \; x \in X' \; {\rm such \; that} \; (x,y) \in E \}.
\end{equation}
Thus, $\Gamma_G(X')$ is the set of all vertices $y \in Y$ which are related to at least one vertex
in~$X'$ by an edge of~$G$. Also, let
\begin{equation}
d^+_G(X') \; := \; |\Gamma_G(X')|.
\end{equation}
As will be seen, the integral-valued function $d^+_G : 2^X \setminus \emptyset \to \mathbb{Z}$,
further called {\it set function}, determines~$G$ up to a permutation of the vertices of~$Y$.

An {\it injective} mapping $i : X' \to Y$ such that $(x,i(x)) \in E$ for every $x \in X'$
is called a {\it matching} of~$X'$ into~$Y$ and the pairs $(x,i(x))$ ($x\in X'$) are the edges
of the matching. Let $m^-_G(X')$ be the number of such injective mappings (or matchings).
The mapping $m^-_G : 2^X \setminus \emptyset \to \mathbb{Z}$ is then another set function.
We show that it also determines~$G$ up to a permutation of the vertices of~$Y$, and
we prove an easy formula allowing to calculate the set function~$m^-_G$ with the
help of the set function~$d^+_G$. Moreover, $d^+_G$ can be calculated with the
help of~$m^-_G$.

Hall's classical theorem on matchings in bipartite graphs asserts that $G$ has a matching
of~$X$ into~$Y$ if and only if $d^+_G(X') \; \ge \; |X'|$ for all $\emptyset \subset X' \subseteq X$.
The existence of a matching trivially implies $d^+_G(X') \; \ge \; |X'|$ for all
$\emptyset \subset X' \subseteq X$. Therefore, the interesting part of Hall's
theorem can be formulated as follows~:
\begin{equation}
{\rm If} \quad d^+_G(X') \; \ge \; |X'| \quad \forall \quad \emptyset \subset X' \subseteq X, \quad
{\rm then} \quad m^-_G(X) \; \ge \; 1.
\end{equation}
Let $Y'$ be a set disjoint from $X$ and $Y$ with $|Y'| = |X| = n$, and let $b : X \to Y'$
be a bijection. Next, define the bipartite graph $G' = (X,Y';E')$ by letting $E'$ be the
family of all pairs $(x,b(x))$ with $x \in X$, so that $G'$ has just $n$ independent edges.
This implies $d^+_{G'}(X') \; = \; |X'|$ for all $\emptyset \subset X' \subseteq X$
and $m^-_{G'}(X) \; = \; 1$. We can then reformulate the interesting part of Hall's
theorem as follows:
\begin{equation}
{\rm If} \quad d^+_G(X') \; \ge \; d^+_{G'}(X') \quad \forall \quad \emptyset \subset X' \subseteq X, \quad
{\rm then} \quad m^-_G(X) \; \ge \; m^-_{G'}(X).
\end{equation}
This inspired Triesch~\cite{T} to conjecture that for {\it arbitrary} mutually disjoint finite vertex sets
$X$, $Y$, $Y'$ and for {\it arbitrary} bipartite graphs $G = (X,Y;E)$, $G' = (X,Y';E')$ sharing the
vertex set~$X$ the following implication holds:
\begin{equation}
{\rm If} \quad d^+_G(X') \; \ge \; d^+_{G'}(X') \quad \forall \quad \emptyset \subset X' \subseteq X, \quad
{\rm then} \quad m^-_G(X) \; \ge \; m^-_{G'}(X).
\end{equation}

One purpose of this paper is to prove this conjecture for all graphs with sufficiently many edges
by deriving an explicit monotonic formula counting matchings in bipartite graphs.
If $n = 1$ and $X = \{1\}$, then it is evident that
\begin{equation}
m^-_G(\{1\}) \; = \; d^+_G(\{1\}),
\end{equation}
and this identity implies the conjectured monotonicity immediately. If $n = 2$ and $X = \{1,2\}$,
then we prove the formula
\begin{equation}
m^-_G(\{1,2\}) \; = \; \left(d^+_G(\{1\})-1\right)\left(d^+_G(\{2\})-1\right)+\left(d^+_G(\{1,2\})-1\right)
\end{equation}
implying the monotonicity easily. For $n = 3$ and $X = \{1,2,3\}$, we get
\begin{eqnarray}
m^-_G(\{1,2,3\})
&=& \left(d^+_G(\{1\})-2\right)\left(d^+_G(\{2\})-2\right)\left(d^+_G(\{3\})-2\right) \nonumber\\
&&  +\left(d^+_G(\{1,2\})-2\right)\left(d^+_G(\{3\})-2\right) \nonumber\\
&&  +\left(d^+_G(\{1,3\})-2\right)\left(d^+_G(\{2\})-2\right) \nonumber\\
&&  +\left(d^+_G(\{2,3\})-2\right)\left(d^+_G(\{1\})-2\right) \nonumber\\
&&  +2\left(d^+_G(\{1,2,3\})-2\right),
\end{eqnarray}
and for $n = 4$ and $X = \{1,2,3,4\}$, our formula reads
\begin{eqnarray}
m^-_G(\{1,2,3,4\})
&=& \left(d^+_G(\{1\})-3\right)\left(d^+_G(\{2\})-3\right)\left(d^+_G(\{3\})-3\right)\left(d^+_G(\{4\})-3\right) \nonumber\\
&& +\left(d^+_G(\{1,2\})-3\right)\left(d^+_G(\{3\})-3\right)\left(d^+_G(\{4\})-3\right) \nonumber\\
&& +\left(d^+_G(\{1,3\})-3\right)\left(d^+_G(\{2\})-3\right)\left(d^+_G(\{4\})-3\right) \nonumber\\
&& +\left(d^+_G(\{1,4\})-3\right)\left(d^+_G(\{2\})-3\right)\left(d^+_G(\{3\})-3\right) \nonumber\\
&& +\left(d^+_G(\{2,3\})-3\right)\left(d^+_G(\{1\})-3\right)\left(d^+_G(\{4\})-3\right) \nonumber\\
&& +\left(d^+_G(\{2,4\})-3\right)\left(d^+_G(\{1\})-3\right)\left(d^+_G(\{3\})-3\right) \nonumber\\
&& +\left(d^+_G(\{3,4\})-3\right)\left(d^+_G(\{1\})-3\right)\left(d^+_G(\{2\})-3\right) \nonumber\\
&&  +\left(d^+_G(\{1,2\})-3\right)\left(d^+_G(\{3,4\})-3\right) \nonumber\\
&&  +\left(d^+_G(\{1,3\})-3\right)\left(d^+_G(\{2,4\})-3\right) \nonumber\\
&&  +\left(d^+_G(\{1,4\})-3\right)\left(d^+_G(\{2,3\})-3\right) \nonumber\\
&&  +2\left(d^+_G(\{1,2,3\})-3\right)\left(d^+_G(\{4\})-3\right) \nonumber\\
&&  +2\left(d^+_G(\{1,2,4\})-3\right)\left(d^+_G(\{3\})-3\right) \nonumber\\
&&  +2\left(d^+_G(\{1,3,4\})-3\right)\left(d^+_G(\{2\})-3\right) \nonumber\\
&&  +2\left(d^+_G(\{2,3,4\})-3\right)\left(d^+_G(\{1\})-3\right) \nonumber\\
&&  +6\left(d^+_G(\{1,2,3,4\})-3\right).
\end{eqnarray}
For general $X = \{1,2,3,\dots,n\}$, we prove the following new formula.

\begin{thm} We have
\begin{equation}
m^-_G(X) \; = \; \sum_{k=1}^n \, \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k
                 \left(|B_i|-1\right)! \left(d^+_G(B_i)-n+1\right), \label{eq:d+}
\end{equation}
where the sum is over all partitions of~$X$ into $k$ nonempty blocks $B_1$,\dots,$B_k$
($\uplus$ denotes disjoint union).
\end{thm}

This theorem implies immediately that $m^-_G(X)$ depends monotonically on the numbers
$d^+_G(X')$, $\emptyset \subset X' \subseteq X$, if $d^+_G(X') \ge n-1$
for every $\emptyset \subset X' \subseteq X$. For usual graphs, this
condition is satisfied as soon as the degree $d^+_G(x)$ is at least
$n-1$ for every vertex $x \in X$. In other words, if $G = (X,Y;E)$
and $G' = (X,Y';E')$ are bipartite graphs such that $d^+_{G'}(x) \ge n-1$
for every $x \in X$ and $d^+_G(X') \ge d^+_{G'}(X')$ for all
$\emptyset \subset X' \subseteq X$, then our formula implies
$m^-_G(X) \ge m^-_{G'}(X)$. Therefore, it proves the conjecture
imagined by Triesch as soon as $d^+_{G'}(x) \ge n-1$ for every $x \in X$.
On the other hand, this conjecture follows from Hall's theorem if $d^+_{G'}(x) \le 1$
for every $x \in X$. But of course, some cases of the conjecture remain open between
those extreme situations where $G'$ has few or many edges.

For every $\emptyset \subset X' \subseteq X$, we have introduced $d^+_G(X')$
as the number of vertices $y \in Y$ which are related to at least one vertex
in~$X'$ by an edge of~$G$. In an analogous way, we define $d^-_G(X')$
as the number of vertices $y \in Y$ which are related to every vertex
in~$X'$ by an edge of~$G$, and we prove that the integral-valued
set function $d^-_G : 2^X \setminus \emptyset \to \mathbb{Z}$
also determines~$G$ up to a permutation of the vertices of~$Y$.
More precisely, we prove the formulae
\begin{eqnarray}
d^-_G(X') &=& \sum_{X'' \subseteq X'} (-1)^{|X''|-1} d^+_G(X''), \\
d^+_G(X') &=& \sum_{X'' \subseteq X'} (-1)^{|X''|-1} d^-_G(X''),
\end{eqnarray}
by studying linear transformations between the set functions~$d^-_G$, $d^+_G$
and another set function~$x_G$. These considerations of linear algebra for set
functions will be explained in Section~2.

In order to go beyond those results, however, linear algebra is not
sufficient, and we need the {\it algebra of set functions}. A comprehensive
introduction to this algebraic tool explaining, in particular, the basic product
theorem can be found in the preceding article~\cite{L5} (for other applications
of set functions, see~\cite{L1,L2,L3,L4}).
In Section~3, we make use of this product theorem as well as of the linear
algebra explained in Section~2, in order to count matchings in bipartite graphs.
In particular, we prove the following formulae~:
\begin{eqnarray}
m^-_G(X) &=& \sum_{k=1}^n (-1)^{n-k} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! d^-_G(B_i), \\
d^-_G(X) &=& \sum_{k=1}^n (-1)^{n-k} \frac{(k-1)!}{(n-1)!} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k m^-_G(B_i).
\end{eqnarray}
We still introduce one more set function $m^+_G$ and we show how the algebra
of set functions allows us to prove easily lots of relations between all
those set functions.

Identity~(\ref{eq:d+}) of the preceding theorem, however, cannot be proved in this way,
because the ``local'' factors $\left(d^+_G(B_i)-n+1\right)$ contain the ``global'' parameter $n = |X|$.
Therefore, Section~4 is devoted to a general ``global'' duality theory for the enumeration of matchings
in bipartite graphs, which follows from a still more general duality theory for the enumeration of functions.
We have explained this theory in the preceding article~\cite{L5}. With the help of this ``global'' duality,
we finally get a short and surprising proof of our formula~(\ref{eq:d+}).

In Section~5, devoted to Rook Theory (see~\cite{BCHR}), we show that by means of the duality theory
several results related to~\cite{L4} can be proved, which generalize works by Chung and Graham~\cite{CG},
Chow and Gessel~\cite{C}, Joni, Rota and Zeilberger~\cite{JR}, as well as several articles on Laguerre
polynomials by Askey, Gasper, Ismail, Koornwinder, Even, Gillis, Foata, Zeilberger, Godsil, Jackson,
de Sainte-Catherine and Viennot~\cite{AG, AI, AIK, EG, FZ, Go1, Go2, J, SV, V}.



\section{Bipartite Graphs as Set Functions}

Let $X$ be a fixed finite set of vertices, $n = |X|$. We are interested in bipartite graphs
$G = (X,Y;E)$, $E \subseteq X \times Y$, where the second finite vertex set $Y$ is considered
to be variable.

Let $X'$ be an arbitrary nonempty subset of~$X$, $\emptyset \subset X' \subseteq X$.
Let $x_G(X')$ denote the number of vertices $y \in Y$ for which $(x,y) \in E$ if
and only if $x \in X'$, that is, the number of $y \in Y$ for which $\Gamma_G(y) = X'$,
where $\Gamma_G(y)$ is the set of neighbours of~$y$. In other words, $x_G(X')$ counts
the number of vertices of~$Y$ which are joint by an edge of~$G$ to every vertex of~$X'$
and to no vertex of $X \setminus X'$. The following lemma is evident.

\begin{lemma}
The bipartite graph $G  = (X,Y;E)$ is determined up to isomorphism by the set function
$x_G : 2^X \setminus \emptyset \to \mathbb{Z}$. Here, $x_G$ determines a usual bipartite
graph if and only if $x_G(X') \ge 0$ for all $\emptyset \subset X' \subseteq X$. \qed
\end{lemma}

Moreover, let $d^-_G(X')$, $\emptyset \subset X' \subseteq X$, denote the number of vertices of~$Y$
which are joint by an edge of~$G$ to every vertex of~$X'$ and possibly to some vertices of $X \setminus X'$~:
\begin{equation}
d^-_G : 2^X \setminus \emptyset \to \mathbb{Z}, \qquad d^-_G(X') \; = \; \sum_{X' \subseteq X''} x_G(X'')
\qquad \forall \, \emptyset \subset X' \subseteq X.
\end{equation}
The set function $d^+_G$ already mentioned in the introduction and the set function $x_G$
are related as follows~:
\begin{equation}
d^+_G : 2^X \setminus \emptyset \to \mathbb{Z}, \qquad d^+_G(X') \; = \; \sum_{X' \cap X'' \ne \emptyset} x_G(X'') \; = \; |\Gamma_G(X')|
\qquad \forall \, \emptyset \subset X' \subseteq X.
\end{equation}

We can consider $x_G$, $d^-_G$ and $d^+_G$ as vectors with $2^{|X|} - 1 = 2^n - 1$ components,
and we want to study the linear transformations between them. Let $[X' \subseteq X'']$ denote
a square matrix with $2^n-1$ rows and $2^n-1$ columns indexed by the nonempty subsets of~$X$.
More precisely, if a row is indexed by~$X'$ and a column is indexed by~$X''$, then the
coefficient corresponding to this row and column equals~$1$ if $X' \subseteq X''$
and~$0$ otherwise. Similarly, for the matrix $[X' \subseteq X''](-1)^{|X'' \setminus X'|}$,
the coefficient corresponding to a row indexed by~$X'$ and a column indexed by~$X''$
equals $(-1)^{|X'' \setminus X'|}$ if $X' \subseteq X''$ and~$0$ otherwise.
The coefficients of the matrix $[X' \cap X'' \ne \emptyset]$ are all $0$ or $1$.
The coefficient corresponding to a row indexed by~$X'$ and a column indexed by~$X''$
is~$1$ if and only if $X'$ and $X''$ have a nonempty intersection. The matrices
$-[X' \cup X'' = X](-1)^{|X' \cap X''|}$ and $-[X' \supseteq X''](-1)^{|X''|}$
are defined in the same way. They allow us to formulate the following theorem.

\begin{thm}
The linear transformations between the vectors $x_G$, $d^-_G$ and $d^+_G$ are described by
the matrices already introduced. More precisely, we have for all $\emptyset \subset X' \subseteq X$~:
\begin{eqnarray}
d^-_G(X') &=& [X' \subseteq X''] \cdot x_G(X''), \label{d-x} \\
  x_G(X') &=& [X' \subseteq X''](-1)^{|X'' \setminus X'|} \cdot d^-_G(X''), \label{xd-} \\
d^+_G(X') &=& [X' \cap X'' \ne \emptyset] \cdot x_G(X''), \label{d+x} \\
  x_G(X') &=& -[X' \cup X'' = X](-1)^{|X' \cap X''|} \cdot d^+_G(X''), \label{xd+} \\
d^-_G(X') &=& -[X' \supseteq X''](-1)^{|X''|} \cdot d^+_G(X''), \label{d-d+} \\
d^+_G(X') &=& -[X' \supseteq X''](-1)^{|X''|} \cdot d^-_G(X''). \label{d+d-}
\end{eqnarray}
\end{thm}

\begin{proof}
First of all, equations~(\ref{d-x}) and~(\ref{d+x}) are immediately equivalent to our definitions
of the vectors $d^-_G$ and $d^+_G$. In order to prove~(\ref{xd-}), we have to show that the matrices
$[X' \subseteq X'']$ and $[X' \subseteq X''](-1)^{|X'' \setminus X'|}$ are inverse of each other.
This is a direct consequence of the inclusion-exclusion principle~:
\begin{equation}
[X' \subseteq X^*] \cdot [X^* \subseteq X''](-1)^{|X'' \setminus X^*|} \; = \; [X' = X''],
\end{equation}
where $[X' = X'']$ is the identity matrix; in order to find a coefficient
of a product of two matrices, one has to calculate a scalar product, which
corresponds to a sum over $X^*$ for fixed $X'$ and $X''$ in the preceding
equation. In the same way, we can calculate~:
\begin{eqnarray}
-[X' \cap X^* \ne \emptyset] \cdot [X^* \cup X'' = X](-1)^{|X^* \cap X''|} &=&  \nonumber \\
+[X' \cap X^* = \emptyset] \cdot [X^* \cup X'' = X](-1)^{|X^* \cap X''|} &=& [X' = X''],
\end{eqnarray}
which proves our formula~(\ref{xd+}). The matrix $-[X' \supseteq X''](-1)^{|X''|}$ is inverse of itself~:
\begin{equation}
[X' \supseteq X^*] \cdot [X^* \supseteq X''](-1)^{|X^*|+|X''|} \; = \; [X' = X''],
\end{equation}
which shows the equivalence of~(\ref{d-d+}) and~(\ref{d+d-}). Therefore, it remains to deduce~(\ref{d-d+})~:
\begin{eqnarray}
d^-_G(X') &=& [X' \subseteq X^*] \cdot x_G(X^*) \nonumber \\
          &=& -[X' \subseteq X^*] \cdot [X^* \cup X'' = X] (-1)^{|X^* \cap X''|} \cdot d^+_G(X'') \nonumber \\
          &=& -[X' \supseteq X''](-1)^{|X''|} \cdot d^+_G(X'').
\end{eqnarray}
\end{proof}

\begin{example}
For $n = 3$ and $X = \{1,2,3\}$, we use shorthand notations of type $d^-_{13} = d^-_G(\{1,3\})$.
Then our formulae read as follows.
\begin{eqnarray}
d^-_{1}   &=& x_{1}+x_{12}+x_{13}+x_{123}, \\
d^-_{12}  &=& x_{12}+x_{123}, \\
d^-_{123} &=& x_{123}; \\
\nonumber \\
x_{1}     &=& d^-_{1}-d^-_{12}-d^-_{13}+d^-_{123}, \\
x_{12}    &=& d^-_{12}-d^-_{123}, \\
x_{123}   &=& d^-_{123}; \\
\nonumber \\
d^+_{1}   &=& x_{1}+x_{12}+x_{13}+x_{123}, \\
d^+_{12}  &=& x_{1}+x_{2}+x_{12}+x_{13}+x_{23}+x_{123}, \\
d^+_{123} &=& x_{1}+x_{2}+x_{3}+x_{12}+x_{13}+x_{23}+x_{123}; \\
\nonumber \\
x_{1}     &=& -d^+_{23}+d^+_{123} \\
x_{12}    &=& -d^+_{3}+d^+_{13}+d^+_{23}-d^+_{123} \\
x_{123}   &=& d^+_{1}+d^+_{2}+d^+_{3}-d^+_{12}-d^+_{13}-d^+_{23}+d^+_{123}; \\
\nonumber \\
d^-_{1}   &=& d^+_{1}, \\
d^-_{12}  &=& d^+_{1}+d^+_{2}-d^+_{12}, \\
d^-_{123} &=& d^+_{1}+d^+_{2}+d^+_{3}-d^+_{12}-d^+_{13}-d^+_{23}+d^+_{123}; \\
\nonumber \\
d^+_{1}   &=& d^-_{1}, \\
d^+_{12}  &=& d^-_{1}+d^-_{2}-d^-_{12}, \\
d^+_{123} &=& d^-_{1}+d^-_{2}+d^-_{3}-d^-_{12}-d^-_{13}-d^-_{23}+d^-_{123}.
\end{eqnarray}
\end{example}

\bigskip

\noindent
The following corollaries are immediate consequences of the preceding theorem.

\bigskip

\begin{coro}
The bipartite graph $G  = (X,Y;E)$ is determined up to a permutation
of the vertices of~$Y$ by the set function
$d^-_G : 2^X \setminus \emptyset \to \mathbb{Z}$. Here $d^-_G$ determines a
bipartite graph if and only if
\begin{equation}
x_G(X') \; = \; \sum_{X' \subseteq X''} (-1)^{|X'' \setminus X'|} \cdot d^-_G(X'') \; \ge \; 0 \qquad \forall \, \emptyset \subset X' \subseteq X.
\end{equation}
\qed
\end{coro}

\begin{coro}
The bipartite graph $G  = (X,Y;E)$ is determined up to a permutation
of the vertices of~$Y$ by the set function
$d^+_G : 2^X \setminus \emptyset \to \mathbb{Z}$. Here $d^+_G$ determines a
bipartite graph if and only if
\begin{equation}
x_G(X') \; = \; \sum_{X' \cup X'' = X} -(-1)^{|X' \cap X''|} \cdot d^+_G(X'') \; \ge \; 0 \qquad \forall \, \emptyset \subset X' \subseteq X.
\end{equation}
\qed
\end{coro}

\begin{coro}
For
\begin{equation}
D^-_G(\chi) \; := \; \sum_{\emptyset \subset X' \subseteq X} d^-_G(X') \cdot \chi^{X'} \qquad \hbox{and} \qquad
D^+_G(\chi) \; := \; \sum_{\emptyset \subset X' \subseteq X} d^+_G(X') \cdot \chi^{X'}
\end{equation}
we have
\begin{equation}
D^+_G(\chi) \; = \; -D^-_G(-\chi) \cdot \exp(\mathcal{X}) \qquad \hbox{and} \qquad
D^-_G(\chi) \; = \; -D^+_G(-\chi) \cdot \exp(\mathcal{X}).
\end{equation}
\qed
\end{coro}



\section{Matchings in Bipartite Graphs}

Now our purpose is to calculate the set function $m^-_G : 2^X \setminus \emptyset \to \mathbb{Z}$
defined in the introduction. To this end, we define
\begin{equation}
M^-_G(\chi) \; := \; \sum_{\emptyset \subset X' \subseteq X} m^-_G(X') \cdot \chi^{X'}.
\end{equation}
The product theorem of~\cite{L5} implies the following lemma.

\begin{lemma}
Let
\begin{equation}
\mathcal{X'} \; = \; \sum_{x \in X'}  \chi^{\{x\}}.
\end{equation}
Then
\begin{eqnarray}
1 + M^-_G(\chi)
&=& \prod_{\emptyset \subset X' \subseteq X} (1+\mathcal{X'})^{x_G(X')} \label{produit} \\
&=& \prod_{\emptyset \subset X' \subseteq X} \, \sum_{k=0}^{|X'|} x_G(X')^{\underline{k}} \cdot \frac{\mathcal{X'}^k}{k!}, \label{m-}
\end{eqnarray}
where $x_G(X')^{\underline{k}} = x_G(X') (x_G(X')-1) (x_G(X')-2) \cdots (x_G(X')-k+1)$ by definition.
\end{lemma}

\begin{proof} For every $\emptyset \subset X' \subseteq X$ we have
\begin{equation}
(1+\mathcal{X'})^{x_G(X')}
\; = \; \sum_{k=0}^{|X'|} \binom{x_G(X')}{k} \mathcal{X'}^k \\
\; = \; \sum_{k=0}^{|X'|} x_G(X')^{\underline{k}} \cdot \frac{\mathcal{X'}^k}{k!}.
\end{equation}
\end{proof}

\medskip

\noindent
We next calculate the logarithm of the product displayed in~(\ref{produit})~:
\begin{eqnarray}
\log \left( 1 + M^-_G(\chi) \right)
&=& \sum_{\emptyset \subset X' \subseteq X} x_G(X') \cdot \log \left( 1+\mathcal{X'} \right) \nonumber \\
&=& \sum_{\emptyset \subset X' \subseteq X} (-1)^{|X'|-1} (|X'|-1)! \cdot d^-_G(X') \cdot \chi^{X'}.
\end{eqnarray}

\noindent
We can now define
\begin{equation}
D^-_G!(\chi) \; := \; \sum_{\emptyset \subset X' \subseteq X} (|X'|-1)! \cdot d^-_G(X') \cdot \chi^{X'}
\end{equation}
and immediately get the following theorem.

\begin{thm} We have the identities~:
\begin{eqnarray}
1 + M^-_G(\chi) &=& \exp \left( -D^-_G!(-\chi) \right), \label{M-D-} \\
\log \left( 1 + M^-_G(\chi) \right) &=& -D^-_G!(-\chi), \\
\partial^x M^-_G(\chi) &=& - \left( 1 + M^-_G(\chi) \right) \cdot \partial^x D^-_G!(-\chi) \qquad \forall \, x \in X, \\
\partial M^-_G(\chi) &=& - \left( 1 + M^-_G(\chi) \right) \cdot \partial D^-_G!(-\chi).
\end{eqnarray}
\qed
\end{thm}

\begin{coro} We have
\begin{eqnarray}
m^-_G(X) &=& \sum_{k=1}^n (-1)^{n-k} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! d^-_G(B_i), \label{m-d-} \\
d^-_G(X) &=& \sum_{k=1}^n (-1)^{n-k} \frac{(k-1)!}{(n-1)!} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k m^-_G(B_i). \label{d-m-}
\end{eqnarray}
In particular, the bipartite graph $G  = (X,Y;E)$ is determined up to a permutation
of the vertices of~$Y$ by the set function $m^-_G : 2^X \setminus \emptyset \to \mathbb{Z}$. \qed
\end{coro}

\begin{example}
For $n = 3$ and $X = \{1,2,3\}$, we use shorthand notations of type $m^-_{13} = m^-_G(\{1,3\})$.
Then our formulae read as follows. 
\begin{eqnarray}
m^-_{1}   &=& d^-_{1}, \\
m^-_{12}  &=& d^-_{1}d^-_{2}-d^-_{12}, \\
m^-_{123} &=& d^-_{1}d^-_{2}d^-_{3}-d^-_{12}d^-_{3}-d^-_{13}d^-_{2}-d^-_{23}d^-_{1}+2d^-_{123}; \\
\nonumber \\
d^-_{1}   &=& m^-_{1}, \\
d^-_{12}  &=& m^-_{1}m^-_{2}-m^-_{12}, \\
d^-_{123} &=& \hbox{$m^-_{1}m^-_{2}m^-_{3}-\frac{1}{2}m^-_{12}m^-_{3}-\frac{1}{2}m^-_{13}m^-_{2}-\frac{1}{2}m^-_{23}m^-_{1}+\frac{1}{2}m^-_{123}.$}
\end{eqnarray}
\end{example}

\begin{remark}
With our method of set functions, it is possible to study most questions for matchings in bipartite graphs
also for permanents of matrices. It seems that the only result known along those lines (without using
set functions) is the analogue of formula~(\ref{m-d-}); see~\cite{M}.
\end{remark}

\medskip

Our preceding formula~(\ref{m-d-}) implies, in particular, that $m^-_G(X)$ is a polynomial
in the variables~$d^-_G(X')$, $\emptyset \subset X' \subseteq X$. Moreover, $m^-_G(X)$ is
also a polynomial in the variables~$d^+_G(X')$, $\emptyset \subset X' \subseteq X$,
as well as in the variables~$x_G(X')$, $\emptyset \subset X' \subseteq X$. This
can be seen easily if we replace the variables~$d^-_G(X')$ using
formulae~(\ref{d-d+}) or~(\ref{d-x}). In particular, everything
is well defined for negative integers~$x_G(X')$, $\emptyset \subset X' \subseteq X$
(more generally, $x_G(X') \in A$ for an arbitrary commutative ring~$A$ with~$1$
is sufficient). We can give the following traditional combinatorial interpretation
for this situation.

We can consider~$X$ as a set of persons and to every subset~$X' \subseteq X$ associate a job
for which all the persons of the subset~$X'$ are qualified, and nobody else (the qualification of
a person~$x \in X$ for a job $y \in Y$ is indicated by an edge~$(x,y) \in E$ in our bipartite graph~$G = (X,Y;E)$).
This job has the \emph{usual} capacity~$x_G(X')$, which means that at most $x_G(X')$ persons can work there. More precisely,
if $k$ persons want to work there, then this is possible in $x_G(X')^{\underline{k}} = x_G(X') (x_G(X')-1) (x_G(X')-2) \cdots (x_G(X')-k+1)$
different ways, that is, every person taking the job reduces its capacity by~$1$. In this way, $m^-_G(X)$ counts the number of possibilities
to find jobs for everybody, as reflected by our formula~(\ref{m-}) of the preceding lemma.

This combinatorial interpretation motivates us to study the following slight modification.
We continue to consider~$X$ as a set of persons and with every subset~$X' \subseteq X$ to associate
a job for which all the persons from~$X'$ are qualified, and nobody else. But we give this
job the \emph{alternative} capacity~$x_G(X')$, which means that if $k$ persons want to work there,
then this is possible in $x_G(X')^{\overline{k}} = x_G(X') (x_G(X')+1) (x_G(X')+2) \cdots (x_G(X')+k-1)$
different ways, that is, every person taking the job increases its capacity by~$1$. (This is completely
analogous to the problem of choosing $k$ elements among $x_G(X')$ ones~: if repetitions are not
allowed, then the number of different ways is $x_G(X')^{\underline{k}}/k!$ ; if they are
allowed, then we have $x_G(X')^{\overline{k}}/k!$ different choices.) If we work with
those alternative capacities, then we denote the number of possibilities to find jobs
for everybody by~$m^+_G(X)$. If $X' \subseteq X$, then the number of ways
to find a job (with alternative capacities) for every person $x \in X'$
(for which this person is qualified) is~$m^+_G(X')$.
This defines a new set function $m^+_G : 2^X \setminus \emptyset \to \mathbb{Z}$ we want to study~:
\begin{equation}
M^+_G(\chi) \; := \; \sum_{\emptyset \subset X' \subseteq X} m^+_G(X') \cdot \chi^{X'}.
\end{equation}
Our preceding discussion proves an analogue of our preceding lemma.

\begin{lemma}
We have
\begin{eqnarray}
1 + M^+_G(\chi)
&=&   \prod_{\emptyset \subset X' \subseteq X} \, \sum_{k=0}^{|X'|} x_G(X')^{\overline{k}} \cdot \frac{\mathcal{X'}^k}{k!} \\
&=&   \prod_{\emptyset \subset X' \subseteq X} (1-\mathcal{X'})^{-x_G(X')},  \label{m+}
\end{eqnarray}
where $x_G(X')^{\overline{k}} = x_G(X') (x_G(X')+1) (x_G(X')+2) \cdots (x_G(X')+k-1)$ by definition.
\end{lemma}

\begin{proof} For every $\emptyset \subset X' \subseteq X$ we have
\begin{equation}
\sum_{k=0}^{|X'|} x_G(X')^{\overline{k}} \cdot \frac{\mathcal{X'}^k}{k!}
\; = \; \sum_{k=0}^{|X'|} (-1)^k \left(-x_G(X')\right)^{\underline{k}} \cdot \frac{\mathcal{X'}^k}{k!}
\; = \; \sum_{k=0}^{|X'|} \binom{-x_G(X')}{k} (-\mathcal{X'})^k \\
\; = \; (1-\mathcal{X'})^{-x_G(X')}.
\end{equation}
\end{proof}

Identities~(\ref{m-}) and~(\ref{m+}) show that by choosing negative integers for $x_G(X')$, $\emptyset \subset X' \subseteq X$,
we get $(-1)^n m^+_G(X)$ with $n = |X|$ instead of $m^-_G(X)$. This proves the following theorem.

\begin{thm} We have
\begin{equation}
1 + M^+_G(\chi) \; = \; \left(1 + M^-_G(-\chi)\right)^{-1}.
\end{equation}
\qed
\end{thm}

\begin{coro} We have
\begin{eqnarray}
m^+_G(X) &=& \sum_{k=1}^n (-1)^{n-k} k! \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k m^-_G(B_i), \label{m+m-} \\
m^-_G(X) &=& \sum_{k=1}^n (-1)^{n-k} k! \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k m^+_G(B_i). \label{m-m+}
\end{eqnarray}
In particular, the bipartite graph $G  = (X,Y;E)$ is determined up to isomorphism by the set function $m^+_G : 2^X \setminus \emptyset \to \mathbb{Z}$.
Moreover, the identity $\left(1 + M^+_G(-\chi)\right)\left(1 + M^-_G(\chi)\right) = 1$ means
\begin{equation}
(-1)^{|X|}m^+_G(X) + m^-_G(X) + \sum_{\emptyset \subset X' \subset X} (-1)^{|X'|}m^+_G(X') \cdot m^-_G(X \setminus X') \; = \; 0.
\end{equation}
\qed
\end{coro}

\medskip

\noindent
The two preceding theorems imply the following results.

\begin{thm} We have the identities~:
\begin{eqnarray}
1 + M^+_G(\chi) &=& \exp \left( D^-_G!(\chi) \right), \\
\log \left( 1 + M^+_G(\chi) \right) &=& D^-_G!(\chi), \\
\partial^x M^+_G(\chi) &=& \left( 1 + M^+_G(\chi) \right) \cdot \partial^x D^-_G!(\chi) \qquad \forall \, x \in X, \\
\partial M^+_G(\chi) &=& \left( 1 + M^+_G(\chi) \right) \cdot \partial D^-_G!(\chi).
\end{eqnarray}
\qed
\end{thm}

\begin{coro} We have
\begin{eqnarray}
m^+_G(X) &=& \sum_{k=1}^n \, \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! d^-_G(B_i), \label{m+d-} \\
d^-_G(X) &=& \sum_{k=1}^n (-1)^{k-1} \frac{(k-1)!}{(n-1)!} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k m^+_G(B_i). \label{d-m+}
\end{eqnarray}
Therefore, $m^+_G(X)$ depends monotonically on the numbers $d^-_G(X')$, $\emptyset \subset X' \subseteq X$, if $d^-_G(X') \ge 0$ for every
$\emptyset \subset X' \subseteq X$, i.e.~in particular if $x_G(X') \ge 0$ for every $\emptyset \subset X' \subseteq X$, which are
the defining inequalities for bipartite graphs. \qed
\end{coro}

\begin{remark}
It is possible to interpret formula~(\ref{m+d-}) in such a way, that we sum over all permutations of~$X$
the number of functions from~$X$ to $Y$ which respect the edges~$E$ of our bipartite graph and which
are constant on the cycles of the permutations. This provides a link to P\'olya's Counting
Theory.
\end{remark}

\begin{example}
For $n = 3$ and $X = \{1,2,3\}$, we use shorthand notations of type $m^+_{13} = m^+_G(\{1,3\})$.
Then our formulae read as follows. 
\begin{eqnarray}
m^+_{1}   &=& d^-_{1}, \\
m^+_{12}  &=& d^-_{1}d^-_{2}+d^-_{12}, \\
m^+_{123} &=& d^-_{1}d^-_{2}d^-_{3}+d^-_{12}d^-_{3}+d^-_{13}d^-_{2}+d^-_{23}d^-_{1}+2d^-_{123}; \\
\nonumber \\
d^-_{1}   &=& m^+_{1}, \\
d^-_{12}  &=& -m^+_{1}m^+_{2}+m^+_{12}, \\
d^-_{123} &=& \hbox{$m^+_{1}m^+_{2}m^+_{3}-\frac{1}{2}m^+_{12}m^+_{3}-\frac{1}{2}m^+_{13}m^+_{2}-\frac{1}{2}m^+_{23}m^+_{1}+\frac{1}{2}m^+_{123}.$}
\end{eqnarray}
\end{example}

\bigskip

The end of this section is not necessary for understanding the rest of the article~: it is written only for readers
interested in exponential generating functions. If we want to work with them instead of working with set functions,
we must use an infinite set~$X$. Moreover, everything must depend just on the cardinalities of the finite
subsets of~$X$ and not on those subsets themselves. For our bipartite graph $G = (X,Y;E)$, this means that
every vertex of~$Y$ is either joint to all vertices of~$X$ or to just one vertex of~$X$~: if a
vertex $y \in Y$ is joint to~$x \in X$ and to~$X'$ with $\emptyset \subset X' \subset X \setminus \{x\}$,
then, by permuting the elements of~$X \setminus \{x\}$, we see that there must be infinitely many vertices~$y \in Y$
each of which is joint to~$x$ and to a subset~$X''$ of~$X \setminus \{x\}$ in bijection with~$X'$. Therefore, $x$ would
get an infinite degree, which makes it impossible to count matchings.

In other words, we can suppose that there is one $y \in Y$ of capacity~$a$ joint to every~$x \in X$,
and for every vertex $x \in X$, there is a vertex in~$Y$ of capacity~$i$ joint only to~$x$.
Let us denote this infinite bipartite graph by~$G(a,i)$. It is evident that
$1+M^-_{G(1,0)}(\chi) = 1+\mathcal{X}$ and $1+M^-_{G(0,1)}(\chi) = \exp(\mathcal{X})$.
Therefore the product theorem implies the following proposition.

\begin{proposition} We have
\begin{eqnarray}
1+M^-_{G(a,i)}(\chi) &=& (1+\mathcal{X})^a \exp(i \cdot \mathcal{X}), \\
1+M^+_{G(a,i)}(\chi) &=& 1+M^-_{G(-a,-i)}(-\chi) \; = \; (1-\mathcal{X})^{-a} \exp(i \cdot \mathcal{X}).
\end{eqnarray}
\qed
\end{proposition}

\begin{example}
Let $G_n(2)$ be the number of connected $2$-regular bipartite multigraphs (i.e.~multiple edges are allowed)
$G = (\{1,2,\dots,n\},\{1,2,\dots,n\};E)$ with fixed marked vertices, then $G_1(2) = 1$ and $G_n(2) = n!(n-1)!/2$
for $n > 1$~: if we choose every second edge of such a cycle, then we get an arbitrary first permutation,
and a second permutation which is cyclic with respect to the first one.

Let $H_n(2)$ be the number of arbitrary $2$-regular bipartite multigraphs $G = (X,Y;E)$ with fixed marked vertex sets
of cardinality~$n$. By permuting the vertices of~$Y$, we get
\begin{equation}
\frac{H_n(2)}{n!} \; = \; \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \frac{G_{|B_i|}(2)}{|B_i|!} \; = \; m^+_{G(1/2,1/2)}(X).
\end{equation}
Therefore our preceding proposition implies (see Stanley's book \cite{S}, 3.15.1.d)~:
\begin{equation}
\sum_{n=0}^{\infty} H_n(2) \frac{\mathcal{X}^n}{(n!)^2} \; = \; (1-\mathcal{X})^{-1/2} \exp(\mathcal{X}/2).
\end{equation}
\end{example}



\section{Duality for Matchings in Bipartite Graphs}

Let us come back to our study of bipartite graphs $G = (X,Y;E)$ with the help of set functions.
Until now, we have never used $x_G(\emptyset)$, that is the number of vertices $y \in Y$ which
are joint to no $x \in X$ at all. If we want to construct the bipartite complement of~$G$, however,
or just a partial complement $C_{X'}(G)$ with $\emptyset \subset X' \subseteq X$, then $x_G(\emptyset)$
will become indispensable. In fact, for every $\emptyset \subseteq X'' \subseteq X$, we have the identity
\begin{equation}
x_{C_{X'}(G)}(X'') \; = \; x_G(X' \triangle X''), \qquad \hbox{and in particular} \qquad x_{\overline{G}}(X'') \; = \; x_G(X \setminus X'').
\end{equation}
Therefore it is convenient to choose $x_G(\emptyset)$ in a useful way, namely in such a way
that we get normality in the sense of the duality theory of~\cite{L5}.

\medskip

\begin{proposition}
The set of injective functions from $X$ to $Y$, that is the set of functions
with usual capacities $x_G(X')$, $\emptyset \subseteq X' \subseteq X$
is normal if and only if
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \; = \; |X|-1.
\end{equation}
\end{proposition}

\begin{proof}
Since the edges of our bipartite graph have no importance at all for the question of normality
(see~\cite{L5}), it is sufficient to consider the situation with a single job of capacity
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X').
\end{equation}
If everybody except one person has already chosen this job, then the last person has
\begin{equation}
\left( \sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \right) - \left( |X|-1 \right)
\end{equation}
choices to take this job, and the situation is called \emph{normal} if and only if
the last number is equal to~$0$.
\end{proof}

\medskip

\noindent
The same kind of argument proves the analogous result for alternative capacities.

\medskip

\begin{proposition}
The set of functions from $X$ to $Y$ with alternative capacities $x_G(X')$,
$\emptyset \subseteq X' \subseteq X$ is normal if and only if
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \; = \; 1-|X|.
\end{equation}
\qed
\end{proposition}

\bigskip

\noindent
These propositions, together with the duality theory of~\cite{L5}, imply the following theorems.

\begin{thm} (Duality Theorem for Usual Matchings in Bipartite Graphs)
If $x_G(\emptyset)$ is chosen in such a way that
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \; = \; |X|-1,
\end{equation}
then
\begin{eqnarray}
m^-_{C_x(G)}(X) &=& -m^-_G(X) \qquad \forall \, x \in X, \\
m^-_{C_{X'}(G)}(X) &=& (-1)^{|X'|}m^-_G(X) \qquad \forall \, X' \subseteq X, \\
m^-_{\overline{G}}(X) &=& (-1)^{|X|}m^-_G(X).
\end{eqnarray}
\qed
\end{thm}

\begin{thm} (Duality Theorem for Alternative Matchings in Bipartite Graphs)
If $x_G(\emptyset)$ is chosen in such a way that
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \; = \; 1-|X|,
\end{equation}
then
\begin{eqnarray}
m^+_{C_x(G)}(X) &=& -m^+_G(X) \qquad \forall \, x \in X, \\
m^+_{C_{X'}(G)}(X) &=& (-1)^{|X'|}m^+_G(X) \qquad \forall \, X' \subseteq X, \\
m^+_{\overline{G}}(X) &=& (-1)^{|X|}m^+_G(X).
\end{eqnarray}
\qed
\end{thm}

\bigskip

\noindent
It is evident that for every $\emptyset \subset X' \subseteq X$ we have
\begin{equation}
d^-_G(X') + d^+_{\overline{G}}(X') \; = \; d^-_{\overline{G}}(X') + d^+_G(X') \; = \; \sum_{\emptyset \subseteq X'' \subseteq X} x_G(X'').
\end{equation}
This identity allows us to prove the following two corollaries easily.

\medskip

\begin{coro} We have
\begin{equation}
m^+_G(X) \; = \;  \sum_{k=1}^n (-1)^{n-k} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! \left( d^+_G(B_i)+n-1 \right). \label{m+d+}
\end{equation}
\end{coro}

\begin{proof}
If we are in a \emph{normal} situation, then the preceding duality theorem for alternative matchings in bipartite graphs and our formula~(\ref{m+d-}) imply
\begin{eqnarray}
m^+_G(X)
&=& (-1)^{|X|} m^+_{\overline{G}}(X) \nonumber \\
&=& (-1)^{|X|} \sum_{k=1}^{|X|} \, \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! d^-_{\overline{G}}(B_i) \nonumber \\
&=& \sum_{k=1}^{|X|} (-1)^{|X|} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! \left( 1-|X|-d^+_G(B_i) \right).
\end{eqnarray}
\end{proof}

\medskip

\noindent
In the same way, we obtain the formula already mentioned in the introduction.

\begin{coro} We have
\begin{equation}
m^-_G(X) \; = \;  \sum_{k=1}^n \, \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! \left( d^+_G(B_i)-n+1 \right). \label{m-d+}
\end{equation}
Therefore, $m^-_G(X)$ depends monotonically on the numbers $d^+_G(X')$, $\emptyset \subset X' \subseteq X$, if $d^+_G(X') \ge n-1$ for every
$\emptyset \subset X' \subseteq X$, i.e.~in particular if $x_G(X') \ge 0$ for all $\emptyset \subset X' \subseteq X$ and
$d^+_G(x) = d^-_G(x) = d_G(x) \ge n-1$ for all $x \in X$, where the last condition is satisfied as soon as $x_G(X') \in \mathbb{Z}$
and $x_G(X') > 0$ for all $\emptyset \subset X' \subseteq X$.
\end{coro}

\begin{proof}
If we are in a \emph{normal} situation, then the preceding duality theorem for usual matchings in bipartite graphs and our formula~(\ref{m-d-}) imply
\begin{eqnarray}
m^-_G(X)
&=& (-1)^{|X|} m^-_{\overline{G}}(X) \nonumber \\
&=& (-1)^{|X|} \sum_{k=1}^{|X|} (-1)^{|X|-k} \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! d^-_{\overline{G}}(B_i) \nonumber \\
&=& \sum_{k=1}^{|X|} (-1)^k \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k \left(|B_i|-1\right)! \left( |X|-1-d^+_G(B_i) \right).
\end{eqnarray}
\end{proof}

\medskip

The conjecture imagined by Triesch~\cite{T} does not follow in all cases from the preceding corollary because it affirms that
$m^-_G(X)$ depends monotonically on the numbers $d^+_G(X')$, $\emptyset \subset X' \subseteq X$, as soon as $x_G(X') \in \mathbb{Z}$
and $x_G(X') \ge 0$ for all $\emptyset \subset X' \subseteq X$. If we consider bipartite graphs as integer points in the cone
defined by the inequalities $x_G(X') \ge 0$ for all $\emptyset \subset X' \subseteq X$, then we have proved the conjecture
for all points which are not on the boundary of the cone.

It is possible to prove the monotonicity directly, if just one component of the vector $d^+_G$ is increased by~$1$.
Ideas of this kind can also be used in order to give a more elementary (but less instructive) proof of our formula~(\ref{m-d+}).
If we increase $d^+_G(X')$, $\emptyset \subset X' \subseteq X$, by~$1$, then all $x_G(X'')$, $\emptyset \subset X'' \subseteq X$,
with $X'' \cup X' = X$ are modified~: they decrease by~$1$ if $|X'' \cap X'| \equiv 0 \pmod 2$ and they increase by~$1$ if
$|X'' \cap X'| \equiv 1 \pmod 2$; see our formula~(\ref{xd+}). In particular, in order to accomplish this transformation
without violating the conditions $x_G(X'') \in \mathbb{Z}$ and $x_G(X'') \ge 0$ for all $\emptyset \subset X'' \subseteq X$,
we need the conditions $d_G(x) \ge 2^{|X'|-1}$ for all $x \in X \setminus X'$ and $d_G(x) \ge 2^{|X'|-2}$ for all $x \in X'$
if $|X'| > 1$.

If we increase only components of $d^+_G$ of the same parity (the parity of the component $d^+_G(X')$ is by definition
the parity of $|X'|$), then the monotonicity follows directly from what has already been said. If we increase just
two arbitrary components, then it can also be shown directly.

The right hand side of~(\ref{m-d+}) looks perfect if $d^+_G(X') \ge n-1$ for every $\emptyset \subset X' \subseteq X$,
but far from perfect if some of the numbers $d^+_G(X')-n+1$ are negative, since a lot of cancellation occurs.
A natural way to avoid it consists in replacing $d^+_G(X')-n+1$ by $\left(d^+_G(X')-n+1\right)_+$,
where $(x)_+ := \max(x,0)$ denotes the maximum of $x$ and $0$ for any real number $x$.
More precisely, we conjecture that an identity of the following type holds~:
\begin{equation}
m^-_G(X) \; = \; \sum_{k=1}^n \, \sum_{B_1 \uplus \dots \uplus B_k = X} \, \prod_{i=1}^k
                 f(B_i) \left(d^+_G(B_i)-n+1\right)_+,
\end{equation}
where $f(X')$, $\emptyset \subset X' \subseteq X$, depends monotonically on the numbers
$d^+_G(X'')$, $\emptyset \subset X'' \subseteq X'$. In other words, formula (\ref{eq:d+}) 
can be replaced by a monotonic interpolation with multidimensional spline functions.

Our conjectured formula would imply, as a corollary, that any bipartite graph $G = (X,Y;E)$
with $|X| = |Y| = n$ has at most $(n-1)!$ perfect matchings (matchings covering every vertex
of~$G$), if for any partition of~$X$ into two nonempty blocks~$X'$ and $X''$ we have
$d^+_G(X') \le n-1$ or $d^+_G(X'') \le n-1$. This corollary can indeed be proved
by induction on~$n$. Moreover, if $G$ really has those $(n-1)!$ perfect matchings,
then either there exists an $x \in X$ such that $d^+_G(X \setminus \{x\}) = n-1$
or G is isomorphic to $C_6$, a circle with $6$ vertices.

\bigskip

\noindent
Let us conclude this section with an easy example for exponential generating functions.

\medskip

\begin{example}
Let $D(n)$ be the number of fixed point free permutations of the set $\{1,2,\dots,n\} = X$
(or, equivalently, the number of possibilities to put $n$ letters into $n$ envelopes
in such a way, that no letter will be in the correct envelope). In other words,
$D(n)$ is the number of perfect matchings of the complete bipartite graph $K_{n,n}$
from which one perfect matching has been removed. This situation can be normalized
with an additional vertex $y \in Y$ of weight~$-1$, which is not joined to any vertex of~$X$,
that is $x_G(\emptyset) = -1$. Now our duality theorem for usual matchings in bipartite graphs
proves $D(n) = (-1)^n m^-_{G(-1,1)}(X)$, and the last proposition of Section~3 implies
\begin{equation}
\sum_{n=0}^{\infty} D(n) \cdot \frac{\mathcal{X}^n}{n!} \; = \; 1 + M^-_{G(-1,1)}(-\chi) \; = \; (1-\mathcal{X})^{-1} \exp(-\mathcal{X}),
\end{equation}
one of the most classical results of enumerative combinatorics, which can be found in~\cite{A} or \cite{S}, for example.
\end{example}


\section{Rook Theory}

Let $G = (X,Y;E)$ be a simple bipartite graph with $|X| = n$. We denote by $G+z$ the graph obtained from $G$
by adding to $Y$ one vertex with the usual capacity~$z$ which is joined to every $x \in X$ by an edge.
Let $G_a$ be a graph for which $x_G(\emptyset)$ has been chosen in such a way that
\begin{equation}
\sum_{\emptyset \subseteq X' \subseteq X} x_G(X') \; = \; |X|+a.
\end{equation}
Then our duality theorem for usual matchings in bipartite graphs implies the following lemma.

\begin{lemma} We have
\begin{equation}
m^-_{\overline{G_a}+z}(X) \; = \; (-1)^{|X|} m^-_{G_a-z-a-1} (X).
\end{equation}
\qed
\end{lemma}

\medskip

\noindent
We can define the \emph{factorial rook polynomial} easily by
\begin{equation}
\rho ! (G_a,z) \; : = \; m^-_{G_a+z} (X) \; = \; \sum_{r=0}^n p(G_a,r) z^{\underline{n-r}},
\end{equation}
where $z^{\underline{n-r}} = z(z-1)(z-2)\cdots(z-n+r+1)$ and where $p(G_a,r)$ denotes the number of $r$-matchings of~$G_a$,
$p(G_a,0) := 1$. An $r$-matching is a set of $r$ independent (i.e., mutually non adjacent) edges. Traditionally, one considers
$X$ and $Y$ as rows and columns of a checkerboard so that $r$-matchings become placements of non-attacking rooks; see~\cite{BCHR}
for an introduction to rook theory. It is classical (see the book~\cite{R} by Riordan, chapter~7.7), that the numbers $p(\overline{G_a},r)$
are determined by the numbers $p(G_a,r)$. No simple relation between them, however, has been found yet. Inspired by the definition of
Chung and Graham's cover polynomial~\cite{CG}, Chow (and Gessel)~\cite{C} have introduced our factorial rook polynomial, which
proved already to be useful in the work of Foata and Sch\"utzenberger~\cite{FS} on Ferrers relations, because in that case,
it factorizes naturally (see~\cite{GJW} and Stanley's book~\cite{S}, theorem 2.4.1). Our preceding lemma implies the
following duality relation for the factorial rook polynomial, which was imagined by Chow (and Gessel)~\cite{C}
in the case $a = 0$.

\begin{proposition} We have
\begin{equation}
\rho ! (\overline{G_a},z) \; = \; (-1)^n \rho ! (G_a,-z-a-1).
\end{equation}
\qed
\end{proposition}

\bigskip

The \emph{classical rook polynomial} can be found, for example, in Godsil's book~\cite{Go1}, chapter 1.3.
We will define it as follows~:
\begin{equation}
\rho (G_a,t) \; : = \; \sum_{r=0}^n (-1)^r p(G_a,r) t^{n-r}.
\end{equation}
Let $G_a[X']$ be the simple bipartite graph formed by the vertices of~$X'$ ($\emptyset \subset X' \subseteq X$),
the edges of~$G$ incident with them and the second endpoints (in~$Y$) of those edges. Our main theorem of Section~3,
i.e.~identity~(\ref{M-D-}), implies the following lemma.

\begin{lemma} We have
\begin{eqnarray}
1 + \sum_{\emptyset \subset X' \subseteq X} \rho (G_a[X'],t) \cdot \chi^{X'}
&=& \exp \left( t \cdot \mathcal{X} \right) \cdot \left( 1 + M^-_{G_a}(-\chi) \right) \\
&=& \exp \left( t \cdot \mathcal{X} - D^-_{G_a}!(\chi) \right).
\end{eqnarray}
\qed
\end{lemma}

\medskip

\noindent
It allows us to prove the the last theorem of this article.

\begin{thm} We have
\begin{eqnarray}
\int_{0}^{\infty} t^{z+a} \cdot e^{-t} \rho (G_a,t) dt
&=& (-1)^n \rho ! (G_a,-z-a-1) \cdot \Gamma (z+a+1) \\
&=& \rho ! (\overline{G_a},z) \cdot \Gamma (z+a+1).
\end{eqnarray}
In particular, if $a = -1$, then $\rho ! (\overline{G_{-1}},z) \cdot \Gamma (z) = (-1)^n \rho ! (G_{-1},-z) \cdot \Gamma (z)$
is the Mellin transform of $e^{-t} \rho (G_{-1},t)$.
\end{thm}

\begin{proof}
The first identity can be proved easily with the algebra of set functions~:
\begin{eqnarray}
&&\int_{0}^{\infty} t^{z+a} e^{-t} \cdot \exp \left( t \cdot \mathcal{X} \right) \cdot \left( 1 + M^-_{G_a}(-\chi) \right) \cdot dt  \nonumber \\
&&= \; \left( 1 + M^-_{G_a}(-\chi) \right) \int_{0}^{\infty} t^{z+a} \exp \left( -t(1-\mathcal{X}) \right) dt  \nonumber \\
&&= \; \left( 1 + M^-_{G_a}(-\chi) \right) \int_{0}^{\infty} \left( \frac{s}{1-\mathcal{X}} \right)^{z+a} \exp \left( -s \right) \frac{ds}{1-\mathcal{X}}  \nonumber \\
&&= \; \left( 1 + M^-_{G_a}(-\chi) \right) \left( 1-\mathcal{X} \right)^{-z-a-1} \int_{0}^{\infty} s^{z+a} e^{-s} ds  \nonumber \\
&&= \; \left( 1 + M^-_{G_a-z-a-1}(-\chi) \right) \cdot \Gamma (z+a+1).
\end{eqnarray}
The second identity is nothing else but the preceding proposition.
\end{proof}

\medskip

The preceding theorem is closely related to results of~\cite{L4}. Its special case~$a = z = 0$ was found by Joni, Rota and Zeilberger~\cite{JR},
since $\rho ! (\overline{G_0},0) = m^-_{\overline{G_0}} (X)$ counts the number of perfect matchings of~$\overline{G_0}$. This result makes it possible
to interpret combinatorially integrals of products of generalized Laguerre polynomials; see~\cite{AG, AI, AIK, EG, FZ, Go1, Go2, J, SV, V}. Following
Godsil~\cite{Go1}, we can define Laguerre polynomials as rook polynomials of complete bipartite graphs~$K_{n,m} := (X,Y;X \times Y)$ with
$|X| = n$ and $|Y| = m$. More precisely, for every $a \in \mathbb{N}$ we define
\begin{equation}
Le^{(a)}_n(t) \; := \; \rho (K_{n,n+a},t).
\end{equation}
Since $\rho ( K_{n,n+a} \uplus K_{m+a,m} , t ) = t^a \cdot Le^{(a)}_n(t) \cdot Le^{(a)}_m(t)$, the identity of Joni, Rota and Zeilberger implies that
\begin{equation}
\rho ! ( \overline{ K_{n,n+a} \uplus K_{m+a,m} } , 0 ) \; = \; \int_{0}^{\infty} Le^{(a)}_n(t) \cdot Le^{(a)}_m(t) \cdot t^a e^{-t} dt
\end{equation}
(see~\cite{Go2}). This proves in particular the orthogonality of our polynomials $Le^{(a)}_n(t)$ with respect to $t^a e^{-t} dt$.
Therefore our definition of Laguerre polynomials corresponds to the classical definition. Our normalization, however, is chosen
in such a way that the first coefficient (i.e.~the coefficient of~$t^n$) is equal to~$1$.

\bigskip

\noindent
\emph{Acknowledgements:} \quad
I should like to thank most cordially Eberhard Triesch, who has familiarized me with his
very beautiful conjecture, which inspired all results of this article and many others.
I am also grateful to D.~Foata and G.~Han for all their help and encouragement.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}

\bibitem{A}
M.~Aigner,
"Combinatorial Theory",
Springer-Verlag, Heidelberg, 1979.

\bibitem{AG}
R.~Askey and G.~Gasper,
"Convolution structures for Laguerre polynomials",
\emph{J. Analyse Math.} \textbf{31} (1977), 48-68.

\bibitem{AI}
R.~Askey and M.~Ismail,
"Permutation problems and special functions",
\emph{Canad.~J.~Math.} \textbf{28} (1976), 853-874.

\bibitem{AIK}
R.~Askey, M.~Ismail and T.~Koornwinder,
"Weighted permutation problems and Laguerre Polynomials",
\emph{J.~Combin.~Theory Ser.~A} \textbf{25} (1978), 277-287.

\bibitem{BCHR}
F.~Butler, M.~Can, J.~Haglund and J.B.~Remmel,
"Rook Theory Notes".

\bibitem{C}
T.~Chow,
"A short proof of the rook reciprocity theorem",
\emph{Electronic J.~Combin.} \textbf{3} (1996), R10.

\bibitem{CG}
F.R.K.~Chung and R.L.~Graham,
"On the cover polynomial of a digraph",
\emph{J.~Combin.~Theory Ser.~B} \textbf{65} (1995), 273-290.

\bibitem{EG}
S.~Even and J.~Gillis,
"Derangements and Laguerre polynomials",
\emph{Math.~Proc.~Camb. Phil.~Soc.} \textbf{79} (1976), 135-143.

\bibitem{FS}
D.~Foata and M.-P.~Sch\"utzenberger,
"On the rook polynomials of Ferrers relations",
in~: Combinatorial Theory and its Applications, vol.~2
(P.~Erd\"os, A.~Renyi and V.~T.~S\'os, eds.),
\emph{Colloq.~Math.~Soc.~J\'anos Bolyai} \textbf{4} (1970),
North-Holland, Amsterdam, 431-436.

\bibitem{FZ}
D.~Foata and D.~Zeilberger,
"Laguerre polynomials, weighted derangements and positivity",
\emph{SIAM J.~Disc.~Math.} \textbf{1} (1988), 425-433.

\bibitem{Go1}
C.D.~Godsil,
"Algebraic Combinatorics",
Chapman \& Hall, 1993.

\bibitem{Go2}
C.D.~Godsil,
"Hermite polynomials and a duality relation for matchings polynomials",
\emph{Combinatorica} \textbf{1} (1981), 257-262.

\bibitem{GJW}
J.R.~Goldman, J.T.~Joichi and D.E.~White,
"Rook theory I, Rook equivalence of Ferrers boards",
\emph{Proc.~Amer.~Math.~Soc.} \textbf{52} (1975), 485-492.

\bibitem{J}
D.~M.~Jackson,
"Laguerre polynomials and derangements",
\emph{Math.~Proc.~Camb.~Phil.~Soc.} \textbf{80} (1976), 213-214.

\bibitem{JR}
S.A.~Joni and G.-C.~Rota,
"A vector space analog of permutations with restricted position",
\emph{J.~Combinatorial Theory, Series A} \textbf{29} (1980), 59-73.

\bibitem{L1}
B.~Lass,
"Matching polynomials and duality",
\emph{Combinatorica} \textbf{24} (2004), 427-440.

\bibitem{L2}
B.~Lass,
"Orientations acycliques et le polyn\^ome chromatique",
\emph{European J.~Combin.} \textbf{22} (2001), 1101-1123.

\bibitem{L3}
B.~Lass,
"The $N$-dimensional matching polynomial",
\emph{Geom.~Funct.~Anal.} \textbf{15} (2005), 453-475.

\bibitem{L4}
B.~Lass,
"Variations sur le th\`eme $E+\overline E=XY$",
\emph{Adv.~in Appl.~Math.} \textbf{29} (2002), 215--242.

\bibitem{L5}
B.~Lass,
"The algebra of set functions I~: The product theorem and duality",
preprint.

\bibitem{M}
H.~Minc,
"Permanents",
Addison-Wesley, 1978.

\bibitem{R}
J.~Riordan,
"An Introduction to Combinatorial Analysis",
Wiley, New York, 1958.

\bibitem{SV}
M.~de Sainte-Catherine and G.~Viennot,
"Combinatorial interpretation of integrals of products of
Hermite, Laguerre and Tchebycheff polynomials",
in~: Polyn\^omes orthogonaux et applications
(C.~Brezinski, et al., eds.), Bar-le-Duc, 1984,
\emph{Lecture Notes in Mathematics} \textbf{1175} (1985),
Springer-Verlag, Berlin, 120-128.

\bibitem{S}
R.P.~Stanley,
"Enumerative Combinatorics", Volume 1,
Cambridge University Press, Cambridge, 1997.

\bibitem{T}
E.~Triesch,
"Conjectures on the uniqueness of Hamiltonian cycles and the number of perfect matchings",
\emph{Proceedings of the Fourth Prague Combinatorial Workshop (Martin Klazar, editor)}
KAM Series No.~97-339 (1997), 42-46.

\bibitem{V} G.~Viennot,
"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.

\end{thebibliography}
\end{document}