A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

1, 4, 20, 276, 4324, 229348, 13535280, 3023313284, 745416341496, 730044829512632, 786671485270308848, 3452664855804347354220, 16652005717670534681315580, 331809088406733654427925292528, 7263611367960266490262600117251524

Offset: 1

Author

David Bevan, Jul 19 2006

Keywords

• nonn
• walk

Examples

			From _Robert FERREOL_, Apr 03 2019: (Start)
a(3) = 20:
there are 4 paths similar to
  + - + - +
          |
  + - + - +
  |
  + - + - +
8 paths similar to
  + - + - +
  |       |
  +   + - +
  |   |
  +   + - +
and 8 paths similar to
  + - + - +
  |       |
  +   +   +
  |   |   |
  +   + - +
(End)
		

Links

• Jesper L. Jacobsen, Table of n, a(n) for n = 1..17
• 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.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Hamiltonian Path
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

Main diagonal of A332307.

Cf. A003685, A003695, A003778, A145402.

Cf. A003763, A000532, A001184, A145157, A271507, A007764, A121785, A121789.

Formula

a(n) = A096969(n) / 2 for n > 1.

Extensions

More terms from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007