A391478 Triangle read by rows: T(m,n) is the number of Hamiltonian cycles on m X n torus where each step goes north or east or northeast; 2 <= n <= m.

6, 12, 18, 24, 74, 272, 48, 192, 560, 3900, 96, 408, 3596, 29017, 129024, 192, 1372, 17928, 137301, 1204399, 11050620, 384, 3834, 54412, 472684, 6880196, 58009240, 1211010880, 768, 10182, 190760, 2319015, 38998434, 1028370181, 22313235168, 269574347232, 1536, 31742, 706004, 17364875, 400630520, 14140168616, 301038678872, 6943956403769, 160570443266120

Offset

2,1

Comments

We require m>=2 and n>=2, otherwise an m X n torus is degenerate. We have T(m,n)=T(n,m) because north and east can be interchanged. Only the entries below or on the diagonal are listed; thus, T(2,2)=6, T(3,2)=12, T(3,3)=18, T(4,2)=24, T(4,3)=74, etc.

References

D. E. Knuth, Hamiltonian paths and cycles. (Draft of Section 7.2.2.4 of The Art of Computer Programming, a work in progress.)

Links

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

Formula

From Filip Stappers, Dec 27 2025: (Start)

T(2,n) = 3*2^(n-1).

T(3,n) = (3^(n+1) + 2^(n+2) + 5*(-1)^n)/6 for n == 0 (mod 3).

T(3,n) = (3^(n+1) + 13*2^n - 7*(-1)^n)/6 for n != 0 (mod 3). (End)

Example

The a(7)=T(4,3)=T(3,4)=74 solutions break down into 10 nonisomorphic cycles, A-J, because we can add a constant (mod 3 in the first component and mod 4 in the second) to get essentially the same cycle.
A: 00 01 02 03 20 21 22 23 10 11 12 13 00 (4 solutions).
B: 00 01 02 23 10 11 12 03 20 21 22 13 00 (4 solutions).
C: 00 01 21 11 02 22 12 13 03 23 20 10 00 (12 solutions).
D: 00 01 21 12 03 20 10 11 02 22 23 13 00 (12 solutions).
E: 00 01 21 12 03 20 11 02 22 23 13 10 00 (12 solutions).
F: 00 01 21 12 03 23 20 10 11 02 22 13 00 (12 solutions).
G: 00 01 21 12 03 23 20 11 02 22 13 10 00 (12 solutions).
H: 00 01 22 23 10 11 02 03 20 21 12 13 00 (2 solutions).
I: 00 20 10 01 21 11 02 22 12 03 23 13 00 (3 solutions).
J: 00 21 12 03 20 11 02 23 10 01 22 13 00 (1 solution).
Triangle begins:
    6;
   12,   18;
   24,   74,   272;
   48,  192,   560,   3900;
   96,  408,  3596,  29017,  129024;
  192, 1372, 17928, 137301, 1204399, 11050620;
  384, 3834, 54412, 472684, 6880196, 58009240, 1211010880;
  ...

Crossrefs

Cf. A007283, A324604, A324605.

Sequence in context: A073455 A279894 A209309 * A020333 A044831 A033003

Adjacent sequences: A391475 A391476 A391477 * A391479 A391480 A391481

Keyword

nonn,tabl

Author

Don Knuth, Dec 10 2025

Extensions

T(9,n) and T(10,n) from Filip Stappers, Dec 27 2025

Status

approved