Automatic Generation of Generating Functions for Enumerating Matchings
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 29, 2011.
Frans Faase and Per Hakan Lundow devised algorithms
for automatically generating generating functions for the number of matchings in grid graphs
of fixed widths, and more generally any graph G times the path graphs.
Here we generalize this even further, and make it all accessible to the whole world
by supplying the Maple source code, by which anyone can derive (rigorously!) any
generating function that he or she (or it) desires.
Important:
This article is accompanied by the Maple package
KamaShidukhim, that automatically computes generating functions for
counting the number of spanning trees in infinite families of graphs of fixed widths (see the article).
Sample Input and Output for the Maple package KamaShidukhim
-
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
PERFECT matchings 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=10, 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
PERFECT matchings of the m by n cylinder
graph (the Cartesian product of a path of m vertices and a path of length n)
for m=2 to m=10, 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
PERFECT matchings of the m by n Chess King
graph (the m by n Chessboard where every square is incident to the (usually)
eight neighboring squares)
for m=2 to m=8 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
ALL matchings 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=9, 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
ALL matchings of the m by n cylinder
graph (the Cartesian product of a path of m vertices and a path of length n)
for m=2 to m=9, 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
ALL matchings of the m by n Chess King
graph (the m by n Chessboard where every square is incident to the (usually)
eight neighboring squares)
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
PERFECT matchings of the Cartesian product of a graph G with the path graph Pn
of ALL connected graphs with ≤ 7 vertices (of course it suffices to
pick one representative from each symmetry class)
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
ALL matchings of the Cartesian product of a graph G with the path graph Pn
of ALL connected graphs with ≤ 6 vertices (of course it suffices to
pick one representative from each symmetry class)
the
input
gives the
output.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page