Untying The Gordian Knot via Experimental Mathematics

By Yukun Yao and Doron Zeilberger

.pdf   .ps   .tex

Written: Dec. 17, 2018. This vesion: Jan. 7, 2019.
[Appeared in "Algorithmic Combinatorics-Enumerative Combinatorics, Special Functions, and Computer Algebra: In honor of Peter Paule's 60th birthday", Springer; edited by Veronika Pillwein and Carsten Schneider]

Dedicated to Peter Paule on his 60th birthday

Peter Paule is one of the pioneers of Symbolic computation and experimental mathematics, and the co-author (with Manuel Kauers) of the bible in our field. This article is dedicated to him with friendship and admiration.

Maple packages

• GFMatrix.txt, a Maple package for automatically computing, both experimentally and rigorously rational generating functions for sequences of determinants of "almost diagonal matrices"

• SpanningTrees.txt, a Maple package for automatically computing rational generating functions for sequences enumerating spanning trees, with applications to joint resistance.

• JointConductance.txt, a Maple package for joint conductance .

Sample Input and Output for GFMatrix.txt

• If you want to see rational generating functions for determinants of sequences of "almost diagonal matrices" with up to 11 non-zero diagonals, for SYMBOLIC matrices the
input file yields the output file
[Warning: very big file!]

• If you want to see rational generating functions for determinants of sequences of "almost diagonal matrices" with up to 11 non-zero diagonals, for random NUMERICAL matrices the
input file yields the output file

Sample Input and Output for SpanningTrees.txt

• If you want to see rational generating functions for enumerating the spanning trees of the graphs GxPn for various G
input file yields the output file

• If you want to see rational generating functions for enumerating the spanning trees of the grid graphs PmxPn for m from 2 to 6
input file yields the output file

Sample Input and Output for JointConductance.txt

• If you want to see the rational generating functions enumerating the sequences enumerating the number of spanning trees in an m by n rectangular grid, for m from 2 to 7

the input file generates the output file.

Note that the generating functions for n ≤ 6 have been previously computed by Paul Raff and Faase, but m=7 seems to be new. Suprisingly, the degree of the denominator is 48, rather than 64 (until m=6 the degree is 2m-1)