A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418

Offset: 1

Author

Don Knuth, Jul 26 2008

Keywords

• nonn
• walk

Comments

Or, number of Hamiltonian cycles in the graph P_n X P_n (strong product of two paths of length n-1).

If the direction of the tour is to be taken into account, the numbers for n > 1 must be multiplied by 2 (see A140521).

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

References

• D. E. Knuth, The Art of Computer Programming, Section 7.1.4, in preparation.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..16 [From Pettersson 2014]
• Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
• Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015.
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, King Graph
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

Cf. A001230, A140521.

Extensions

New name from Eric W. Weisstein, May 06 2019