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