Automatic Generation of Generating Functions for Counting
the Number of Spanning Trees for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.ps
.tex
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger)
Written: April 2, 2011.
Paul Raff
did a beautiful, and very clever, job in teaching the
computer how to derive generating functions for the number of spanning trees in grid graphs
for fixed width, and more generally any graph G times the path graphs, continuing the pioneering work
of Frans Faase and others.
Here we adopt a much more naive approach, and succeed in doing more general things!
Since we know a priori that the generating functions are rational, and at least
in principle, we can rigorously find upper bounds for the degrees of the denominators,
Shalosh uses the matrix-tree theorem to compute the first whatever number of terms in the
sequence, and then it "fits" a rational function that fits the data.
Important:
This article is accompanied by the Maple package
KamaEtzim, that automatically computes generating functions for
counting the number of spanning trees in infinite families of graphs of fixed width (see the article).
Sample Input and Output for the Maple package KamaEtzim
-
If you want to see explicit expressions (as rational functions in z) for
the formal power series whose coefficient of zn in its Maclaurin
expansion (with respect to z) would give you the number of spanning trees of the m by n grid
graph (the Cartesian product of a path of m vertices and a path of length n)
for m=2 to m=6, the
the input
gives the output.
-
If you want to see explicit expressions (as rational functions of z) for
the formal power series whose coefficient of zn in its Maclaurin
expansion (with respect to z) would give you the number of spanning trees of the m by n cylinder
graph (the Cartesian product of a cycle of m vertices and a path of length n)
for m=2 to m=6, the
the input
gives the output.
If you want to see explicit expressions (as rational functions in z) for
the formal power series whose coefficient of zn in its Maclaurin
expansion (with respect to z) would give you the number of spanning trees of the 7 by n grid
graph (the Cartesian product of a path of 7 vertices and a path of length n)
the input
gives the output.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page