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