login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A321172 Triangle read by rows: T(m,n) = number of Hamiltonian cycles on m X n grid of points (m >= 2, 2 <= n <= m). 7
1, 1, 0, 1, 2, 6, 1, 0, 14, 0, 1, 4, 37, 154, 1072, 1, 0, 92, 0, 5320, 0, 1, 8, 236, 1696, 32675, 301384, 4638576, 1, 0, 596, 0, 175294, 0, 49483138, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,5

COMMENTS

Orientation of the path is not important; you can start going either clockwise or counterclockwise. Paths related by symmetries are considered distinct.

The m X n grid of points when drawn forms a (m-1) X (n-1) rectangle of cells, so m-1 and n-1 are sometimes used as indices instead of m and n (see, e. g., Kreweras' reference below).

These cycles are also called "closed non-intersecting rook's tours" on m X n chess board.

LINKS

Table of n, a(n) for n=2..37.

Robert Ferréol, The T(4,5)=14 hamiltonian cycles on 4 X 5 square grid of points; the T(5,6) = 154 cycles on 5 X 6 grid are reduced to 44 different forms.

Germain Kreweras, Dénombrement des cycles hamiltoniens dans un rectangle quadrillé, European Journal of Combinatorics, Volume 13, Issue 6 (1992), page 476.

Robert Stoyan, Volker Strehl, Enumeration of Hamiltonian Circuits in Rectangular Grids, Séminaire Lotharingien de Combinatoire, B34f (1995), 21 pp.

Eric Weisstein's World of Mathematics, Grid Graph

FORMULA

T(m,n) = T(n,m).

T(2m+1,2n+1) = 0.

T(2n,2n) = A003763(n).

T(n,n+1) = T(n+1,n) = A222200(n).

G. functions , G_m(x)=Sum {n>=0} T(m,n-2)*x^n after Stoyan's link p. 18 :

G_2(x) = 1/(1-x) = 1+x+x^2+...

G_3(x) = 1/(1-2*x^2) = 1+2*x^2+4*x^4+...

G_4(x) = 1/(1-2*x-2*x^2+2*x^3-x^4) = 1+2*x+6*x^2+...

G_5(x) = (1+3*x^2)/(1-11*x^2-2*x^6) = 1+14*x^2+154*x^4+...

EXAMPLE

T(5,4)=14 is illustrated in the links above.

Table starts:

=================================================================

m\n|  2    3      4       5         6           7            8

---|-------------------------------------------------------------

2  |  1    1      1       1         1           1            1

3  |  1    0      2       0         4           0            8

4  |  1    2      6      14        37          92          236

5  |  1    0     14       0       154           0         1696

6  |  1    4     37     154      1072        5320        32675

7  |  1    0     92       0      5320           0       301384

8  |  1    8    236    1696     32675      301384      4638576

The table is symmetric, so it is completely described by its lower-left half.

PROG

(Python)

# Program due to Laurent Jouhet-Reverdy

def cycle(m, n):

     if (m%2==1 and n%2==1): return 0

     grid = [[0]*n for _ in range(m)]

     grid[0][0] = 1; grid[1][0] = 1

     counter = 0; stop = m*n-1

     def run(i, j, nb_points):

         for ni, nj in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)] :

             if  0<=ni<=m-1 and 0<=nj<=n-1 and grid[ni][nj]==0 and (ni, nj)!=(0, 1):

                 grid[ni][nj] = 1

                 run(ni, nj, nb_points+1)

                 grid[ni][nj] = 0

             elif (ni, nj)==(0, 1) and nb_points==stop:

                 counter += 1

     run(1, 0, 2)

     return counter

L=[]; n=7#maximum for a time < 1 mn

for i in range(2, n):

    for j in range(2, i+1):

       L.append(cycle(i, j))

print(L)

CROSSREFS

Cf. A003763 (bisection of main diagonal), A222200 (subdiagonal), A006864, A006865, A270273.

Sequence in context: A175474 A271877 A021387 * A127508 A244814 A090185

Adjacent sequences:  A321169 A321170 A321171 * A321173 A321174 A321175

KEYWORD

nonn,tabl,more

AUTHOR

Robert FERREOL, Jan 10 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 2 16:47 EDT 2020. Contains 335404 sequences. (Running on oeis4.)