Automatic Generation of Generating Functions for Enumerating Spanning Trees

Automatic Generation of Generating Functions for Enumerating Spanning Trees
By Pablo Blanco and Doron Zeilberger
.pdf .tex (LaTeX source file)

Written: June 25, 2025

Using the theoretical basis developed by Yao and Zeilberger, we consider certain graph families whose structure results in a rational generating function for sequences related to spanning tree enumeration. Said families are Powers of Cycles and Powers of Path; later, we briefly discuss Torus graphs and Grid graphs. In each case we know, a priori, that the set of spanning trees of the family of graphs can be described in terms of a finitestate-machine, and hence there is a finite transfer-matrix that guarantees the generating function is rational. Finding this "grammar", and hence the transfer-matrix is very tedious, so a much more efficient approach is to use experimental mathematics. Since computing numerical determinants is so fast, one can use the matrix tree theorem to generate sufficiently many terms, then fit the data to a rational function. The whole procedure can be done rigorously a posteriori.
We also construct generating functions for the quantity "total number of leaves" over all spanning trees, and automatically derive the asymptotics for both number of spanning trees and the sum of the number of leaves, enabling our computer to get the asymptotic for the average number of leaves per vertex in a random spanning tree in each family that always tends to a certain number, which we compute explicitly. This number, that we christen the B-Z constant for the infinite family is always some (often complicated) algebraic number, in contrast to the family of complete graphs where this constant is 1/e (a transcendental number)

Maple package

ExpSP.txt, A maple package for computing generating functions enumerating the number of spanning trees in numerous infinite familes of graphs.

Sample Input and Output for ExpSP.txt

If you want to see the generating functions (that are always rational functions), in n, for the the number of spanning trees of the graphs H_n,r defined in the paper, for 2 ≤ r ≤ 5, as well as generating functions for the "sum of the number of leaves" over all spanning trees (that enables) computing the exact average number of leaves, as well as precise asymptotics
the input gives the output

If you want to see the same as above, but where the asympotic information (including the BZ contant) are in floating-point, rather than often complicated and unreadable algebraic numbers
the input gives the output

If you want to see the generating functions (that are always rational functions), in n, for the the number of spanning trees of the graphs G_n,r defined in the paper, for 2 ≤ r ≤ 5, as well as generating functions for the "sum of the number of leaves" over all spanning trees (that enables) computing the exact average number of leaves, as well as precise asymptotics
the input gives the output

If you want to see the same as above, but where the asympotic information (including the BZ contant) are in floating-point, rather than often complicated and unreadable algebraic numbers
the input gives the output

If you want to see the generating functions (that are always rational functions), in n, for the the number of spanning trees of the r by n rectangular grid, for 2 ≤ r ≤ 4, as well as generating functions for the "sum of the number of leaves" over all spanning trees (that enables) computing the exact average number of leaves, as well as precise asymptotics
the input gives the output

If you want to see the same as above, but where the asympotic information (including the BZ contant) are in floating-point, rather than often complicated and unreadable algebraic numbers
the input gives the output

If you want to see the generating functions (that are always rational functions), in n, for the the number of spanning trees of the r by n rectangular torus, for 3 ≤ r ≤ 6, as well as generating functions for the "sum of the number of leaves" over all spanning trees (that enables) computing the exact average number of leaves, as well as precise asymptotics
the input gives the output
WARNING: The floating version of the BZ constants for the cases r=5 and r=6 were given (erroneusly of course) as 0 (due to the complexity of the algebaric numbers and Maple's round-off errors even with Digits=300). Pleaes ignore them.

If you want to see the same as above, but where the asympotic information (including the BZ contant) are in floating-point, rather than often complicated and unreadable algebraic numbers
the input gives the output

If you want to see estimated statistics about the number of leaves in a random spanning tree of H_n,r for various n and several r
the input gives the output

If you want to see estimated statistics about the number of leaves in a random spanning tree of G_n,r for various n and several r
the input gives the output

If you want to see estimated statistics about the number of leaves in a random labeled tree on n vertices for various n
the input gives the output

If you want to see a comparison of the exact average of the number of leaves in a random spanning trees for our four favorite families,
See here