\documentstyle[11pt]{article} \sloppy \newcommand{\xbar}{\overline{x}} \newlength{\mylength} \newcounter{robifigure} \def\therobifigure{\arabic{robifigure}} \def\caption#1{\refstepcounter{robifigure} \figurename\enspace\therobifigure. #1}%\medskip\par} \def\endrobifigure{} \author{ Robert Stoyan\thanks{rtstoyan@cip.informatik.uni-erlangen.de}\\ Volker Strehl\thanks{strehl@immd1.informatik.uni-erlangen.de}\\ Computer Science Department (Informatik)\\ University of Erlangen-N\"urnberg\\ D-91058 Erlangen, Germany} \date{[ \small Note: this article has been accepted for publication by the\\ {\it Journal of Combinatorial Mathematics and Combinatorial Computing}]} \title{Enumeration of Hamiltonian Circuits in Rectangular Grids} \begin{document} \maketitle \begin{abstract} \noindent We describe an algorithm for computing the number $h_{m,n}$ of Hamiltonian circuits in a rectangular grid graph consisting of $m\times n$ squares. 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 \subset \left(\{0,1\}^m\right)^*$. We show how to systematically construct a finite automaton ${\cal 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 ${\cal 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. \end{abstract} \newpage \section{Introduction} We consider the problem of enumerating Hamiltonian circuits on rectangular grid graphs. \begin{center} \unitlength=0.7mm \linethickness{0.4pt} \begin{picture}(61.00,28.00) \put(6.00,22.00){\circle{2.00}} \put(7.00,22.00){\line(1,0){4.00}} \put(6.00,17.00){\line(0,1){4.00}} \put(6.00,16.00){\circle{2.00}} \put(7.00,16.00){\line(1,0){4.00}} \put(6.00,11.00){\line(0,1){4.00}} \put(12.00,22.00){\circle{2.00}} \put(13.00,22.00){\line(1,0){4.00}} \put(12.00,17.00){\line(0,1){4.00}} \put(12.00,16.00){\circle{2.00}} \put(13.00,16.00){\line(1,0){4.00}} \put(12.00,11.00){\line(0,1){4.00}} \put(18.00,22.00){\circle{2.00}} \put(19.00,22.00){\line(1,0){4.00}} \put(18.00,17.00){\line(0,1){4.00}} \put(18.00,16.00){\circle{2.00}} \put(19.00,16.00){\line(1,0){4.00}} \put(18.00,11.00){\line(0,1){4.00}} \put(24.00,22.00){\circle{2.00}} \put(24.00,17.00){\line(0,1){4.00}} \put(24.00,16.00){\circle{2.00}} \put(24.00,11.00){\line(0,1){4.00}} \put(6.00,10.00){\circle{2.00}} \put(7.00,10.00){\line(1,0){4.00}} \put(12.00,10.00){\circle{2.00}} \put(13.00,10.00){\line(1,0){4.00}} \put(18.00,10.00){\circle{2.00}} \put(19.00,10.00){\line(1,0){4.00}} \put(24.00,10.00){\circle{2.00}} \put(6.00,5.00){\line(0,1){4.00}} \put(6.00,4.00){\circle{2.00}} \put(7.00,4.00){\line(1,0){4.00}} \put(12.00,5.00){\line(0,1){4.00}} \put(12.00,4.00){\circle{2.00}} \put(13.00,4.00){\line(1,0){4.00}} \put(18.00,5.00){\line(0,1){4.00}} \put(18.00,4.00){\circle{2.00}} \put(19.00,4.00){\line(1,0){4.00}} \put(24.00,5.00){\line(0,1){4.00}} \put(24.00,4.00){\circle{2.00}} \put(25.00,22.00){\line(1,0){4.00}} \put(25.00,16.00){\line(1,0){4.00}} \put(30.00,22.00){\circle{2.00}} \put(31.00,22.00){\line(1,0){4.00}} \put(30.00,17.00){\line(0,1){4.00}} \put(30.00,16.00){\circle{2.00}} \put(31.00,16.00){\line(1,0){4.00}} \put(30.00,11.00){\line(0,1){4.00}} \put(36.00,22.00){\circle{2.00}} \put(37.00,22.00){\line(1,0){4.00}} \put(36.00,17.00){\line(0,1){4.00}} \put(36.00,16.00){\circle{2.00}} \put(37.00,16.00){\line(1,0){4.00}} \put(36.00,11.00){\line(0,1){4.00}} \put(42.00,22.00){\circle{2.00}} \put(42.00,17.00){\line(0,1){4.00}} \put(42.00,16.00){\circle{2.00}} \put(42.00,11.00){\line(0,1){4.00}} \put(25.00,10.00){\line(1,0){4.00}} \put(30.00,10.00){\circle{2.00}} \put(31.00,10.00){\line(1,0){4.00}} \put(36.00,10.00){\circle{2.00}} \put(37.00,10.00){\line(1,0){4.00}} \put(42.00,10.00){\circle{2.00}} \put(25.00,4.00){\line(1,0){4.00}} \put(30.00,5.00){\line(0,1){4.00}} \put(30.00,4.00){\circle{2.00}} \put(31.00,4.00){\line(1,0){4.00}} \put(36.00,5.00){\line(0,1){4.00}} \put(36.00,4.00){\circle{2.00}} \put(37.00,4.00){\line(1,0){4.00}} \put(42.00,5.00){\line(0,1){4.00}} \put(42.00,4.00){\circle{2.00}} \put(43.00,22.00){\line(1,0){4.00}} \put(43.00,16.00){\line(1,0){4.00}} \put(48.00,22.00){\circle{2.00}} \put(49.00,22.00){\line(1,0){4.00}} \put(48.00,17.00){\line(0,1){4.00}} \put(48.00,16.00){\circle{2.00}} \put(49.00,16.00){\line(1,0){4.00}} \put(48.00,11.00){\line(0,1){4.00}} \put(54.00,22.00){\circle{2.00}} \put(55.00,22.00){\line(1,0){4.00}} \put(54.00,17.00){\line(0,1){4.00}} \put(54.00,16.00){\circle{2.00}} \put(55.00,16.00){\line(1,0){4.00}} \put(54.00,11.00){\line(0,1){4.00}} \put(60.00,22.00){\circle{2.00}} \put(60.00,17.00){\line(0,1){4.00}} \put(60.00,16.00){\circle{2.00}} \put(60.00,11.00){\line(0,1){4.00}} \put(43.00,10.00){\line(1,0){4.00}} \put(48.00,10.00){\circle{2.00}} \put(49.00,10.00){\line(1,0){4.00}} \put(54.00,10.00){\circle{2.00}} \put(55.00,10.00){\line(1,0){4.00}} \put(60.00,10.00){\circle{2.00}} \put(43.00,4.00){\line(1,0){4.00}} \put(48.00,5.00){\line(0,1){4.00}} \put(48.00,4.00){\circle{2.00}} \put(49.00,4.00){\line(1,0){4.00}} \put(54.00,5.00){\line(0,1){4.00}} \put(54.00,4.00){\circle{2.00}} \put(55.00,4.00){\line(1,0){4.00}} \put(60.00,5.00){\line(0,1){4.00}} \put(60.00,4.00){\circle{2.00}} \put(6.00,28.00){\makebox(0,0)[ct]{0}} \put(60.00,28.00){\makebox(0,0)[ct]{n}} \put(2.00,22.00){\makebox(0,0)[cc]{0}} \put(3.00,4.00){\makebox(0,0)[rc]{m}} \end{picture} \end{center} \caption{The grid graph $G_{3,9}^*$}\label{graph} \bigskip Let $h_{m,n}$ denote the number of Hamiltonian circuits on a grid graph with $(m+1) \times (n+1)$ vertices as in Fig.~\ref{graph}, and let \[ h_m(z) = \sum\limits_{n \geq 1} h_{m,n} z^n \] denote the associated generating function for fixed $m$. The main goal of this article is to outline an algorithm which allows to systematically compute --- in principle --- $h_{m}(z)$ for any $m$. It turns out that $h_m(z)$ is always a rational function, a fact that has been observed by authors who studied this enumeration problem for small values of $m$ by {\em ad hoc} methods (\cite{kreweras},\cite{kwong},\cite{rogers}). This result is an immediate consequence of the transfer-matrix method, which we employ here for the general approach. See Sec. 4.7 in \cite{stanley} for a presentation of this method. Indeed, we show how Hamiltonian circuits on grid graphs can be encoded by the words of a suitable language that is recognized by a finite automaton. Note that Hamiltonicity of a graph has both a local (every vertex is visited exactly once) and a global (the subgraph is connected) aspect. It is quite obvious how to code the local aspect in a way that can be checked by a finite automaton. It is less obvious how the same can be done for the global aspect in a systematical way. This is the main contribution of the present article. Once a coding in terms of a regular language has been given and a recognizing finite automaton has been constructed, the computation of the generating function $h_m(z)$ is a routine matter --- in principle! In practice there are severe limits due to the exponentially increasing number of states (as a function of $m$). Indeed, we can give precise information about the number of states of our automata (prior to minimization) and thus an upper bound for the degree of the denominator polynomial of $h_m(z)$. Interestingly, the states can be put into bijection with the words of the familiar Motzkin language. Even though minimization may cut down the number of states considerably (for $m$ odd about half of the original states turn out to be non-reachable), we conjecture that the growth of the degrees of the denominator polynomials of $h_m(z)$ is of the same order as that of the Motzkin numbers. We refer the reader to \cite{hu} for the basic notions of automata theory needed here, and \cite{br} for the relation between regular languages and rational generating functions. The algorithm outlined here has been implemented by the first author (\cite{stoyan}). For efficiency reasons, this implementation uses a slightly different way of representing the automaton in question, which we will not discuss here. The program, written in the C++ language, and a complete description of its functionality are available on request from the first author. At the end of this article we present some results obtained by this program. \section{Representation and characterization} We begin by introducing some notation: For positive integers $m,n$ the grid graph $G_{m,n}$ is given by its vertex set $ \{\,(x,y) \,;\, 1 \leq x \leq n , 1 \leq y \leq m \,\}$ and the usual nearest-neighbour-edges of a rectangular grid. It is convenient for our purposes to introduce also the extended grid graph $G_{m,n}^*$ with vertex set $ \{\,(x,y) \,;\, 0 \leq x \leq n , 0 \leq y \leq m \,\}$. See Fig.~\ref{graph} for an example. A ``cell'' of $G_{m,n}^*$ is a quadrangle of points \[ [x,y] = \{(x,y), (x-1,y), (x,y-1), (x-1, y-1) \} \] where $1 \leq x \leq n , 1 \leq y \leq m$. Think of $G_{m,n}$ as a graph whose vertices are the cells of $G_{m,n}^*$, and edges in $G_{m,n}$ joining neighbouring cells in $G_{m,n}^*$ (i.e. cells which have an edge of $G_{m,n}^*$ in common). A {\em Hamiltonian circuit} of $G_{m,n}^*$ is a subgraph $H^*$ of $G_{m,n}^*$ with the following properties: \begin{itemize} \item[-] every vertex $(x,y)$ has degree $2$ w.r.t. $H^*$ \item[-] $H^*$ is connected \end{itemize} By a discrete version of the Jordan curve theorem it is clear that each cell $[x,y]$ of $G_{m,n}^*$ lies either ``inside'' or ``outside'' such a Hamiltonian circuit $H^*$. This gives rise to a mapping \[ H : G_{m,n} \rightarrow \{ 0,1 \} : (x,y) \mapsto \cases{ 1& if $[x,y]$ is an ``inside'' cell w.r.t. $H^*$\cr 0& if $[x,y]$ is an ``outside'' cell w.r.t. $H^*$ } \] Let now $F : G_{m,n} \rightarrow \{ 0,1 \}$ be any mapping. We will use the same notation $F$ for different presentations of the same object: \begin{itemize} \item[-] a mapping from (the vertex set of) $G_{m,n}$ to $\{ 0,1 \}$, as indicated; \item[-] the corresponding $(m \times n)$-matrix which has entry $F(x,y)$ in position $(x,y)$; \item[-] the {\em induced} subgraph of $G_{m,n}$ with vertex set $F^{-1} (1)$; \item[-] the word $F^{(1)} F^{(2)} \ldots F^{(n)}$ over the alphabet $\Sigma_m := \{ 0,1 \}^m$ where $F^{(k)}$ denotes the $k$-th column of the matrix $F$, written as a word over $\Sigma_m$, for convenience. \end{itemize} \begin{center} \unitlength=0.7mm \linethickness{0.4pt} \begin{picture}(180.00,30.00)(1.50,4) \put(4.00,33.00){\line(1,0){4.00}} \put(3.00,28.00){\line(0,1){4.00}} \put(4.00,27.00){\line(1,0){4.00}} \put(3.00,16.00){\line(0,1){4.00}} \put(4.00,15.00){\line(1,0){4.00}} \put(3.00,10.00){\line(0,1){4.00}} \put(10.00,33.00){\line(1,0){4.00}} \put(9.00,28.00){\line(0,1){4.00}} \put(10.00,27.00){\line(1,0){4.00}} \put(9.00,16.00){\line(0,1){4.00}} \put(10.00,15.00){\line(1,0){4.00}} \put(9.00,10.00){\line(0,1){4.00}} \put(15.00,33.00){\circle{2.00}} \put(16.00,33.00){\line(1,0){4.00}} \put(15.00,28.00){\line(0,1){4.00}} \put(15.00,21.00){\circle{2.00}} \put(16.00,27.00){\line(1,0){4.00}} \put(15.00,16.00){\line(0,1){4.00}} \put(16.00,15.00){\line(1,0){4.00}} \put(15.00,10.00){\line(0,1){4.00}} \put(21.00,33.00){\circle{2.00}} \put(21.00,28.00){\line(0,1){4.00}} \put(21.00,21.00){\circle{2.00}} \put(21.00,16.00){\line(0,1){4.00}} \put(21.00,15.00){\circle{2.00}} \put(21.00,10.00){\line(0,1){4.00}} \put(3.00,9.00){\circle{2.00}} \put(4.00,9.00){\line(1,0){4.00}} \put(9.00,9.00){\circle{2.00}} \put(10.00,9.00){\line(1,0){4.00}} \put(15.00,9.00){\circle{2.00}} \put(16.00,9.00){\line(1,0){4.00}} \put(21.00,9.00){\circle{2.00}} \put(3.00,4.00){\line(0,1){4.00}} \put(3.00,3.00){\circle{2.00}} \put(4.00,3.00){\line(1,0){4.00}} \put(9.00,4.00){\line(0,1){4.00}} \put(9.00,3.00){\circle{2.00}} \put(10.00,3.00){\line(1,0){4.00}} \put(15.00,4.00){\line(0,1){4.00}} \put(15.00,3.00){\circle{2.00}} \put(16.00,3.00){\line(1,0){4.00}} \put(21.00,4.00){\line(0,1){4.00}} \put(21.00,3.00){\circle{2.00}} \put(22.00,33.00){\line(1,0){4.00}} \put(22.00,27.00){\line(1,0){4.00}} \put(22.00,15.00){\line(1,0){4.00}} \put(27.00,33.00){\circle{2.00}} \put(28.00,33.00){\line(1,0){4.00}} \put(27.00,28.00){\line(0,1){4.00}} \put(27.00,21.00){\circle{2.00}} \put(28.00,27.00){\line(1,0){4.00}} \put(27.00,16.00){\line(0,1){4.00}} \put(27.00,15.00){\circle{2.00}} \put(28.00,15.00){\line(1,0){4.00}} \put(27.00,10.00){\line(0,1){4.00}} \put(33.00,33.00){\circle{2.00}} \put(34.00,33.00){\line(1,0){4.00}} \put(33.00,28.00){\line(0,1){4.00}} \put(33.00,21.00){\circle{2.00}} \put(34.00,27.00){\line(1,0){4.00}} \put(33.00,16.00){\line(0,1){4.00}} \put(33.00,15.00){\circle{2.00}} \put(34.00,15.00){\line(1,0){4.00}} \put(33.00,10.00){\line(0,1){4.00}} \put(39.00,33.00){\circle{2.00}} \put(39.00,28.00){\line(0,1){4.00}} \put(39.00,21.00){\circle{2.00}} \put(39.00,16.00){\line(0,1){4.00}} \put(39.00,15.00){\circle{2.00}} \put(39.00,10.00){\line(0,1){4.00}} \put(22.00,9.00){\line(1,0){4.00}} \put(27.00,9.00){\circle{2.00}} \put(28.00,9.00){\line(1,0){4.00}} \put(33.00,9.00){\circle{2.00}} \put(34.00,9.00){\line(1,0){4.00}} \put(39.00,9.00){\circle{2.00}} \put(22.00,3.00){\line(1,0){4.00}} \put(27.00,4.00){\line(0,1){4.00}} \put(28.00,3.00){\line(1,0){4.00}} \put(33.00,4.00){\line(0,1){4.00}} \put(33.00,3.00){\circle{2.00}} \put(34.00,3.00){\line(1,0){4.00}} \put(39.00,4.00){\line(0,1){4.00}} \put(39.00,3.00){\circle{2.00}} \put(40.00,33.00){\line(1,0){4.00}} \put(40.00,27.00){\line(1,0){4.00}} \put(40.00,15.00){\line(1,0){4.00}} \put(45.00,33.00){\circle{2.00}} \put(46.00,33.00){\line(1,0){4.00}} \put(45.00,28.00){\line(0,1){4.00}} \put(45.00,21.00){\circle{2.00}} \put(46.00,27.00){\line(1,0){4.00}} \put(45.00,16.00){\line(0,1){4.00}} \put(46.00,15.00){\line(1,0){4.00}} \put(45.00,10.00){\line(0,1){4.00}} \put(51.00,33.00){\circle{2.00}} \put(52.00,33.00){\line(1,0){4.00}} \put(51.00,28.00){\line(0,1){4.00}} \put(51.00,21.00){\circle{2.00}} \put(52.00,27.00){\line(1,0){4.00}} \put(51.00,16.00){\line(0,1){4.00}} \put(51.00,15.00){\circle{2.00}} \put(52.00,15.00){\line(1,0){4.00}} \put(51.00,10.00){\line(0,1){4.00}} \put(57.00,33.00){\circle{2.00}} \put(57.00,28.00){\line(0,1){4.00}} \put(57.00,21.00){\circle{2.00}} \put(57.00,16.00){\line(0,1){4.00}} \put(57.00,15.00){\circle{2.00}} \put(57.00,10.00){\line(0,1){4.00}} \put(40.00,9.00){\line(1,0){4.00}} \put(45.00,9.00){\circle{2.00}} \put(46.00,9.00){\line(1,0){4.00}} \put(51.00,9.00){\circle{2.00}} \put(52.00,9.00){\line(1,0){4.00}} \put(57.00,9.00){\circle{2.00}} \put(40.00,3.00){\line(1,0){4.00}} \put(45.00,4.00){\line(0,1){4.00}} \put(45.00,3.00){\circle{2.00}} \put(46.00,3.00){\line(1,0){4.00}} \put(51.00,4.00){\line(0,1){4.00}} \put(51.00,3.00){\circle{2.00}} \put(52.00,3.00){\line(1,0){4.00}} \put(57.00,4.00){\line(0,1){4.00}} \put(15.00,15.00){\circle*{2.00}} \put(9.00,15.00){\circle*{2.00}} \put(9.00,21.00){\circle*{2.00}} \put(9.00,33.00){\circle*{2.00}} \put(3.00,33.00){\circle*{2.00}} \put(3.00,21.00){\circle*{2.00}} \put(3.00,15.00){\circle*{2.00}} \put(3.00,9.00){\circle*{2.00}} \put(3.00,3.00){\circle*{2.00}} \put(3.00,15.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(3.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(3.00,32.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(8.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(9.00,20.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(3.00,15.00){\rule{12.00\unitlength}{1.00\unitlength}} \put(15.00,21.00){\circle*{2.00}} \put(15.00,33.00){\circle*{2.00}} \put(21.00,33.00){\circle*{2.00}} \put(21.00,21.00){\circle*{2.00}} \put(27.00,21.00){\circle*{2.00}} \put(27.00,33.00){\circle*{2.00}} \put(33.00,33.00){\circle*{0.00}} \put(33.00,33.00){\circle*{2.00}} \put(39.00,33.00){\circle*{2.00}} \put(45.00,33.00){\circle*{2.00}} \put(51.00,33.00){\circle*{2.00}} \put(57.00,33.00){\circle*{2.00}} \put(57.00,21.00){\circle*{2.00}} \put(51.00,21.00){\circle*{2.00}} \put(45.00,21.00){\circle*{2.00}} \put(39.00,21.00){\circle*{2.00}} \put(33.00,21.00){\circle*{2.00}} \put(21.00,15.00){\circle*{2.00}} \put(27.00,15.00){\circle*{2.00}} \put(33.00,15.00){\circle*{2.00}} \put(15.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(15.00,32.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(20.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(21.00,20.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(27.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(27.00,32.00){\rule{30.00\unitlength}{1.00\unitlength}} \put(56.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(3.00,8.00){\rule{12.00\unitlength}{1.00\unitlength}} \put(9.00,9.00){\circle*{2.00}} \put(15.00,9.00){\circle*{2.00}} \put(9.00,3.00){\circle*{2.00}} \put(15.00,3.00){\circle*{2.00}} \put(21.00,3.00){\circle*{2.00}} \put(21.00,9.00){\circle*{2.00}} \put(27.00,9.00){\circle*{2.00}} \put(27.00,3.00){\circle*{2.00}} \put(33.00,3.00){\circle*{2.00}} \put(33.00,9.00){\circle*{2.00}} \put(39.00,9.00){\circle*{2.00}} \put(39.00,3.00){\circle*{2.00}} \put(45.00,3.00){\circle*{2.00}} \put(51.00,3.00){\circle*{2.00}} \put(57.00,3.00){\circle*{2.00}} \put(57.00,9.00){\circle*{2.00}} \put(51.00,9.00){\circle*{2.00}} \put(45.00,9.00){\circle*{2.00}} \put(39.00,15.00){\circle*{2.00}} \put(45.00,15.00){\circle*{0.00}} \put(51.00,15.00){\circle*{2.00}} \put(57.00,15.00){\circle*{2.00}} \put(45.00,15.00){\circle*{2.00}} \put(44.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}} \put(56.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(45.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(51.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(51.00,14.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(56.00,3.00){\rule{1.00\unitlength}{12.00\unitlength}} \put(33.00,3.00){\rule{24.00\unitlength}{1.00\unitlength}} \put(33.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(39.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}} \put(44.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}} \put(51.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(51.00,14.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(33.00,27.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(15.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(26.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(21.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(20.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(21.00,15.00){\rule{12.00\unitlength}{1.00\unitlength}} \put(32.00,15.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(33.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(3.00,3.00){\rule{24.00\unitlength}{1.00\unitlength}} \put(3.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(3.00,27.00){\circle*{2.00}} \put(9.00,27.00){\circle*{2.00}} \put(15.00,27.00){\circle*{2.00}} \put(27.00,27.00){\circle*{2.00}} \put(33.00,27.00){\circle*{2.00}} \put(39.00,27.00){\circle*{2.00}} \put(45.00,27.00){\circle*{2.00}} \put(51.00,27.00){\circle*{2.00}} \put(57.00,27.00){\circle*{2.00}} \put(21.00,27.00){\circle*{2.00}} \put(4.00,21.00){\line(1,0){4.00}} \put(16.00,21.00){\line(1,0){4.00}} \put(28.00,21.00){\line(1,0){4.00}} \put(34.00,21.00){\line(1,0){4.00}} \put(40.00,21.00){\line(1,0){4.00}} \put(46.00,21.00){\line(1,0){4.00}} \put(3.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(8.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(15.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(20.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(27.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(32.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(39.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(44.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(51.00,21.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(45.00,27.00){\rule{6.00\unitlength}{1.00\unitlength}} \put(51.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(56.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}} \put(-2.00,0.00) { \put(73.00,30.00){\makebox(0,0)[cc]{1}} \put(79.00,30.00){\makebox(0,0)[cc]{0}} \put(85.00,30.00){\makebox(0,0)[cc]{1}} \put(91.00,30.00){\makebox(0,0)[cc]{0}} \put(97.00,30.00){\makebox(0,0)[cc]{1}} \put(103.00,30.00){\makebox(0,0)[cc]{1}} \put(109.00,30.00){\makebox(0,0)[cc]{1}} \put(115.00,30.00){\makebox(0,0)[cc]{1}} \put(121.00,30.00){\makebox(0,0)[cc]{1}} \put(73.00,18.00){\makebox(0,0)[cc]{1}} \put(79.00,18.00){\makebox(0,0)[cc]{1}} \put(85.00,18.00){\makebox(0,0)[cc]{1}} \put(91.00,18.00){\makebox(0,0)[cc]{1}} \put(97.00,18.00){\makebox(0,0)[cc]{1}} \put(103.00,18.00){\makebox(0,0)[cc]{0}} \put(109.00,18.00){\makebox(0,0)[cc]{1}} \put(115.00,18.00){\makebox(0,0)[cc]{0}} \put(121.00,18.00){\makebox(0,0)[cc]{0}} \put(73.00,6.00){\makebox(0,0)[cc]{1}} \put(79.00,6.00){\makebox(0,0)[cc]{1}} \put(79.00,12.00){\makebox(0,0)[cc]{0}} \put(73.00,12.00){\makebox(0,0)[cc]{0}} \put(85.00,12.00){\makebox(0,0)[cc]{1}} \put(91.00,12.00){\makebox(0,0)[cc]{0}} \put(97.00,12.00){\makebox(0,0)[cc]{0}} \put(103.00,12.00){\makebox(0,0)[cc]{0}} \put(109.00,12.00){\makebox(0,0)[cc]{1}} \put(115.00,12.00){\makebox(0,0)[cc]{0}} \put(121.00,12.00){\makebox(0,0)[cc]{1}} \put(85.00,6.00){\makebox(0,0)[cc]{1}} \put(91.00,6.00){\makebox(0,0)[cc]{1}} \put(97.00,6.00){\makebox(0,0)[cc]{0}} \put(103.00,6.00){\makebox(0,0)[cc]{1}} \put(109.00,6.00){\makebox(0,0)[cc]{1}} \put(115.00,6.00){\makebox(0,0)[cc]{1}} \put(121.00,6.00){\makebox(0,0)[cc]{1}} \put(79.00,24.00){\makebox(0,0)[cc]{0}} \put(73.00,24.00){\makebox(0,0)[cc]{1}} \put(85.00,24.00){\makebox(0,0)[cc]{1}} \put(91.00,24.00){\makebox(0,0)[cc]{0}} \put(97.00,24.00){\makebox(0,0)[cc]{1}} \put(103.00,24.00){\makebox(0,0)[cc]{0}} \put(109.00,24.00){\makebox(0,0)[cc]{1}} \put(115.00,24.00){\makebox(0,0)[cc]{0}} \put(121.00,24.00){\makebox(0,0)[cc]{1}} \put(70.00,33.00){\line(0,-1){30.00}} \put(70.00,33.00){\line(1,0){6.00}} \put(70.00,27.00){\line(1,0){6.00}} \put(70.00,21.00){\line(1,0){6.00}} \put(70.00,15.00){\line(1,0){6.00}} \put(70.00,9.00){\line(1,0){6.00}} \put(70.00,3.00){\line(1,0){6.00}} \put(76.00,33.00){\line(0,-1){30.00}} \put(76.00,33.00){\line(1,0){6.00}} \put(76.00,27.00){\line(1,0){6.00}} \put(76.00,21.00){\line(1,0){6.00}} \put(76.00,15.00){\line(1,0){6.00}} \put(76.00,9.00){\line(1,0){6.00}} \put(76.00,3.00){\line(1,0){6.00}} \put(82.00,33.00){\line(0,-1){30.00}} \put(82.00,33.00){\line(1,0){6.00}} \put(82.00,27.00){\line(1,0){6.00}} \put(82.00,21.00){\line(1,0){6.00}} \put(82.00,15.00){\line(1,0){6.00}} \put(82.00,9.00){\line(1,0){6.00}} \put(82.00,3.00){\line(1,0){6.00}} \put(88.00,33.00){\line(0,-1){30.00}} \put(88.00,33.00){\line(1,0){6.00}} \put(88.00,27.00){\line(1,0){6.00}} \put(88.00,21.00){\line(1,0){6.00}} \put(88.00,15.00){\line(1,0){6.00}} \put(88.00,9.00){\line(1,0){6.00}} \put(88.00,3.00){\line(1,0){6.00}} \put(94.00,33.00){\line(0,-1){30.00}} \put(94.00,33.00){\line(1,0){6.00}} \put(94.00,27.00){\line(1,0){6.00}} \put(94.00,21.00){\line(1,0){6.00}} \put(94.00,15.00){\line(1,0){6.00}} \put(94.00,9.00){\line(1,0){6.00}} \put(94.00,3.00){\line(1,0){6.00}} \put(100.00,33.00){\line(0,-1){30.00}} \put(100.00,33.00){\line(1,0){6.00}} \put(100.00,27.00){\line(1,0){6.00}} \put(100.00,21.00){\line(1,0){6.00}} \put(100.00,15.00){\line(1,0){6.00}} \put(100.00,9.00){\line(1,0){6.00}} \put(100.00,3.00){\line(1,0){6.00}} \put(106.00,33.00){\line(0,-1){30.00}} \put(106.00,33.00){\line(1,0){6.00}} \put(106.00,27.00){\line(1,0){6.00}} \put(106.00,21.00){\line(1,0){6.00}} \put(106.00,15.00){\line(1,0){6.00}} \put(106.00,9.00){\line(1,0){6.00}} \put(106.00,3.00){\line(1,0){6.00}} \put(112.00,33.00){\line(0,-1){30.00}} \put(112.00,33.00){\line(1,0){6.00}} \put(112.00,27.00){\line(1,0){6.00}} \put(112.00,21.00){\line(1,0){6.00}} \put(112.00,15.00){\line(1,0){6.00}} \put(112.00,9.00){\line(1,0){6.00}} \put(112.00,3.00){\line(1,0){6.00}} \put(118.00,33.00){\line(0,-1){30.00}} \put(118.00,33.00){\line(1,0){6.00}} \put(118.00,27.00){\line(1,0){6.00}} \put(118.00,21.00){\line(1,0){6.00}} \put(118.00,15.00){\line(1,0){6.00}} \put(118.00,9.00){\line(1,0){6.00}} \put(118.00,3.00){\line(1,0){6.00}} \put(124.00,33.00){\line(0,-1){30.00}} } \put(56.00,0.00) { \put(76.00,32.00){\line(0,-1){4.00}} \put(76.00,26.00){\line(0,-1){4.00}} \put(76.00,33.00){\circle{2.00}} \put(76.00,27.00){\circle{2.00}} \put(76.00,21.00){\circle{2.00}} \put(76.00,9.00){\circle{2.00}} \put(77.00,21.00){\line(1,0){4.00}} \put(77.00,9.00){\line(1,0){4.00}} \put(82.00,21.00){\circle{2.00}} \put(82.00,9.00){\circle{2.00}} \put(83.00,21.00){\line(1,0){4.00}} \put(83.00,9.00){\line(1,0){4.00}} \put(88.00,32.00){\line(0,-1){4.00}} \put(88.00,26.00){\line(0,-1){4.00}} \put(88.00,20.00){\line(0,-1){4.00}} \put(88.00,14.00){\line(0,-1){4.00}} \put(88.00,33.00){\circle{2.00}} \put(88.00,27.00){\circle{2.00}} \put(88.00,21.00){\circle{2.00}} \put(88.00,15.00){\circle{2.00}} \put(88.00,9.00){\circle{2.00}} \put(89.00,21.00){\line(1,0){4.00}} \put(89.00,9.00){\line(1,0){4.00}} \put(94.00,21.00){\circle{2.00}} \put(94.00,9.00){\circle{2.00}} \put(95.00,21.00){\line(1,0){4.00}} \put(100.00,32.00){\line(0,-1){4.00}} \put(100.00,26.00){\line(0,-1){4.00}} \put(100.00,33.00){\circle{2.00}} \put(100.00,27.00){\circle{2.00}} \put(100.00,21.00){\circle{2.00}} \put(101.00,33.00){\line(1,0){4.00}} \put(106.00,33.00){\circle{2.00}} \put(106.00,9.00){\circle{2.00}} \put(107.00,33.00){\line(1,0){4.00}} \put(107.00,9.00){\line(1,0){4.00}} \put(112.00,32.00){\line(0,-1){4.00}} \put(112.00,26.00){\line(0,-1){4.00}} \put(112.00,20.00){\line(0,-1){4.00}} \put(112.00,14.00){\line(0,-1){4.00}} \put(112.00,33.00){\circle{2.00}} \put(112.00,27.00){\circle{2.00}} \put(112.00,21.00){\circle{2.00}} \put(112.00,15.00){\circle{2.00}} \put(112.00,9.00){\circle{2.00}} \put(113.00,33.00){\line(1,0){4.00}} \put(113.00,9.00){\line(1,0){4.00}} \put(118.00,33.00){\circle{2.00}} \put(118.00,9.00){\circle{2.00}} \put(119.00,33.00){\line(1,0){4.00}} \put(119.00,9.00){\line(1,0){4.00}} \put(124.00,32.00){\line(0,-1){4.00}} \put(124.00,14.00){\line(0,-1){4.00}} \put(124.00,33.00){\circle{2.00}} \put(124.00,27.00){\circle{2.00}} \put(124.00,15.00){\circle{2.00}} \put(124.00,9.00){\circle{2.00}} } \end{picture} \end{center} \caption{Three representations~: conventional, matrix, induced subgraph.} \bigskip Our first goal is to give a handy characterization of those mappings $F$ that correspond to the Hamiltonian circuits of $G_{m,n}^*$. For this purpose we need a concept which allows us to represent the degree constraint of circuits. Two vectors (or words) $u = u_1 \ldots u_p~,~ v = v_1 \ldots v_p \in \{ 0,1 \}^p$ (for some $p$) are {\em compatible}, if for all $k~(1 \leq k < p)$ \[ {u_k ~~~~~ v_k \choose u_{k+1} ~ v_{k+1}} \not\in \left\{ {1 ~ 1 \choose 1 ~ 1} , {0 ~ 0 \choose 0 ~ 0} , {1 ~ 0 \choose 0 ~ 1} , {0 ~ 1 \choose 1 ~ 0} \right\} \] Think of the matrix on the left as representing the ``inside''-``outside'' situation of four neighbouring cells of $G_{m,n}^*$ with respect to a Hamiltonian circuit $H^*$. It is clear that neither of the matrices on the r.h.s is possible because they represent the situation at vertices of degree $0$ or $4$ w.r.t. the subgraph $H^*$. Note that all the other 12 $(2 \times 2)$-matrices over $\{ 0,1 \}$ may occur because they represent the situation occuring at vertices of degree $2$. For any vector (word) $w \in \{0,1\}^m$ let $\overline{w}$ denote the {\em augmented} vector $0 \cdot w \cdot 0 \in \{0,1\}^{m+2}$, constructed by prepending and appending a $0$ to $w$. Furthermore, let ${\bf 0} = 0^m \in \{ 0,1 \}^m$ denote the all-zero vector and ${\overline {\bf 0}} = 0^{m+2}$ the corresponding augmented vector. It is easy to see, that the following holds: \begin{itemize} \item if $H^*$ is a Hamiltonian circuit of $G_{m,n}^*$, then \begin{itemize} \item[--] the sequence of vectors \[ {\overline {\bf 0}}~,~ {\overline H}^{(1)}~,~ {\overline H}^{(2)} ~,~ \ldots ~,~{\overline H}^{(n)} ~,~ {\overline {\bf 0}} \] is a compatible sequence, i.e. ${\overline H}^{(i)}$ is compatible with ${\overline H}^{(i+1)}$ for $0 \leq i \leq n$, where we put ${\overline H}^{(0)} = {\overline {\bf 0}} = {\overline H}^{(n+1)}$ ; \item[--] the induced subgraph $H$ of $G_{m,n}$ is a tree. \end{itemize} \end{itemize} It is a little less obvious that the converse also holds: any mapping $F \,:\, G_{m,n} \rightarrow \{ 0,1 \}$ such that the sequence ${\overline {\bf 0}} , {\overline F}^{(a)} , \ldots , {\overline F}^{(n)}, {\overline {\bf 0}}$ is compatible and such that $F$, viewed as an induced subgraph of $G_{m,n}$, is a tree, actually gives rise to a Hamiltonian circuit of $G_{m,n}^*$. We give a short outline of {\em proof}: $F$ will be used to define a subgraph $F^*$ of $G_{m,n}^*$ in the obvious way: \begin{itemize} \item an edge $(x-1, y) \longleftrightarrow (x,y)$ , where $1 \leq x \leq n ,\, 0 \leq y \leq m$ belongs to $F^*$ (together with its endpoints) iff ${\overline F} (x,y) \not= {\overline F} (x,y + 1)$ \item an edge $(x, y-1) \longleftrightarrow (x,y)$, where $0 \leq x \leq n ,\, 1 \leq y \leq m$ belongs to $F^*$ iff ${\overline F} (x,y) \not= {\overline F} (x+1, y)$ \end{itemize} We have used here the augmented $(m+2) \times (n+2)$-matrix ${\overline F}$: \[ {\overline F} (x,y) = \cases{ F(x,y)& if $ 1 \leq x \leq n, 1 \leq y \leq m$ \cr 0 & if $ x \in \{0, n+1 \}$ or $y \in \{0, m+1 \}$} \] is obtained by bordering $F$ with zeros. The compatibility condition guarantees that $F^*$ has degree $2$ at each vertex. The tree condition guarantees that $F^*$ is connected. \section{Constructing Hamiltonian circuits} Let us now consider the problem of systematically {\em constructing} Hamiltonian circuits $H^* \subseteq G_{m,n}^*$ for fixed $m$ and arbitrary $n \in {\bf N}$. We have seen that these circuits correspond to mappings $H : G_{m,n} \rightarrow \{ 0,1 \}$ such that the sequence ${\overline {\bf 0}}, {\overline H}^{(1)} , {\overline H}^{(2)} , \ldots , {\overline H}^{(n)}, {\overline {\bf 0}}$ of augmented column vectors is a compatible one, and that the induced subgraph $H \subseteq G_{m,n}$ is a tree. This implies that each initial seqment ${\overline {\bf 0}} , {\overline H}^{(1)}, \ldots , {\overline H}^{(k)}$ is a compatible sequence and that the corresponding subgraph $H^{(1\ldots k)} \subseteq G_{m,k}$ is a forest. This forest is ``special'' in that all its trees have at least one vertex belonging to the last, the $k$-th column. We will now consider two aspects: {\em continuation} and {\em termination}. \begin{itemize} \item Continuation: if we want to extend such an initial segment in a way that may ultimately lead to a Hamiltonian circuit $H^* \subseteq G_{m,n}^*$ for some $n > k$, we have to examine as candidates for the $(k+1)$-st column $H^{(k+1)}$ all nonzero vectors $K \in \{ 0,1 \}^m$ such that the following holds: \begin{itemize} \item ${\overline H}^{(k)}$ and ${\overline K}$ are compatible; \item the subgraph induced by $H^{(1)} , \ldots , H^{(k)} , K$ in $G_{m,k+1}$ is again a special forest. \end{itemize} The first of these conditions can be easily checked by a finite automaton. What is less obvious is that for checking the second condition we do not need to know the whole ``history'' $H^{(1)} , \ldots , H^{(k)}$, but only a limited (i.e. bounded for $m$ fixed) amount of information in addition to knowing $H^{(k)}$ : \begin{itemize} \item[-] we need to know which of the 1-cells of $H^{(k)}$ (i.e. the $y$ such that $H^{(k)}_y = H(k,y) = 1$) belong to the same tree in the special forest induced by $H^{(1)} , \ldots , H^{(k)}$. \end{itemize} We can then check whether the addition of $K$ as $(k+1)$-st column leads to a cycle or not in the new induced subgraph, and if not, whether all the previously existing trees are now merged into trees which all have at least one vertex belonging to in the $(k+1)$-st column. Note that the addition of $K$ may also create new trees consisting of just a single vertex or a string of vertices in the $(k+1)$-st column. (In the example given in Fig.~\ref{partition}, this happens in the third column.) \item Termination: If all the vertices of $H^{(k)}$ belong to the same tree, then by maintaining the property of being a ``special'' forest by continuation, it is clear that the forest induced by $H^{(1)} , \ldots , H^{(k)}$ is in fact a single tree. If ${\overline H}^{(k)}$ turns out to be compatible with ${\overline {\bf 0}}$, we may terminate the construction and a Hamiltonian cycle of $G^*_{m,k}$ is constructed. \end{itemize} \section{Some technical details} It should be evident from the previous section that for each fixed $m > 0$ a finite automaton can be constructed which works over the alphabet $\Sigma_m = \{ 0,1 \}^m$ and which accepts a word $H = H^{(1)} H^{(2)} \ldots H^{(n)} \in \Sigma_m^*$ if and only if the corresponding matrix $H$ represents a Hamiltonian circuit of $G_{m,n}^*$. In this section we look a little closer on the problem how to construct such an automaton. The main point is, of course, how to integrate the knowledge about the forest induced by initial segments $H^{(1)} H^{(2)} \ldots H^{(k)}$ into the states of such an automaton. Let us begin with recalling some familiar concepts from combinatorics. A {\em partition} of the set $[1..n] := \{ 1,2 , \ldots , n \}$ can be specified by a function $\pi : [1..n] \rightarrow [1..n]$ such that \[ \pi (1) = 1~,~ 1 \leq \pi (j) \leq \max \{ \pi (i) ; i < j \} + 1 ~ \mbox{for} ~ 2 \leq j \leq n \] The idea of this coding is that element $j$ belongs to block number $k$ if $\pi (j) = k$, and the sequence of smallest elements in blocks numbered $1,2,3, \ldots$ is increasing. A partition $\pi$ of $[1..n]$ is {\em non-crossing} ($ncp$) if for each quadruple $1 \leq i < j < k < l \leq n$ \[ \pi (i) = \pi (k) \wedge \pi (j) = \pi (l) ~~ \mbox{implies} ~~ \pi (i) = \pi (j) (= \pi (k) = \pi (l)) \] For later use we introduce the notation ${\cal NCP}_n$ to denote the set of non-crossing partitions of $[1..n]$. If we look at the situation discussed above, namely that of a sequence $H^{(1)}, H^{(2)}, \ldots , H^{(k)} ~ \mbox{in} ~ \Sigma_m$ inducing a ``special'' forest in $G_{m,k}$, we notice that the partition $\pi$ of the vertices belonging to $H^{(k)}$ according to the membership in the trees of the forest is necessarily an $ncp$. More precisely, let \[ {\overline H}^{(k)} = 0^{j_0} 1^{i_1} 0^{j_1} 1^{i_2} 0^{j_2} \ldots 1^{i_r} 0^{j_r}~~\hbox{with}~~i_1, \ldots , i_r, j_0, j_1 , \ldots , j_r > 0 \] \smallskip %F3 %F3 \setlength{\mylength}{\textwidth} %F3 \addtolength{\mylength}{-3.0cm} %F3 %F3 \noindent %F3 \begin{minipage}{\mylength} %F3 be the unique factorization of ${\overline H}^{(k)}$ into maximal $0$-blocks and maximal $1$-blocks. Vertices belonging to the same $1$-block obviously belong to the same tree induced by $H^{(1)} , \ldots , H^{(k)}$. Thus a partition $\pi$ of $[1..r]$ indicates to which tree the vertices of each $1$-block belong. An example is given in Fig.~\ref{partition}, where a Hamiltonian circuit on $G_{9,5}^*$, written in matrix form, is given, together with the {\em ncp}s associated to the five column vectors and coding the backward tree structure. These partitions $\pi$ must belong to ${\cal NCP}$ for obvious topological reasons. Otherwise we would have a contradictory situation as indicated in Fig.~\ref{cross}. These objects, pairs $(u,\pi)$ consisting of a vector $u \in \{ 0,1 \}^m$ together with an $ncp ~ \pi$ on its set of maximal $1$-blocks, are actually the {\em states} of the automaton we are going to construct. \end{minipage} \hfill %F3 \begin{minipage}{2.0cm} %F3 \begin{center} %F3 \unitlength=0.7pt \begin{picture}(60.70,261.09)(8.50,8.45) \put(55.51,8.45){\line(0,1){17.01}} \put(38.41,8.45){\line(0,1){17.01}} \put(55.51,25.46){\line(0,1){17.01}} \put(38.41,25.46){\line(0,1){17.01}} \put(55.51,42.47){\line(0,1){17.01}} \put(38.47,25.50){\line(1,0){17.01}} \put(55.49,8.41){\line(-1,0){17.01}} \put(38.47,59.50){\line(0,-1){17.00}} \put(38.47,42.50){\line(1,0){17.01}} \put(38.40,59.50){\line(1,0){17.01}} \put(55.51,78.45){\line(0,1){17.01}} \put(38.41,78.45){\line(0,1){17.01}} \put(55.51,95.46){\line(0,1){17.01}} \put(38.41,95.46){\line(0,1){17.01}} \put(55.51,112.47){\line(0,1){17.01}} \put(38.47,95.50){\line(1,0){17.01}} \put(55.49,78.41){\line(-1,0){17.01}} \put(38.47,129.50){\line(0,-1){17.00}} \put(38.47,112.50){\line(1,0){17.01}} \put(38.40,129.50){\line(1,0){17.01}} \put(55.51,148.45){\line(0,1){17.01}} \put(38.41,148.45){\line(0,1){17.01}} \put(55.51,165.46){\line(0,1){17.01}} \put(38.41,165.46){\line(0,1){17.01}} \put(55.51,182.47){\line(0,1){17.01}} \put(38.47,165.50){\line(1,0){17.01}} \put(55.49,148.41){\line(-1,0){17.01}} \put(38.47,199.50){\line(0,-1){17.00}} \put(38.47,182.50){\line(1,0){17.01}} \put(38.40,199.50){\line(1,0){17.01}} \put(55.51,218.45){\line(0,1){17.01}} \put(38.41,218.45){\line(0,1){17.01}} \put(55.51,235.46){\line(0,1){17.01}} \put(38.41,235.46){\line(0,1){17.01}} \put(55.51,252.47){\line(0,1){17.01}} \put(38.47,235.50){\line(1,0){17.01}} \put(55.49,218.41){\line(-1,0){17.01}} \put(38.47,269.50){\line(0,-1){17.00}} \put(38.47,252.50){\line(1,0){17.01}} \put(38.40,269.50){\line(1,0){17.01}} \put(38.00,244.00){\line(-2,-5){28.00}} \put(38.07,103.32){\line(-2,5){28.07}} \put(38.00,175.00){\line(-2,-5){29.00}} \put(37.96,31.16){\line(-2,5){28.96}} \put(7.84,139.85){\vector(1,0){10.23}} \put(23.47,139.85){\circle{8}} \put(47.01,16.96){\makebox(0,0)[cc]{1}} \put(47.01,50.97){\makebox(0,0)[cc]{1}} \put(47.06,38.04){\makebox(0,0)[cc]{\vdots}} \put(47.01,86.96){\makebox(0,0)[cc]{1}} \put(47.01,120.97){\makebox(0,0)[cc]{1}} \put(47.06,108.04){\makebox(0,0)[cc]{\vdots}} \put(47.01,156.96){\makebox(0,0)[cc]{1}} \put(47.01,190.97){\makebox(0,0)[cc]{1}} \put(47.06,178.04){\makebox(0,0)[cc]{\vdots}} \put(47.01,226.96){\makebox(0,0)[cc]{1}} \put(47.01,260.97){\makebox(0,0)[cc]{1}} \put(47.06,248.04){\makebox(0,0)[cc]{\vdots}} \put(68.53,243.91){\makebox(0,0)[cc]{A}} \put(68.43,173.58){\makebox(0,0)[cc]{B}} \put(68.43,103.85){\makebox(0,0)[cc]{A}} \put(68.43,33.60){\makebox(0,0)[cc]{B}} \end{picture} %F3 \caption{}\label{cross} %F3 \end{center} %F3 \end{minipage} %F3 %F3 \smallskip %F3 \noindent \begin{center} \begin{minipage}{290pt} \begin{minipage}{95pt} \begin{center} \unitlength=0.7pt \begin{picture}(104.45,153.09)(8.50,8.45) \put(93.56,8.45){\line(-1,0){85.05}} \put(93.56,8.45){\line(0,1){17.01}} \put(76.54,8.45){\line(0,1){17.01}} \put(59.53,8.45){\line(0,1){17.01}} \put(42.53,8.45){\line(0,1){17.01}} \put(25.51,8.45){\line(0,1){17.01}} \put(8.51,8.45){\line(0,1){17.01}} \put(93.56,25.46){\line(-1,0){85.05}} \put(93.56,25.46){\line(0,1){17.01}} \put(76.54,25.46){\line(0,1){17.01}} \put(59.53,25.46){\line(0,1){17.01}} \put(42.53,25.46){\line(0,1){17.01}} \put(25.51,25.46){\line(0,1){17.01}} \put(8.51,25.46){\line(0,1){17.01}} \put(93.56,42.47){\line(-1,0){85.05}} \put(93.56,42.47){\line(0,1){17.01}} \put(76.54,42.47){\line(0,1){17.01}} \put(59.53,42.47){\line(0,1){17.01}} \put(42.53,42.47){\line(0,1){17.01}} \put(25.51,42.47){\line(0,1){17.01}} \put(8.51,42.47){\line(0,1){17.01}} \put(93.56,59.48){\line(-1,0){85.05}} \put(93.56,59.48){\line(0,1){17.01}} \put(76.54,59.48){\line(0,1){17.01}} \put(59.53,59.48){\line(0,1){17.01}} \put(42.53,59.48){\line(0,1){17.01}} \put(25.51,59.48){\line(0,1){17.01}} \put(8.51,59.48){\line(0,1){17.01}} \put(93.56,76.49){\line(-1,0){85.05}} \put(93.56,76.49){\line(0,1){17.01}} \put(76.54,76.49){\line(0,1){17.01}} \put(59.53,76.49){\line(0,1){17.01}} \put(42.53,76.49){\line(0,1){17.01}} \put(25.51,76.49){\line(0,1){17.01}} \put(8.51,76.49){\line(0,1){17.01}} \put(93.56,93.50){\line(-1,0){85.05}} \put(93.56,93.50){\line(0,1){17.01}} \put(76.54,93.50){\line(0,1){17.01}} \put(59.53,93.50){\line(0,1){17.01}} \put(42.53,93.50){\line(0,1){17.01}} \put(25.51,93.50){\line(0,1){17.01}} \put(8.51,93.50){\line(0,1){17.01}} \put(93.56,110.51){\line(-1,0){85.05}} \put(93.56,110.51){\line(0,1){17.01}} \put(76.54,110.51){\line(0,1){17.01}} \put(59.53,110.51){\line(0,1){17.01}} \put(42.53,110.51){\line(0,1){17.01}} \put(25.51,110.51){\line(0,1){17.01}} \put(8.51,110.51){\line(0,1){17.01}} \put(93.56,127.52){\line(-1,0){85.05}} \put(93.56,127.52){\line(0,1){17.01}} \put(76.54,127.52){\line(0,1){17.01}} \put(59.53,127.52){\line(0,1){17.01}} \put(42.53,127.52){\line(0,1){17.01}} \put(25.51,127.52){\line(0,1){17.01}} \put(8.51,127.52){\line(0,1){17.01}} \put(93.56,144.53){\line(-1,0){85.05}} \put(93.56,144.53){\line(0,1){17.01}} \put(76.54,144.53){\line(0,1){17.01}} \put(59.53,144.53){\line(0,1){17.01}} \put(42.53,144.53){\line(0,1){17.01}} \put(25.51,144.53){\line(0,1){17.01}} \put(8.51,144.53){\line(0,1){17.01}} \put(93.56,161.54){\line(-1,0){85.05}} \put(17.01,16.96){\makebox(0,0)[cc]{1}} \put(34.02,16.96){\makebox(0,0)[cc]{1}} \put(51.03,16.96){\makebox(0,0)[cc]{1}} \put(68.04,16.96){\makebox(0,0)[cc]{1}} \put(85.05,16.96){\makebox(0,0)[cc]{1}} \put(17.01,33.96){\makebox(0,0)[cc]{0}} \put(34.02,33.96){\makebox(0,0)[cc]{0}} \put(51.03,33.96){\makebox(0,0)[cc]{1}} \put(68.04,33.96){\makebox(0,0)[cc]{0}} \put(85.05,33.96){\makebox(0,0)[cc]{0}} \put(17.01,50.97){\makebox(0,0)[cc]{1}} \put(34.02,50.97){\makebox(0,0)[cc]{1}} \put(51.03,50.97){\makebox(0,0)[cc]{1}} \put(68.04,50.97){\makebox(0,0)[cc]{1}} \put(85.05,50.97){\makebox(0,0)[cc]{1}} \put(17.01,67.98){\makebox(0,0)[cc]{0}} \put(34.02,67.98){\makebox(0,0)[cc]{0}} \put(51.03,67.98){\makebox(0,0)[cc]{1}} \put(68.04,67.98){\makebox(0,0)[cc]{0}} \put(85.05,67.98){\makebox(0,0)[cc]{1}} \put(17.01,84.99){\makebox(0,0)[cc]{1}} \put(34.02,84.99){\makebox(0,0)[cc]{1}} \put(51.03,84.99){\makebox(0,0)[cc]{1}} \put(68.04,84.99){\makebox(0,0)[cc]{0}} \put(85.05,84.99){\makebox(0,0)[cc]{1}} \put(17.01,102.01){\makebox(0,0)[cc]{1}} \put(34.02,102.01){\makebox(0,0)[cc]{0}} \put(51.03,102.01){\makebox(0,0)[cc]{0}} \put(68.04,102.01){\makebox(0,0)[cc]{0}} \put(85.05,102.01){\makebox(0,0)[cc]{1}} \put(17.01,119.02){\makebox(0,0)[cc]{1}} \put(34.02,119.02){\makebox(0,0)[cc]{0}} \put(51.03,119.02){\makebox(0,0)[cc]{1}} \put(68.04,119.02){\makebox(0,0)[cc]{1}} \put(85.05,119.02){\makebox(0,0)[cc]{1}} \put(17.01,136.03){\makebox(0,0)[cc]{1}} \put(34.02,136.03){\makebox(0,0)[cc]{0}} \put(51.03,136.03){\makebox(0,0)[cc]{0}} \put(68.04,136.03){\makebox(0,0)[cc]{0}} \put(85.05,136.03){\makebox(0,0)[cc]{1}} \put(17.01,153.04){\makebox(0,0)[cc]{1}} \put(34.02,153.04){\makebox(0,0)[cc]{1}} \put(51.03,153.04){\makebox(0,0)[cc]{1}} \put(68.04,153.04){\makebox(0,0)[cc]{0}} \put(85.05,153.04){\makebox(0,0)[cc]{1}} \put(112.96,85.23){\makebox(0,0)[cc]{{\boldmath $\rightarrow$}}} \end{picture} \end{center} \end{minipage} \begin{minipage}{190pt} $ \left( \begin{array}{c} 1\\ 2\\ 3 \end{array} \right) , \left( \begin{array}{c} 1\\ 1\\ 2\\ 3 \end{array} \right) , \left( \begin{array}{c} 1\\ 2\\ 1 \end{array} \right) , \left( \begin{array}{c} 1\\ 2\\ 2 \end{array} \right) , \left( \begin{array}{c} 1\\ 1 \end{array} \right) $ \end{minipage} \end{minipage} \end{center} \smallskip \noindent \caption{Example~: The partitions $\pi$ corresponding to the columns.} \label{partition} \vskip0.5cm We now define the state set: \[ Q_m = \left\{\, q = (u, \pi) \,;\, u \in \{ 0,1 \}^m , \pi ~ ncp ~\mbox{on maximal 1-blocks of} ~ u \,\right\} \] \section{Construction of the automaton ${\cal A}_m$} Let $ L_{m} \subset \Sigma_m^*$ denote the set of matrices corresponding to Hamiltonian circuits on $G_{m,n}^*$ for some $n \geq 1$. $L_m$ will be considered as a language over the alphabet $\Sigma_m = \{0,1\}^m$, written as column vectors, and with horizontal concatenation of columns as operation. In this section we will construct a finite automaton ${\cal A}_{m}$ recognizing this language $L_m$. \begin{center} \unitlength=0.7pt %\unitlength=1.0pt \begin{picture}(400.63,290)(0,-80) \newsavebox{\state} \savebox{\state}(00.00,50.00) { \put(25.36,25.36){\line(-1,0){17.01}} \put(8.35,42.37){\line(1,0){17.01}} \put(8.35,8.35){\framebox(17.01,51.03)[cc]{}} \put(24.51,34.26){\oval(50.63,66.64)} } %\put(00.00,-5.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(0,0) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{0}} \put(16.90,28.77){\makebox(0,0)[cc]{1}} \put(16.80,11.77){\makebox(0,0)[cc]{0}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } %\put(200.00,-5.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(200.00,0) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{0}} \put(16.90,28.77){\makebox(0,0)[cc]{0}} \put(16.80,11.77){\makebox(0,0)[cc]{1}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } %\put(280.00,5.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(280.00,10.00) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{1}} \put(16.90,28.77){\makebox(0,0)[cc]{0}} \put(16.80,11.77){\makebox(0,0)[cc]{1}} \put(32.80,30.07) { \makebox(0,0)[cc] { $ \left(\!\!\!\!\hspace{1.0pt} \begin{array}{c} 1\\ 1 \end{array} \hspace{1.0pt}\!\!\!\!\right) $ } } } %\put(50.00,65.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(55.00,70.00){\usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{1}} \put(16.90,28.77){\makebox(0,0)[cc]{0}} \put(16.80,11.77){\makebox(0,0)[cc]{1}} \put(32.80,30.07){ \makebox(0,0)[cc]{ $ \left(\!\!\!\!\hspace{1.0pt} \begin{array}{c} 1\\ 2 \end{array} \hspace{1.0pt}\!\!\!\!\right) $ } } } %\put(135.00,55.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(135.00,60.00) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{1}} \put(16.90,28.77){\makebox(0,0)[cc]{1}} \put(16.80,11.77){\makebox(0,0)[cc]{1}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } %\put(350.00,65.00){\put(24.51,34.26){\oval(50.63,66.64)}} \put(350.00,70.00) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{1}} \put(16.90,28.77){\makebox(0,0)[cc]{0}} \put(16.80,11.77){\makebox(0,0)[cc]{0}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } %\put(250.00,185.00) %{ % \put(-24.51,-34.26) % { % \usebox{\state} % \put(16.85,45.88){\makebox(0,0)[cc]{0}} % \put(16.90,28.77){\makebox(0,0)[cc]{0}} % \put(16.80,11.77){\makebox(0,0)[cc]{0}} % \put(38.00,28.00){\makebox(0,0)[cc]{$\left(\right)$}} % \put(38.00,50.00){\makebox(0,0)[cc]{$\omega$}} % } %} %Hier gehts weiter einer der neuen ovale wurde schon eingef"ugt (siehe oben) %so. \put(159.51,185.00) { \put(-24.51,-34.26) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{0}} \put(16.90,28.77){\makebox(0,0)[cc]{0}} \put(16.80,11.77){\makebox(0,0)[cc]{0}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(\right)$}} % \put(38.00,50.00){\makebox(0,0)[cc]{$\alpha$}} } } \put(5,-20.00) { % \put(353.07,147.84){\vector(-1,0){257.07}} % \put(74.74,174.07){\vector(0,-1){19.13}} % \put(159.39,174.34){\vector(0,-1){29.38}} % \put(102.13,119.97){\vector(1,0){29.79}} % \put(196.82,40.09){\vector(-2,1){100.91}} % \put(52.28,58.07){\vector(2,1){79.65}} % \put(137.92,80.52){\vector(-2,-1){86.01}} % \put(186.95,120.53){\vector(1,0){159.94}} % \put(347.01,134.77){\vector(-1,0){163.70}} % \put(186.86,105.09){\vector(4,-1){92.41}} % \put(185.47,88.20){\vector(3,-1){21.44}} % \put(196.74,61.67){\vector(-2,1){25.86}} % \put(276.91,48.83){\vector(-1,0){24.78}} % \put(329.70,82.54){\vector(3,2){19.86}} % \put(304.74,24.02){\vector(0,-1){22.63}} % \put(159.91,74.02){\vector(0,-1){72.72}} %\put(24.51,49.26){\oval(50.63,66.64)} %\put(224.51,49.26){\oval(50.63,66.64)} %\put(304.51,59.26){\oval(50.63,66.64)} %\put(74.51,119.26){\oval(50.63,66.64)} %\put(159.51,109.26){\oval(50.63,66.64)} %\put(374.51,119.26){\oval(50.63,66.64)} %\put(250.00,200.00){\oval(50.63,66.64)} %\put(159.51,200.00){\oval(50.63,66.64)} \put(46.50,118.50){\oval(51.00,25.00)[l]} \put(46.00,131.00){\vector(1,0){1.00}} \put(332.00,58.50){\oval(52.00,25.00)[r]} \put(333.00,46.00){\vector(-1,0){1.00}} \put(353.07,147.84){\vector(-1,0){257.07}} \put(132.67,180.48){\vector(-2,-1){50.02}} \put(155.00,160.00){\vector(0,-1){15.00}} \put(165.00,145.00){\vector(0,1){15.00}} \put(102.13,119.97){\vector(1,0){29.79}} \put(196.82,40.09){\vector(-2,1){100.91}} \put(52.28,58.07){\vector(2,1){79.65}} \put(137.92,80.52){\vector(-2,-1){86.01}} \put(186.95,120.53){\vector(1,0){159.94}} \put(347.01,134.77){\vector(-1,0){163.70}} \put(186.86,105.09){\vector(4,-1){92.41}} \put(185.47,88.20){\vector(3,-1){21.44}} \put(196.74,61.67){\vector(-2,1){25.86}} \put(276.91,48.83){\vector(-1,0){24.78}} \put(329.70,82.54){\vector(3,2){19.86}} \put(46.00,131.00){\vector(1,0){1.00}} \put(333.00,46.00){\vector(-1,0){1.00}} % \put(174.59,142.84){\vector(3,2){49.90}} % \put(291.12,93.59){\vector(-1,2){35.11}} \put(280,85){\vector(-1,1){95}} } \put(60,-80) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{1}} \put(16.90,28.77){\makebox(0,0)[cc]{1}} \put(16.80,11.77){\makebox(0,0)[cc]{0}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } \put(240,-80) { \usebox{\state} \put(16.85,45.88){\makebox(0,0)[cc]{0}} \put(16.90,28.77){\makebox(0,0)[cc]{1}} \put(16.80,11.77){\makebox(0,0)[cc]{1}} \put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}} } \put(120,-60){\vector(1,0){120}} \put(240,-50){\vector(-1,0){120}} \end{picture} \end{center} \caption{The transition system ${\cal T}_{3}$}\label{auto} \bigskip We first construct a transition system ${\cal T}_m = (Q_m, \rightarrow)$ as follows: \begin{quote} for $q, q' \in Q_m$ with $q = (u, \pi )$, $q' = (v, \sigma)$ we put $q \rightarrow q'$ if and only if the following holds \begin{itemize} \item[--] ${\overline u}$ and ${\overline v} \in \{ 0,1 \}^{m+2}$ are compatible vectors \item[--] extending the (type of) special forest structure encoded in $q=(u,\pi)$ via the {\em ncp} $\pi$ by column $v$ again leads to a (type of) special forest structure, which is encoded by $(v,\sigma)$. \end{itemize} \end{quote} It must be admitted that checking the second item is rather intricate to implement. No further details are given here, see \cite{stoyan}. We point out, however, that given a state $q = (u, \pi)$ and $v \in \Sigma_m$ such that ${\overline u}$ and ${\overline v}$ are compatible, there is {\em at most one} $\sigma$ such that $q' = (v, \sigma) \in Q_m$ and $q \rightarrow q'$ holds. The paths of length $n+1$ in ${\cal T}_m$, starting at $q_0 :=({\bf 0},\emptyset)$ and ending in $q_0$, without returning to $q_0$ in between, precisely correspond to the Hamiltonian circuits of $G_{m,n}^*$. This leads to the construction of the automaton ${\cal A}_m := \langle Q'_m, \Sigma_m, \delta, \alpha, \Omega\rangle$. Again, we take $\Sigma_m = \{ 0,1 \}^m$ as alphabet and define a {\em complete deterministic} automaton over the state set \[ Q'_m = \left\{ Q_m \setminus q_0 \right\} \cup \left\{ \alpha, \rho \right\} \] where the new states $\alpha$ ($\rho$ resp.) serve as {\em initial} ({\em dead} resp.) states. The set $\Omega$ of terminal states is given by \[ \Omega = \{\,(u,\pi_{\omega})\,;\, (u,\pi_{\omega}) \rightarrow q_0~\hbox{in}~{\cal T}_m\,\} \] Here $\pi_{\omega} = (1)$ denotes the {\em ncp} where all 1-blocks belong to the same class. The transition function $\delta ~:~Q_m' \times \Sigma_m \rightarrow Q_m'$ is defined as follows: \begin{itemize} \item[--] for $q=(u,\pi) , \, q' = (v,\sigma) \in Q_m \setminus \{q_0\}$ : \[ \delta(q,v) := \cases{ q' & iff $q \rightarrow q' ~\hbox{in}~{\cal T}_m$ \cr \rho & iff $q \not\rightarrow q' ~\hbox{in}~{\cal T}_m$} \] \item[--] for each $u \in \Sigma_m$ such that $q_0 \rightarrow (u,\pi_{\alpha})~\hbox{in}~{\cal T}_m$ : \[ \delta(\alpha,u) = (u,\pi_{\alpha}) \] \end{itemize} Here $\pi_{\alpha}$ is the {\em ncp} where each 1-block of $u$ is in a class by itself. The language $L_m$ of Hamiltonian circuits on $G_{m,n}^*$ (for some $n \geq 1$) is the language accepted by ${\cal A}_m$. In particular, we have thus shown that the language $L_m$ is a regular (rational) language for any $m$, and that its generating function is rational. \section{A review of the Motzkin language} In the next section we will present another way of writing the states of our transition systems ${\cal T}_m$, hence of the automata ${\cal A}_m$. This has the double advantage of being closer to the actual implementation of the automata, and of giving precise information about the size (number of states) of ${\cal T}_m$ and ${\cal A}_m$. Quite surprisingly, it turns out that the states of ${\cal T}_m$ can be put into bijection with the words of length $m+1$ of the familiar Motzkin language. In the present section we recall some (familiar) facts about the Motzkin language ${\cal M}$ over the ternary alphabet $\{x,\xbar,y\}$. This language can be defined as the unique solution in $\{x,\xbar,y\}^*$ of the fixed point equation \[ Z = y^* \cdot ( \lambda + x \cdot Z \cdot \xbar \cdot Z)~~~, \] where $\lambda$ denotes the empty word. This equation reflects the fact that ${\cal M}$ is a context-free language, generated by the (unambiguous) grammar \[ Z \rightarrow Y + Y \cdot x \cdot Z \cdot \xbar \cdot Z~~,~~ Y \rightarrow \lambda + y \cdot Y \] Hence, a word $w \in \{x,\xbar,y\}^*$ belongs to ${\cal M}$ if and only if one of the two cases holds: \begin{itemize} \item[--] $w = y^k$ for some $k \geq 0$ \item[--] $w$ has a factorization $w = y^k \cdot x \cdot u \cdot \xbar \cdot v$ with $u,v \in {\cal M}$ and $k \geq 0$ (recursion!) \end{itemize} Another way of looking at the Motzkin language is by taking the Dyck language over the alphabet $\{x,\xbar\}$ and ``shuffling'' it with the set of words $y^* = \{ y^k\,;\, k \geq 0 \}$. We note in passing that the set ${\cal NCP}_n$ of non-crossing partitions of $[1..n]$ is in bijection with the words of length $2n$ of the Dyck-language over $\{x,\xbar\}$, hence the cardinality $\sharp {\cal NCP}_n$ is the Catalan number $\hbox{\em cat}_n = {1 \over n+1}{2n \choose n}$. We now list some known facts about $\hbox{\em mot}_n := \sharp {\cal M}_n$, the number of Motzkin words of length $n$: \begin{itemize} \item[--] The sum representation \[ \hbox{\em mot}_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \hbox{\em cat}_k {n \choose 2 k} = \sum_{k=0}^{\lfloor n/2 \rfloor} {1 \over k+1} {2k \choose k}{n \choose 2k} \] \item[--] The generating function \begin{eqnarray*} \sum_n \hbox{\em mot}_n \, z^n &=& \frac{1-z-\sqrt{1-2z-3z^2}}{2z^2} \\ &=& 1+z+2 z^2+4 z^3 + 9 z^4 + 21 z^5 + 51 z^6 + \ldots \end{eqnarray*} \item[--] The asymptotic behaviour \[ \hbox{\em mot}_n = \sqrt{3 \over 4\,\pi\,n^3} \, 3^n - {45 \over 32} {1 \over \sqrt{3 \,\pi\,n^5}} \, 3^n + O\left({3^n \over n^{7/2}}\right) \] \end{itemize} \section{A bijection} We will now define a mapping $\Psi$ which maps the state set $Q_m$ of the transition system ${\cal T}_m$ bijectively onto the set ${\cal M}_{m+1}$ of words of length $m+1$ of the Motzkin language ${\cal M}$ over the alphabet $\{x,\xbar,y\}$. The definition is by induction on $m$. \begin{itemize} \item[--] For $m=0$, we formally introduce $Q_0 = \{(\lambda,\emptyset)\}$, where $\lambda$ is the empty word and $\emptyset$ denotes the empty partition, the unique element of ${\cal NCP}_0$. This ``state'' is mapped by $\Psi$ onto the word $y \in {\cal M}_1$. \item[--] More generally: for any $m \geq 0$, the state set $Q_m$ contains the element $(0^m,\emptyset)$, and this particular state will be mapped by $\Psi$ onto the word $y^{m+1} \in {\cal M}_{m+1}$. \item[--] Let $q = (u,\pi) \in Q_m, q \neq (0^m,\emptyset)$. Then $u \in \{0,1\}^m$ has $r$ maximal 1-blocks for some $r$ with $1 \leq r \leq \lfloor m/2 \rfloor$, and $\pi$ is an element of ${\cal NCP}_r$. As in Section 4, write \[ \overline{u} = 0 \cdot u \cdot 0 = 0^{j_0} 1^{i_1} 0^{j_1} 1^{i_2} 0^{j_2} \ldots 1^{i_r} 0^{j_r} \] with $i_1, \ldots ,i_r,j_0, \ldots ,j_r > 0$ and \[ i_1 + \ldots + i_r + j_0 +\ldots + j_r = m+2 \] Now factorize $\pi$ according to the last position in $\pi(1) \pi(2) \ldots \pi(r)$ where ``1'' appears. Let \begin{eqnarray*} k &=& \max \{\,\nu\,;\, \pi(\nu) = 1 \,\} \\ h &=& \max \{\,\pi(\nu)\,;\,1 \leq \nu \leq k \,\} \end {eqnarray*} Thus $k$ is this last position and $h$ is the maximum block number that appears up to this position. By the properties of non-crossing partitions it is clear that after position $k$ only block numbers bigger than $h$ appear in $\pi$. More precisely: \begin{eqnarray*} \pi' &:=& \pi(1) \pi(2) \ldots \pi(k-1) \in {\cal NCP}_{k-1} \\ \pi'' &:=& (\pi(k+1)-h)(\pi(k+2)-h) \ldots(\pi(r)-h) \in {\cal NCP}_{r-k} \end{eqnarray*} (This decomposition $\pi \mapsto (\pi',\pi'')$ can actually be used to produce a bijection between ${\cal NCP}_r$ and the set of Dyck words of length $2r$.) Now let \begin{eqnarray*} q' &:=& \left( 0^{j_0} 1^{i_1} 0^{j_1} \ldots 0^{j_{k-2}} 1^{i_{k-1}} 0^{j_{k-1}}\,,\,\pi' \right) \in Q_{m'} \\ q'' &:=& \left( 0^{j_k} 1^{i_{k+1}} 0^{j_{k+1}} \ldots 0^{j_{r-1}} 1^{i_r} 0^{j_r}\,,\,\pi'' \right) \in Q_{m''} \end{eqnarray*} where \begin{eqnarray*} i_1 + \cdots + i_{k-1} + j_0 + \cdots + j_{k-1} & = & m'+2 \\ i_{k+1} + \cdots + i_r + j_k + \cdots + j_r &=& m''+2 \end{eqnarray*} and define \[ \Psi(q) := y^{i_k-1} \cdot x \cdot \Psi(q') \cdot \xbar \cdot \Psi(q'') \] If we assume (by induction) that \[ \Psi(q') \in {\cal M}_{m'+1}~~~\hbox{and}~~~ \Psi(q'') \in {\cal M}_{m''+1} \] then --- in view of the characterization on ${\cal M}$ given in the previous section --- we have \[ \Psi(q) \in {\cal M}_t ~~~\hbox{where}~~~ t = i_k + 1 + m'+1 + m''+1 = m+1~~, \] as desired. It is a routine task to check that this decomposition and the mapping $\Psi$ can be perfectly reversed, i.e. $\Psi$ maps $Q_m$ bijectively onto ${\cal M}_{m+1}$ for each $m \geq 0$. \end{itemize} Let us illustrate this construction of $\Psi$ by an example. For this purpose we take states $q = (u, \pi) \in Q_m$ with $u$ as above and write it as \[ q \equiv 0^{j_0} \pi(1)^{i_1} 0^{j_1} \pi(2)^{i_2} 0^{j_2} \ldots \pi(r)^{i_r} 0^{j_r} \] i.e. we replace the ones in the 1-blocks of $\overline{u} = 0 \cdot u \cdot 0$ by the corresponding $\pi$-values of the blocks. We let $\Psi$ operate on words of this type. (Note that in this coding we have $\Psi(0^n) = y^{n-1}$ for $n>0$.) Let $m=30$ and $q=(u,\pi)$ with \[ u = 0^1 1^2 0^3 1^1 0^2 1^3 0^1 1^4 0^2 1^1 0^1 1^2 0^2 1^1 0^3 1^1 \in \{0,1\}^{30} \] and \[ \pi = 1\,2\,1\,1\,3\,4\,3\,5 \in {\cal NCP}_8 \] We have \[ k=4~,~ h=2 ~,~ i_k=4 ~,~ \pi' = 1\,2\,1~,~ \pi'' = 1\,2\,1\,3 \] so that \[ q \equiv 0^2 1^2 0^3 2^1 0^2 1^3 0^1 1^4 0^2 3^1 0^1 4^2 0^2 3^1 0^3 5^1 0^1 \] will be mapped onto \[ \Psi(q) = y^3 \cdot x \cdot \Psi(0^2 1^2 0^3 2^1 0^2 1^3 0^1) \cdot \xbar \cdot \Psi(0^2 1^1 0^1 2^2 0^2 1^1 0^3 3^1 0^1) \] Proceeding inductively we arrive at \begin{eqnarray*} \Psi(0^2 1^2 0^3 2^1 0^2 1^3 0^1) &=& y^2 \cdot x \cdot \Psi(0^2 1^2 0^3 2^1 0^2) \cdot \xbar \cdot \Psi(0) \\ &=& y^2 \cdot x \cdot y \cdot x \cdot \Psi(0^2) \cdot \xbar \cdot \Psi(0^3 1^1 0^2) \cdot \xbar \\ &=& y^2 \cdot x \cdot y \cdot x \cdot y \cdot \xbar \cdot x \cdot \Psi(0^3) \cdot \xbar \cdot \Psi(0^2) \cdot \xbar \\ &=& y^2 \cdot x \cdot y \cdot x \cdot y \cdot \xbar \cdot x \cdot y^2 \cdot \xbar \cdot y \cdot \xbar \end{eqnarray*} and \begin{eqnarray*} \Psi(0^2 1^1 0^1 2^2 0^2 1^1 0^3 3^1 0^1) &=& x \cdot \Psi(0^2 1^1 0^1 2^2 0^2) \cdot \xbar \cdot \Psi(0^3 1^1 0^1) \\ &=& x \cdot x \cdot \Psi(0^2) \cdot \xbar \cdot \Psi(0^1 1^2 0^2) \cdot \xbar \cdot x \cdot \Psi(0^3) \cdot \xbar \cdot \Psi(0) \\ &=& x^2 \cdot y \cdot \xbar \cdot y \cdot x \cdot \Psi(0) \cdot \xbar \cdot \Psi(0^2) \cdot \xbar \cdot x \cdot y^2 \cdot \xbar \\ &=& x^2 \cdot y \cdot \xbar \cdot y \cdot x \cdot \xbar \cdot y \cdot \xbar \cdot x \cdot y^2 \cdot \xbar \end{eqnarray*} To conclude this section, we take the example of a Hamiltonian circuit (in matrix form) given at the end of Section 4 and show how it translates into a sequence of Motzkin words (as columns). \begin{center} \unitlength=0.7pt \begin{picture}(220.44,153.10)(4.50,11.45) \put(0,0) { \put(-8.51,-8.44) { \put(17.01,16.96){\makebox(0,0)[cc]{1}} \put(34.01,16.96){\makebox(0,0)[cc]{1}} \put(51.03,16.96){\makebox(0,0)[cc]{1}} \put(68.04,16.96){\makebox(0,0)[cc]{1}} \put(85.04,16.96){\makebox(0,0)[cc]{1}} \put(17.01,33.96){\makebox(0,0)[cc]{0}} \put(34.01,33.96){\makebox(0,0)[cc]{0}} \put(51.03,33.96){\makebox(0,0)[cc]{1}} \put(68.04,33.96){\makebox(0,0)[cc]{0}} \put(85.04,33.96){\makebox(0,0)[cc]{0}} \put(17.01,50.97){\makebox(0,0)[cc]{1}} \put(34.01,50.97){\makebox(0,0)[cc]{1}} \put(51.03,50.97){\makebox(0,0)[cc]{1}} \put(68.04,50.97){\makebox(0,0)[cc]{1}} \put(85.04,50.97){\makebox(0,0)[cc]{1}} \put(17.01,67.99){\makebox(0,0)[cc]{0}} \put(34.01,67.99){\makebox(0,0)[cc]{0}} \put(51.03,67.99){\makebox(0,0)[cc]{1}} \put(68.04,67.99){\makebox(0,0)[cc]{0}} \put(85.04,67.99){\makebox(0,0)[cc]{1}} \put(17.01,84.99){\makebox(0,0)[cc]{1}} \put(34.01,84.99){\makebox(0,0)[cc]{1}} \put(51.03,84.99){\makebox(0,0)[cc]{1}} \put(68.04,84.99){\makebox(0,0)[cc]{0}} \put(85.04,84.99){\makebox(0,0)[cc]{1}} \put(17.01,102.01){\makebox(0,0)[cc]{1}} \put(34.01,102.01){\makebox(0,0)[cc]{0}} \put(51.03,102.01){\makebox(0,0)[cc]{0}} \put(68.04,102.01){\makebox(0,0)[cc]{0}} \put(85.04,102.01){\makebox(0,0)[cc]{1}} \put(17.01,119.01){\makebox(0,0)[cc]{1}} \put(34.01,119.01){\makebox(0,0)[cc]{0}} \put(51.03,119.01){\makebox(0,0)[cc]{1}} \put(68.04,119.01){\makebox(0,0)[cc]{1}} \put(85.04,119.01){\makebox(0,0)[cc]{1}} \put(17.01,136.03){\makebox(0,0)[cc]{1}} \put(34.01,136.03){\makebox(0,0)[cc]{0}} \put(51.03,136.03){\makebox(0,0)[cc]{0}} \put(68.04,136.03){\makebox(0,0)[cc]{0}} \put(85.04,136.03){\makebox(0,0)[cc]{1}} \put(17.01,153.04){\makebox(0,0)[cc]{1}} \put(34.01,153.04){\makebox(0,0)[cc]{1}} \put(51.03,153.04){\makebox(0,0)[cc]{1}} \put(68.04,153.04){\makebox(0,0)[cc]{0}} \put(85.04,153.04){\makebox(0,0)[cc]{1}} } } \put(111,-17.00) { \put(-8.51,-8.44) { \put(17.01,16.96){\makebox(0,0)[cc]{$\bar x$}} \put(34.01,16.96){\makebox(0,0)[cc]{$\bar x$}} \put(51.03,16.96){\makebox(0,0)[cc]{$\bar x$}} \put(68.04,16.96){\makebox(0,0)[cc]{$\bar x$}} \put(85.04,16.96){\makebox(0,0)[cc]{$\bar x$}} \put(17.01,33.96){\makebox(0,0)[cc]{$x$}} \put(34.01,33.96){\makebox(0,0)[cc]{$x$}} \put(51.03,33.96){\makebox(0,0)[cc]{$\bar x$}} \put(68.04,33.96){\makebox(0,0)[cc]{$\bar x$}} \put(85.04,33.96){\makebox(0,0)[cc]{$\bar x$}} \put(17.01,50.97){\makebox(0,0)[cc]{$\bar x$}} \put(34.01,50.97){\makebox(0,0)[cc]{$\bar x$}} \put(51.03,50.97){\makebox(0,0)[cc]{$x$}} \put(68.04,50.97){\makebox(0,0)[cc]{$y$}} \put(85.04,50.97){\makebox(0,0)[cc]{$x$}} \put(17.01,67.99){\makebox(0,0)[cc]{$x$}} \put(34.01,67.99){\makebox(0,0)[cc]{$x$}} \put(51.03,67.99){\makebox(0,0)[cc]{$\bar x$}} \put(68.04,67.99){\makebox(0,0)[cc]{$y$}} \put(85.04,67.99){\makebox(0,0)[cc]{$y$}} \put(17.01,84.99){\makebox(0,0)[cc]{$\bar x$}} \put(34.01,84.99){\makebox(0,0)[cc]{$\bar x$}} \put(51.03,84.99){\makebox(0,0)[cc]{$x$}} \put(68.04,84.99){\makebox(0,0)[cc]{$x$}} \put(85.04,84.99){\makebox(0,0)[cc]{$y$}} \put(17.01,102.01){\makebox(0,0)[cc]{$x$}} \put(34.01,102.01){\makebox(0,0)[cc]{$y$}} \put(51.03,102.01){\makebox(0,0)[cc]{$x$}} \put(68.04,102.01){\makebox(0,0)[cc]{$x$}} \put(85.04,102.01){\makebox(0,0)[cc]{$y$}} \put(17.01,119.01){\makebox(0,0)[cc]{$y$}} \put(34.01,119.01){\makebox(0,0)[cc]{$y$}} \put(51.03,119.01){\makebox(0,0)[cc]{$y$}} \put(68.04,119.01){\makebox(0,0)[cc]{$\bar x$}} \put(85.04,119.01){\makebox(0,0)[cc]{$y$}} \put(17.01,136.03){\makebox(0,0)[cc]{$y$}} \put(34.01,136.03){\makebox(0,0)[cc]{$\bar x$}} \put(51.03,136.03){\makebox(0,0)[cc]{$y$}} \put(68.04,136.03){\makebox(0,0)[cc]{$y$}} \put(85.04,136.03){\makebox(0,0)[cc]{$y$}} \put(17.01,153.04){\makebox(0,0)[cc]{$y$}} \put(34.01,153.04){\makebox(0,0)[cc]{$x$}} \put(51.03,153.04){\makebox(0,0)[cc]{$y$}} \put(68.04,153.04){\makebox(0,0)[cc]{$y$}} \put(85.04,153.04){\makebox(0,0)[cc]{$y$}} \put(17.01,170.05){\makebox(0,0)[cc]{$y$}} \put(34.01,170.05){\makebox(0,0)[cc]{$x$}} \put(51.03,170.05){\makebox(0,0)[cc]{$y$}} \put(68.04,170.05){\makebox(0,0)[cc]{$x$}} \put(85.04,170.05){\makebox(0,0)[cc]{$x$}} \multiput(8.51,161.54)(17.01,0){5} }} \put(103.60,77.00){\makebox(0,0)[cc]{{\boldmath $\simeq$~~~}}} \end{picture} \end{center} \vskip0.5cm \caption{A (matrix) Hamiltonian circuit and its Motzkin translation}\label{012example} \section{Compatible vectors again} In this section we point out a simplification that is possible in both construcing the automata ${\cal A}_m$ and computing with them. This is due to a simple parity argument that is inherent in the concept of compatible vectors (or words), as introduced in Section 2. Consider the following simple transition system on four states, named 00, 01, 10, and 11. \begin{center} \setlength{\unitlength}{0.005000in}% \begin{picture}(498,369)(124,420) \thicklines \put(370,450){\circle*{28}} \put(532,611){\circle*{28}} \put(370,770){\circle*{28}} \put(210,610){\circle*{28}} \put(370,740){\vector( 0, 1){ 0}} \put(370,740){\vector( 0,-1){260}} \put(225,595){\vector(-1, 1){ 0}} \put(225,595){\vector( 1,-1){130}} \put(515,595){\vector( 1, 1){ 0}} \put(515,595){\vector(-1,-1){130}} \put(355,755){\vector( 1, 1){ 0}} \put(355,755){\vector(-1,-1){130}} \put(385,755){\vector(-1, 1){ 0}} \put(385,755){\vector( 1,-1){130}} \put(570,620){\oval(100,20)[r]} \put(570,610){\vector(-1,0){0}} \put(170,600){\oval(100,20)[l]} \put(170,590){\vector(1,0){0}} \put(400,780){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 00}}} \put(540,560){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 10}}} \put(160,640){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 01}}} \put(400,420){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 11}}} \end{picture} \end{center} \caption{The transition system for compatible vectors} \vskip0.5cm To each walk $w$ of length $m$ in this transition graph, given by the sequence $w = w_0 , w_1 , \ldots , w_n$ of states it visits, we associate two words of length $m+1$ over $\{0,1\}$ : \begin{eqnarray*} u_w &:=& ~ \hbox{the concatenation of the first components of}~w_0,w_1,\ldots,w_m \\ v_w &:=& ~ \hbox{the concatenation of the second components of}~w_0,w_1,\ldots,w_m \end{eqnarray*} It is easy to see that the pairs $(u_w,v_w)$ of words of the same length thus generated are precisely the pairs of compatible vectors as defined in Section 2. For ${\cal T}_m$ and ${\cal A}_m$ we need to consider (and to produce) all compatible pairs $(\overline{u},\overline{v}) = (0 \cdot u \cdot 0,0\cdot v\cdot 0)$ with $u,v \in \{0,1\}^m$ --- i.e. we have to consider walks of length $m+1$ starting and ending in state 00. Note that each walk of that kind has an {\em even} number of transitions to or from state 11. Legal transitions between the other three states, however, have the property that the generate a factor 00 either in $u_w$ or in $v_w$, but not in both words. This last observation has the following consequence: call $u \in \{0,1\}^m$ an {\em even} vector if the word $\overline{u} = 0 \cdot u \cdot 0$ contains an even number of factors 00, otherwise $u$ is {\em odd}. Now, by the previous remark: \begin{quote} let $u,v \in \{0,1\}^m$ be vectors such that $\overline{u}$ and $\overline{v}$ are compatible, then \begin{itemize} \item[--] if $m$ is odd, then either both of $u,v$ are even or both are odd \item[--] if $m$ is even, then one of $u,v$ is even and the other one is odd \end{itemize} \end{quote} We draw the following consequences: \begin{itemize} \item if $m$ is odd, then $0^m$ is even and only states $q=(u,\pi) \in Q_m$ with even $u$ are reachable from $0^m$ in ${\cal T}_m$. Hence all the states $q=(u,\pi)$ with $u$ odd can be eliminated from the construction. \item if $m$ is even, then $0^m$ is odd and we need an even number of transitions for a walk that leads from $0^m$ back to $0^m$, since successive states must alternate in ``parity''. \end{itemize} The last remark reflects the well known fact that $G_{m,n}^*$ has a Hamiltonian circuit if and only if not both $m$ and $n$ are even. The next to last remark is illustrated by our example for $m=3$: there are $\hbox{\em mot}_4 = 9$ states in ${\cal T}_3$, namely \begin{eqnarray*} &&(000,\emptyset)~,~(001,1)~,~(010,1)~,~(100,1)~,~ (101,11)~,~(101,12)~,~(111,1)\\ &&(011,1)~,~(110,1) \end{eqnarray*} of which the last two are ``odd'', hence unreachable from any of the seven ``even'' states, see Fig.~\ref{auto}. The precise evaluation of the size of the set of unreachable states in the case of odd $m$ will be given elsewhere. We conclude this section with a {\em conjecture} that has been verified by our computations up to $m=12$, but for which we are unable to give a proof in general: \begin{itemize} \item in the automaton ${\cal A}_m$, all accessible states are also coaccessible, i.e. from every state, which is accessible from the initial state $\alpha$, there is at least one path that leads to the final state $\omega$. \end{itemize} If this conjecture were true in general, the minimization procedure {\`a la Nerode} for the automaton ${\cal A}_m$ that we employ prior to computing the generating function (see the end of the following section) could be simplified considerably by just identifying states that have the same set of successor states. \section{Computing the generating function $h_m(z)$} From Section 5 we know that the generating function $h_m(z) = \sum_{n \geq 1} h_{m,n}\,z^n$ is rational. In this section we informally discuss a way of actually computing $h_m(z)$, at least for small values of $m$. As mentioned in the introduction, a program has been written which carries out these computations for arbitrary $m$ --- in principle. We have explicitly computed the automata ${\cal A}_m$, recognizing the Hamiltonian language $L_m$, for $m \leq 12$. Some of our results are presented in the concluding section. Needless to say that the exponential growth of ${\cal A}_m$ (in terms of the number of states, as made precise by the Motzkin-coding in Section 7) puts severe bounds on practical computations. A standard way of computing $h_m(z)$ proceeds as follows: one takes the automaton ${\cal A}_m$ and represents it by the transition matrix \[ {\bf A}_m = \left( a_{p,q}^{(m)} \right)_{p,q \in Q''} ~~\hbox{where}~~ a_{p,q}^{(m)} = \cases{ 1 & if $\delta(p,v)=q$ for some $v \in \Sigma_m$ \cr 0 & else} \] with $Q_m'' = Q_m' \setminus \{\alpha, \rho\}$. Note that, by the definition of ${\cal A}_m$, there is at most one $v \in \Sigma_m$ such that $\delta(p,v)=q$, for any $p,q, \in Q_m''$. Let ${\bf s}$ denote the vector of states immediately acessible from the initial state $\alpha$ of ${\cal A}_m$ : \[ {\bf s} = \left( s_p \right)_{p \in Q_m''} ~~\hbox{where}~~ s_p = \cases{ 1 & if $\delta(\alpha,u) = p = (u,\pi_{\alpha})$ for some $u \in \Sigma^*$ \cr 0 & else} \] and, correspondingly, let ${\bf t}$ denote the vector of terminal states \[ {\bf t} = \left( t_q \right)_{q \in Q_m''} ~~\hbox{where}~~ t_q = \cases{ 1 & if $q \in \Omega$ \cr 0 & else} \] Then, for any $n \geq 0$, \[ h_{m,n+1} = {\bf s} \cdot {\bf A}_m^n \cdot {\bf t}^{\tt T} \] and thus \[ h_m(z) = \sum_{n \geq 1} h_{m,n}\,z^n = z \cdot {\bf s} \cdot ({\bf I}- z \, {\bf A_m})^{-1} \cdot {\bf t}^{\tt T} \] where ${\bf I}$ denotes an identity matrix of the same format as ${\bf A}_m$. Inverting the matrix ${\bf I} - z \, {\bf A}_m$ is feasible only for very moderate values of $m$. One way to compute $h_m(z)$ for larger values of $m$ is by producing sufficiently many initial coefficients $h_{m,1} \,,\,h_{m,2}\,,\,h_{m,3}\,,\, \ldots$ using the matrix ${\bf A}_m$ and its powers, and then employing the techniques of Pad\'e approximation. In particular, the size of the matrix ${\bf A}_m$ gives us an upper bound on the degree of the denominator polynomial of $h_m(z)$, so that we know in advance when to stop the approximation procedure. A slightly more sophisticated approach that we have experimented successfully with for the purpose of computing $h_m(z)$ is a combination of modular arithmetic and the Berlekamp-Massey algorithm (see e.g. Section 8.6 in \cite{ln}): we compute the residues of the sequence $h_{m,1} \,,\,h_{m,2}\,,\,h_{m,3}\,,\, \ldots$ modulo various (not too big) primes $p$ and apply the Berlekamp-Massey algorithm over the finite fields $GF(p)$ in parallel. This gives a very fast way of determining the true degree of the denominator polynomial of $h_m(z)$. The numerator and denominator polynomial themselves can then be obtained by Chinese remaindering techniques. A more detailed description of this approach will be given elsewhere. One more aspect must be mentioned: the techniques just sketched will not be applied to the automaton ${\cal A}_m$ and its transition matrix ${\bf A}_m$ themselves. We will, of course, first apply standard minimization techniques from automata theory in order to cut down the size of the matrices to be handled, by eliminating inaccessible states (remember Section 8) and identifying equivalent states. The minimal automaton $\tilde{\cal A}_m$ obtained from ${\cal A}_m$ gives us a transition matrix $\tilde{\bf A}_m$ considerably smaller in size, thus leading to a much better {\em \`a priori} bound on the degree of the numerator polynomial of the $h_m(z)$. Nonetheless, our numerical results seem to indicate that the growth rates of the number of states after minimization is of the same order as the one for the automata ${\cal A}_m$ themselves. \section{Numerical results} \subsection{The generating functions $h_m(z)/z$ up to $m=8$}\label{gfns} We give the rational generating functions $h_m(z)/z$ for $1 \leq m \leq 6$ and the degrees of the numerator and denominator polynomials for $m = 7,8$. For these two latter cases the polynomials have been computed explicitly and are available on request, as are (very large, with $n$ in the thousands) initial segments of the coefficient sequences $h_{m,n}~(n \geq 1)$ up to $n = 12$. Note that for $m$ even the generating function $h_m(z)/z$ is actually ``even'' in the sense of being a function of $z^2$. This follows from the parity argument given in Section 8. \noindent $m = 1$~: \[ \frac{1}{-z + 1} = 1 + z + z^2 + z^3 + z^4 + \ldots \] $m = 2$~: \[ \frac{1}{-2z^{2} + 1} = 1 + 2z^2+4z^4 + 8 z^6 + 16 z^8 + \ldots \] $m = 3$~: \[ \frac{1}{-z^{4} + 2z^{3} -2z^{2} -2z + 1} = 1 + 2z + 6 z^2 + 14 z^3 + 37 z^4 + 92 z^5 + 236 z^6 + \ldots \] $m = 4$~: \[ \frac{3z^{2} + 1}{-2z^{6} - 11z^{2} + 1} = 1 + 14 z^2 + 154 z^4 + 1696 z^6 + 18684 z^8 + \ldots \] $m = 5$~: % \[ \frac{z^{12} - 2z^{11} + 4z^{10} + 9z^{9} - 15z^{8} + 3z^{7} - 3z^{5}} % {-2z^{14} + 4z^{13} - 28z^{12} - 42z^{11} % + 82z^{10} + 8z^{9} - 118z^{8} + 66z^{7}} \] % \[ \dots \frac{+\enspace 24z^{4} - 24z^{3} + 3z^{2} - z + 1} % {+\enspace 35z^{6} - 90z{5} - 12z^{4} + 63z^{3} - 14z^{2} - 5z + 1 } \] \[ \frac{ \left(z-1\right) (z^{11}-z^{10}+3\,z^{9}+12\,z^{8}-3\,z^{7}} {-2z^{14} + 4z^{13} - 28z^{12} - 42z^{11} + 82z^{10} + 8z^{9} - 118z^{8} + 66z^{7}} \] \[ \cdots \frac{-\enspace 3\,z^{4}+21\,z^{3}-3\,z^{2}-1)} {+\enspace 35z^{6} - 90z{5} - 12z^{4} + 63z^{3} - 14z^{2} - 5z + 1 } \] \[ = 1 + 4 z + 37 z^2 + 154 z^3 + 1072 z^4 + 5320 z^5 + 32675 z^6 + 175294 z^7 + 1024028 z^8 + \ldots \] $m = 6$: \[ \frac{96z^{32} - 48z^{30} - 4592z^{28} - 9162z^{26} + 64012z^{24} - 252197z^{22} } {-144z^{36} \!-\! 1728z^{34} \!+\! 5972z^{32}\!-\! 17732z^{30} \!-\! 92790z^{28} \!+\! 178842z^{26} \!+ \! 1036420z^{24} } \] \[ \cdots \frac{+\enspace 643288z^{20} - 797154z^{18} + 453054z^{16} - 40229z^{14} } {-\enspace 3390877z^{22} + 4008954z^{20} - 2681994z^{18} + 1690670z^{16} - 1251439z^{14} } \] \[ \cdots \frac{-\enspace 111603z^{12} + 87046z^{10} - 33250z^{8} + 6525z^{6} - 568z^{4} + 7z^{2} + 1} {+\enspace 815141z^{12} - 386724z^{10} + 116734z^{8} - 20403z^{6} + 1932z^{4} - 85z^{2} + 1 } \] \[ = 1 + 92 z^2 + 5320 z^4 + 301384 z^6 + 17066492 z^8 + 966656134 z^{10} + \ldots \] \bigskip \noindent $m = 7$~: degree of numerator~: 64, degree of denominator~: 66. \[ 1 + 8z + 236 z^2 + 1696 z^3 + 32675 z^4 + 301384 z^5 + 4638576 z^6 + 49483138 z^7 + \ldots \] \bigskip \noindent $m = 8$~: degree of numerator~: 206, degree of denominator~: 208. \[ 1 + 596 z^2 + 175294 z^4 + 49483138 z^6 + 13916993782 z^8 + 3913787773536 z^{10} + \ldots \] The reader may check the obvious property $h_{m,n} = h_{n,m}$ from these data. \subsection{Data of the computed automata (matrices)}\label{counts} \begin{minipage}{7.5cm} \begin{tabular}{|r|r|r||r|r|} \hline & \multicolumn{2}{c||}{ num.~of states } & \multicolumn{2}{c|} { num.~of transitions } \\ \hline m & {\Huge \phantom{a} } ${\cal A}_m$ & $\tilde {\cal A}_m$ & ${\cal A}_m$ & $\tilde {\cal A}_m$ \\ \hline 1 & 3 & 3 & 3 & 3 \\ 2 & 5 & 4 & 6 & 5 \\ 3 & 10 & 6 & 20 & 14 \\ 4 & 22 & 13 & 64 & 44 \\ 5 & 52 & 22 & 224 & 121 \\ 6 & 128 & 74 & 803 & 543 \\ 7 & 324 & 117 & 2966 & 1396 \\ 8 & 836 & 461 & 11133 & 7349 \\ 9 & 2189 & 728 & 42409 & 18285 \\ 10 & 5799 & 3094 & 163295 & 105154 \\ 11 & 15512 & 4828 & 634700 & 255196 \\ 12 & 41836 & 21552 & 2486247 & 1556317 \\ % 1 & 1 & 1 & 1 & 1 \\ % 2 & 3 & 2 & 4 & 3 \\ % 3 & 8 & 4 & 16 & 10 \\ % 4 & 20 & 11 & 58 & 38 \\ % 5 & 50 & 20 & 214 & 111 \\ % 6 & 126 & 72 & 787 & 527 \\ % 7 & 322 & 115 & 2940 & 1370 \\ % 8 & 834 & 459 & 11091 & 7307 \\ % 9 & 2187 & 726 & 42341 & 18217 \\ % 10 & 5797 & 3092 & 163185 & 105044 \\ % 11 & 15510 & 4826 & 634522 & 255018 \\ % 12 & 41834 & 21550 & 2485959 & 1556029 \\ \hline \end{tabular} \end{minipage} \begin{minipage}{5.0cm} \begin{itemize} \item[ ] The number $\sharp Q_m'$ of states of ${\cal A}_m$ equals $\hbox{\em mot}_m+1$. The size $\sharp Q_m''$ of ${\bf A}_m$ equals $\hbox{\em mot}_m-1$. Similarly, $\tilde {\cal A}_m$ is bigger by 2 than $\tilde {\bf A}$. % \item The number of transitions of ${\cal A}_m$ and $\tilde {\cal A}_m$ % equals the sum of the elements of the corresponding % matrix. This is % (in the case of $A_m$ only) the number of positive entries, i.e. 1's. \end{itemize} \end{minipage} \subsection{Computation times and memory use}\label{messungen} \begin{minipage}{4.5cm} \begin{tabular}{|c|r|r|} \hline m & cpusec & bytes\\ \hline 1 & .0394 & 24 \\ 2 & .0448 & 46 \\ 3 & .0656 & 150 \\ 4 & .0946 & 254 \\ 5 & .9802 & 2166 \\ 6 & 20.4996 & 21920 \\ 7 & 2189.6090 & 350512 \\ 8 & 2251385.5 & 26895646 \\ \hline \end{tabular} \end{minipage} \hfill \begin{minipage}{7.7cm} These are the average computation times for the generating functions. The bytes column shows the maximum memory need of the main datastructures of the program. The computations reported here have been done on a {\sc sparc 2} (30MHz). The computation for $m=8$ was performed on a {\sc sparc 10}. \end{minipage} \newpage \begin{thebibliography}{99} \bibitem{br} Berstel, Jean and Reutenauer, Christophe~: {\em Rational series and their languages}. Springer, Berlin 1988. \bibitem{hu} Hopcroft, John E.~and Ullman, Jeffrey D.~: {\em Introduction to Automata Theory, Languages and Computation}. Addison-Wesley 1979. \bibitem{kreweras} Kreweras, Germain~: D\'enombrement des Cycles Hamiltoniens dans un Rectangle Quadrill\'e. {\em European Journal of Combinatorics} {\bf 13} (1992), 473-467. \bibitem{kwong} Kwong, Harris~: Enumeration of Hamiltonian Cycles in $P_{4}\times P_{n}$ and $P_{5}\times P_{n}$. {\em Ars Combinatoria} {\bf 33} (1992), 87-96. \bibitem{rogers} Kwong, Harris and Rogers, D.~G.~: A Matrix Method for Counting Hamiltonian Cycles on Grid Graphs. To appear in {\em European Journal of Combinatorics}. \bibitem{ln} Lidl, Rudolf and Niederreiter, Harald~: {\em Finite Fields} (Encyclopedia of Mathematics and its Applications, vol. 20), Cambridge University Press, 1984. \bibitem{stanley} Stanley, Richard P.~: {\em Enumerative Combinatorics}. Wadsworth \& Brooks/Cole, Monterey, California 1986. \bibitem{stoyan} Stoyan, Robert~: {\em Anzahl der Hamilton-Kreise in rechteckigen Gittern}. Studienarbeit im Fach Informatik an der Universit\"at Erlangen-N\"urnberg, 1993. \end{thebibliography} \end{document}