%etzim.tex: Automatic Generation of  Generating Functions for 
%The Number of Spanning Trees
%for Grid Graphs (and more general creatures) of fixed (but arbitrary!) width 
%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 the Number of Spanning Trees}
\centerline
{
for Grid Graphs (and Much More General Creatures) of Fixed (but arbitrary!) Width
}
\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 2, 2011.
\bigskip
{\bf Very Important}: This article comments on the Maple package \hfill\break
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/KamaEtzim}. 
Some 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/etzim.html} \quad .

\bigskip

This work extends the beautiful work of Paul Raff[1], that in turn,
extended pioneering
work of Frans Faase[2] and others (see the references of [1]) about counting spanning trees in grid graphs and more general creatures. 
However, {\it our} approach is very naive (in a good way!) .

For a graph $G$, let $T(G)$ be its number of spanning trees.
Also let $P_n$ be the path-graph of length $n$:
$1-2- \dots - n$.
It is fairly easy to see that for a fixed $m$, the generating function
$$
F_m(z)=\sum_{n=0}^{\infty} T(\P_n \times \P_m) z^n 
$$
is a {\it rational function} of $z$. 
The Maple package {\tt KamaEtzim} automatically
computes $F_m(z)$ for {\it any} inputted numeric $m$.
(See procedure {\tt GFrect(m,z)} of  {\tt KamaEtzim}).
In fact, we  do something much more general.
For {\it any} graph $G$,  {\tt KamaEtzim} can (explicitly!) compute
$$
F_G(z)=\sum_{n=0}^{\infty} T(\P_n \times G) z^n \quad .
$$
(See procedure {\tt GFG(G,m,z,K)} in {\tt KamaEtzim}) .

In fact we  do something {\it even} 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}
$$
mimic the graph $G$ (for $i=0, \dots , n-1$), and in addition the
edges between \vfill\eject
$$
{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 KamaEtzim} can (explicitly!) compute the rational function
(of $z$):
$$
F_{G,C}(z)=\sum_{n=0} T(M_n(G,C)) z^n \quad .
$$
(See procedure {\tt FGt(G,C,m,z,K)} in {\tt KamaEtzim}.)

{\bf The output}:
For the (already known [1][2]) 
generating functions for the
number of spanning trees on grid graphs $P_m \times P_n$
(resp. cylinder graphs $C_m \times P_n$)
for $2 \leq m \leq 6$ see: \hfill\break
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oKamaEtzim1}
\hfill\break
(resp. {\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oKamaEtzim2}) .

For the {\it brand-new}
generating function, for the
number of spanning trees on grid graphs $P_7 \times P_n$
see:
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oKamaEtzim3}  .

{\bf The Method}

The computer first constructs the graphs $M_n(G,C)$ for sufficiently many $n$, then
finds the adjacency matrices, and then uses the matrix tree theorem (see wikipedia or any combinatorics textbook)
to compute the sequence, and finally guesses a rational function describing this sequence.
{\it Voil\`a tout!}


{\bf References}

1. Paul Raff, {\it Spanning Trees in Grid Graphs}, {\tt arXiv:0809.2551v1 }, 15 Sept. 2008. 
(Note that some of the entries in the table
of p. 9 are in error (they correctly represent something else, namely the cylinder graphs).

2. Frans Faase, {\it On the number of specific spanning subgraphs $g \times p_n$}, Ars Combinatorica {\bf 49} (1998), 129-154.

\quad




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

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

\end






