
%shidukhim.tex: 
%Automatic Generation of Generating Functions for 
%Enumerating Matchings

%a Plain TeX file by Shalosh B. Ekhad, and Doron Zeilberger
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Automatic Generation of Generating Functions for 
Enumerating Matchings
}
\rm
\bigskip
\centerline
{By {\it Shalosh B. EKHAD}  and {\it Doron ZEILBERGER}}

\bigskip
Exclusively published in the {\bf Personal Journal of Shalosh B. Ekhad and Doron Zeilberger}: {\tt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html} .
Written: April 29, 2011.
\bigskip
{\bf Very Important}: This article comments on the Maple package \hfill\break
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/KamaShidukhim}. 
Lots of sample input and output can be gotten from the ``front'' of this article: \hfill\break
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/shidukhim.html} \quad .

\bigskip

Per Hakan Lundow ({\tt http://www.theophys.kth.se/\Tilde phl/Text/1factors2.ps.gz}),
and Frans Faase ({\tt http://www.iwriteiam.nl/Cpaper.zip})
devised efficient algorithms for computing {\it generating functions} for  the number of
{\it matchings} (both perfect, and not-necessarily perfect) in
{\it grid graphs},
namely the Cartesian product $\P_n \times \P_m$ where $\P_n$ is the path of length $n$,
and more generally, $\P_n \times G$, for {\it any} graph $G$.
In this article we first reproduce, in Maple, what they did, and further generalize their work to more general infinite families of graphs.

For a graph $G$, let  $S_1(G)$ and $S_2(G)$ be, respectively, the number of {\it perfect matchings}  
(sets of pairwise vertex-disjoint edges that cover all the vertices)
and (all) {\it matchings} (sets of pairwise vertex-disjoint edges).
It is well-known and
fairly easy to see (and is implied by the algorithm outlined below, that is implemented in {\tt KamaShidukhim}) 
that for any {\it fixed} positive integer $m$, the generating functions
$$
\sum_{n=0}^{\infty} S_1(\P_m \times \P_n)  z^n  \quad , \quad \sum_{n=0}^{\infty} S_2(\P_m \times \P_n)  z^n 
$$
are both {\it rational functions} of  $z$. 
The Maple package {\tt KamaShidukhim} automatically
computes these rational function for {\it any} inputted numeric $m$.
See procedure {\tt GFrect(m,z)} and {\tt GFrectMD(m,z)} of  {\tt KamaShidukhim}. 

In fact we  do something much more general.
For {\it any} graph $G$,  {\tt KamaShidukhim} can (explicitly!) compute the rational generating functions
$$
\sum_{n=0}^{\infty} S_1(\P_n \times G) z^n \quad , \quad  \sum_{n=0}^{\infty} S_2(\P_n \times G) z^n \quad .
$$
See procedures {\tt GFG(G,m,z)} and {\tt GFGmd(G,m,z)} of  {\tt KamaShidukhim}. 

In fact we  do something {\it enormously} more general!
For {\it any} graph $G$, on $m$ vertices, and for {\it any} bipartite $(m,m)$ graph $C$, let
$M_n(G,C)$ be the graph on $mn$ vertices where  the edges among
$$
{1+im \, , \, 2+im \, , \,  ... \, , \, m+im} \quad, 
$$
for $i=0, \dots , n-1$, mimic the graph $G$ , and in addition the
edges between 
$$
{1+im \, , \, 2+im \, , \,  ... \, , \,  m+im}
$$
and
$$
{1+(i+1)m \, , \, 2+(i+1)m \, , \,  ... \, , \, m+(i+1)m}
$$
($0 \leq i < n-1$)
mimic the edges of $C$, given as a set of (up to $m^2$) ordered pairs $\{[\alpha,\beta]\}$.
$[\alpha,\beta] \in C$ means that
there is an edge between vertex $\alpha +im$ and vertex $\beta+(i+1)m$ for $0\leq i<n-1$.
Note that when $C$ is the monogamy bipartite 
graph $\{[1,1], \dots, [m,m] \}$,
where Mr $i$ is connected to Mrs $i$ (but no cheating!), then 
$M_n(G,C)$ reduces to the Cartesian product $G \times \P_n$.

{\tt KamaShidukhim} can (explicitly!) compute the rational functions
(of $z$):
$$
\sum_{n=0} S_1(M_n(G,C)) z^n \quad , \quad \sum_{n=0} S_2(M_n(G,C)) z^n .
$$
See procedures {\tt GFt(G,C,z)} and {\tt GFtMD(G,C,z)} of {\tt KamaShidukhim}.


{\bf The Method}

Of course we use the {\it transfer matrix method}.
When we do match-making, we must first 
decide whom amongst those vertices of $M_n(G,C)$ that live on the ``bottom floor'' (``oldest'') copy of $G$ would be connected to each other
and how to decide on these intra-generational pairings within that oldest level.
Having done that, we have to decide how to match the remaining,
not-yet-matched  vertices (still at the oldest copy of $G$)
to some vertices on the next floor, via the edges of the copy of $C$.
After these inter-generational matchings have been decided,
some vertices of the second copy of $G$ (on the second level of $M_n(G,C)$) are already committed to a relationship to
someone older, but the remaining vertices can be either matched to someone in their
own generation, or to someone in the next-generation-copy of $G$, etc. 
So it naturally emerges that we have to tackle the more
general problem of enumerating ``chopped matchings'' where the bottm
copy of $G$ has a prescribed subset of vertices that are already matched.

As the computer does it,
it dynamically builds the {\it set of states}, a certain collection of
subsets of $\{1, \dots, m\}$, and there is
no need for human ``ingenuity'' to ``figure-out'' 
the set of states.

The computer also, {\it all by itself}, figures out the
{\it transition matrix}. 
Then it {\it automatically} sets-up the system of linear equations (involving the variable $z$), and {\it automatically} 
goes on to solve them, {\it symbolically!},
and at the end gets the desired quantity, the generating function of the state $\{1, ...., m\}$.
Please see the Maple source-code of procedures {\tt GFt(G,C,z)} and {\tt GFtMD(G,C,z)} 
of {\tt KamaShidukhim} for more details.


\bigskip
\bigskip
\hrule
\bigskip
\bigskip

Shalosh B. Ekhad and Doron Zeilberger,
Department of Mathematics, Hill Center-Busch Campus, Rutgers University, 110 Frelinghuysen Rd,
Piscataway, NJ 08544, USA.

Email: {\tt [c/o zeilberg, zeilberg]@math.rutgers.edu} .

\end



