#####
Séminaire Lotharingien de Combinatoire, B34f (1995), 21pp.

# Robert Stoyan and Volker Strehl

# Enumeration of Hamiltonian Circuits in Rectangular Grids

**Abstract.**
We describe an algorithm for computing the number *h(m,n)* of
Hamiltonian circuits in a *m*-by-*n* rectangular grid graph.
For any fixed *m*, the set of Hamiltonian circuits on such graphs
(for varying *n*) can be identified via an appropriate coding
with the words of a certain regular language *L(m)*.
We show how to systematically construct a finite automaton *A(m)*
recognizing *L(m)*. This allows, in principle,
the computation of the (rational) generating function *h(m)(z)* of
*L(m)*.
We exhibit a bijection between the states of *A(m)* and the words
of length *m+1* of the familiar Motzkin language. This yields an
upper bound on the degree of the denominator polynomial of *h(m)(z)*,
hence of the order of the linear recurrence satisfied by the coefficients
*h(m,n)* for fixed *m*.
The method described here has been implemented. Numerical data resulting
from this implementation are presented at the end of this article.

The following versions are available: