A193346 Number of (directed) Hamiltonian paths on the n X n X n grid graph.

1, 144, 4960608, 55493434415544000

Offset

1,2

Comments

A general purpose matrix-transfer method can be used to compute values up to a(4). Using a diagonal sweep from one corner to the opposite corner will help to reduce the number of states. - Andrew Howroyd, Dec 20 2015

Schram & Schiessel (see Links) quote a different result for a(4): 27747833510015886 undirected Hamiltonian walks, which would double to 55495667020031772 directed Hamiltonian walks. However, that number is not divisible by 8 and thus cannot be correct. - Arun Giridhar, Dec 15 2015

Links

Table of n, a(n) for n=1..4.

Raoul D. Schram and Helmut Schiessel, Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 46 (2013), 485001.

Raoul D. Schram and Helmut Schiessel, Corrigendum: Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 49 (2016), 369501.

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Hamiltonian Path

Index entries for sequences related to graphs, Hamiltonian

Example

For n = 1, there is a trivial Hamiltonian path of length 0.
For n = 2, the 144 paths fall in three different equivalence classes. Two of the three classes can be derived by taking a Hamiltonian cycle on a cube and deleting a single edge. The third class is a spiral path that ends at the opposite corner from its starting point.

Crossrefs

Cf. A003763, A096969.

Sequence in context: A159436 A318197 A362214 * A003837 A013863 A371624

Adjacent sequences: A193343 A193344 A193345 * A193347 A193348 A193349

Keyword

nonn,hard,more,bref

Author

Eric W. Weisstein, Jul 23 2011

Extensions

a(4) from Andrew Howroyd, Nov 15 2015

a(1) corrected by Arun Giridhar, Dec 20 2015

Status

approved