login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph. 10
1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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
CROSSREFS
Sequence in context: A080273 A096404 A111824 * A285740 A174506 A109216
KEYWORD
nonn,walk
AUTHOR
Don Knuth, Jul 26 2008
EXTENSIONS
New name from Eric W. Weisstein, May 06 2019
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)