|
| |
|
|
A007764
|
|
Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.
|
|
13
|
|
|
|
1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
The length of the path varies.
Comments from Daniel Forgues, Jan 03 2011: (Start) For n=14, there exists at least one Hamiltonian path from (0,0) to (14,14). For which n do we have at least one Hamiltonian path?
Lattice graphs have their values located at the corners of grid cells. Lattice graph edges join the corners of grid cells.
Grid graphs have their values located at the centers of grid cells. Grid graph edges join the centers of grid cells.
An (m+1) X (n+1) square lattice constitutes the cell corners (coordinates (0,0) to (m,n)) of an m X n square grid.
Number of self-avoiding walks from (0,0) to (n,n), n >= 0, of a (n+1) X (n+1) square lattice.
Since rooks move from centers to centers of adjacent grid cells, should the definition say? "Number of nonintersecting (or self-avoiding) rook paths joining opposite corner cells of an (n+1) X (n+1) grid." (End)
|
|
|
REFERENCES
|
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331-339.
D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 27-28.
D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).
|
|
|
LINKS
|
I. Jensen, H. Iwashita, R. Spaans, Table of n, a(n) for n = 0..25 (I. Jensen computed terms 0 to 19, H. Iwashita computed 20 and 21, R. Spaans computed 22 to 24, and H. Iwashita computed 25)
M. Bousquet-Melou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtube-animation demonstrating this sequence. In Japanese with English translation]
S. R. Finch, Self-Avoiding-Walk Connective Constants
H. Iwashita, J. Kawahara, and S. Minato, ZDD-Based Computation of the Number of Paths in a Graph
H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions
I. Jensen, Series Expansions for Self-Avoiding Walks
OEIS Wiki, Self-avoiding_walks
Ruben Grønning Spaans, C program
Eric Weisstein's World of Mathematics, Self-Avoiding Walk
|
|
|
EXAMPLE
|
Suppose we start at (0,0) and end at (n-1,n-1). Let U, D, L, R denote steps that are up, down, left, right.
a(2) = 2: UR or RU.
a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.
|
|
|
CROSSREFS
|
Sequence in context: A134716 A006023 A039748 * A015195 A051421 A182162
Adjacent sequences: A007761 A007762 A007763 * A007765 A007766 A007767
|
|
|
KEYWORD
|
nonn,walk,hard,more,nice
|
|
|
AUTHOR
|
David Radcliffe and D. E. Knuth.
|
|
|
EXTENSIONS
|
Computed to n=11 by John Van Rosendale in 1981, extended to n=12 by D. E. Knuth, Dec 07 1995.
Extended to n=19 by M. Bousquet-Melou, A. J. Guttmann and I. Jensen
Extended to n=21 using ZDD technique based on Knuth's The Art of Computer Programming (exercise 225 in 7.1.4) by H. Iwashita, J. Kawahara, and S. Minato, Sep 18 2012
Extended to n=24 using state space compression (with rank/unrank) and dynamic programming (based in I. Jensen) by Ruben Grønning Spaans, Feb 22 2013
Extended to n=25 by Hiroaki Iwashita, Apr 11 2013
|
|
|
STATUS
|
approved
|
| |
|
|
