A384173 Number of Hamiltonian paths from NW to SW corners in an n X n grid reduced for symmetry, i.e., where reflection about the x-axis is not counted as distinct.

1, 1, 1, 5, 43, 897, 44209, 4467927, 1043906917, 506673590576, 555799435739334, 1284472450789974196, 6625529679919810063544, 72597408139909172033687226, 1762085630816152820582838187465, 91326629994353561722347679614188407

Offset

1,4

Comments

When n is odd there are no symmetric Hamiltonian paths from NW to SW corners, and therefore a(n) = A000532(n)/2.

References

J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.

J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.

Links

Oliver R. Bellwood, Table of n, a(n) for n = 1..21

Oliver R. Bellwood, Heitor P. Casagrande, and William J. Munro, Fractal Path Strategies for Efficient 2D DMRG Simulations, arXiv:2507.11820 [cond-mat.str-el], 2025. See p. 4.

Formula

a(n) = A000532(n)/2 for odd n.

a(n) = (A000532(n) + A331001(n))/2 for even n.

Example

The two paths of A000532(3) = 2 are equivalent under reflection about the x-axis:
  + - + - +
          |
  + - +   +
  |   |   |
  +   + - +
  +   + - +
  |   |   |
  + - +   +
          |
  + - + - +

Crossrefs

Cf. A000532, A209077, A265914, A331001, A363577.

Sequence in context: A160450 A114604 A085098 * A271679 A350875 A099794

Adjacent sequences: A384170 A384171 A384172 * A384174 A384175 A384176

Keyword

nonn,walk

Author

Oliver R. Bellwood, May 21 2025

Status

approved