Counting (and Randomly Generating) Hamiltonian Cycles in Rectangular Grids

By Pablo Blanco and Doron Zeilberger

.pdf    .tex (Plain TeX)

Written: March 2026

      Dedicated to Volker Strehl (born June 23, 1945), great enumerator and dear friend, on his (forthcoming) "perfect fourth power birthday"

We first fully implement, in Maple, the ingenious method of Robert Stoyan and Volker Strehl from 1995 to automatically derive generating functions for the number of Hamiltonian cycles in a grid graph [m]x[n], for a fixed width m, but general length n, and actually compute these generating functions for all m ≤ 10. We also show how to generate a uniformly-at-random such Hamiltonian cycle, and also derive more informative generating functions for other parameters besides the length of the grid graph.

Maple packages

  • Volker.txt, A maple package for computing generating functions enumerating the number of Hamiltonian cycles in grid graphs, and much more

  • WDG.txt, A maple package for generating random directed graphs and for numerating walks and generating random walks in a general directed graph. It uses the Wilf methodology for generating random objects with a recursive structure.

Related Maple package that Inspired this project

  • Kurchan.txt, to create and solve SpellWeaving puzzles, due to Rodolfo Kurchan, that appeared in the New Your Times Sunday magazine between Nov. 24,2025 and Feb. 23, 2026. It also produced this puzzle book.

Sample Input and Output for Volker.txt

  • If you want to see the eight generating functions f_m(z) (of course these are rational functions), for 2 ≤ m ≤ 9, whose coefficient of zn in their Maclaurin expansion is the number of Hamiltonian cycles of the grid graph [m+1]x[n+1], as well as the first 50 terms of each of these sequences
    the input gives the output

    Note that these are also available within the Maple package. The command is GFnzPC(n,z), for n from 2 to 9.

  • If you want to see f10(z)
    the input gives the output

  • If you want to see the four generating functions F_m(z,w) (of course these are rational functions), for 2 ≤ m ≤ 5, whose coefficient of zn in their Maclaurin expansion is the weight-enumerator of the set m by n matrices corresponding to Hamiltonian cycles of the grid graph [m+1]x[n+1], where the weight if the product of w[i]^NumberOfOnesInRow_i for i from 1 to m, as well as the first 50 terms of each of these sequences
    the input gives the output .

  • If you want to see confirmation of procedure RandHP(m,n), to generate a uniformly-at-random Hamiltonian cycle in an m by n grid graph for small (up to 8) m but as large n as you wish, using procedure CheckRandHP(m,n,c,K,K1),
    the input gives the output .

  • If you want to see the asymptotics for the number of Hamiltonian cycles in the grid graph [n]x[m], as n goes to infinity, and m between 3 and 8, as well as asymptotic expressions for the average and variance of the random variable "number of edges in a random Hamiltonian cycle that belong to the left border of the [n]x[m] grid
    the input gives the output .

  • If you want to see the limit, as n goes to infinity, of the correlation coefficient of the random variables "number of edges that belong to the left border" and "number of edges that belong to the right border" over the sample space of all Hamiltonian cycles in in n by m grid (for m between 3 and 7) and the asymptotics is in n. Also the limit of the correlation coefficient between the number of 1s and number of 2s in the associated Stoyan-Strehl 0-1 matrix,
    the input gives the output .

  • If you want to see the exact number of Hamiltonian cycles in the grid graphs P10 x P10, P10 x P100, P10 x P1000, and P10 x P10000,
    the input gives the output .

  • If you want to see lots of picutres of random Hamiltonian cycles (produced by the command RandomHP(m,n), of various sizes, look in

    this directory .

Sample Output for Kurchan.txt

Doron Zeilberger's Home Page

Pablo Blanco's Home Page