

A007764


Number of nonintersecting (or selfavoiding) rook paths joining opposite corners of an n X n grid.


26



1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The length of the path varies.
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 selfavoiding 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 selfavoiding) rook paths joining opposite corner cells of an (n+1) X (n+1) grid." (End)


REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331339.
D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 2728.
D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
Shinichi Minato, The power of enumeration  BDD/ZDDbased algorithms for tackling combinatorial explosion, Chapter 3 of Applications of ZeroSuppressed Decision Diagrams, ed. T. Satsoa and J. t. Butler, Morgan & Claypool Publishers, 2014
Shinichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 16.
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..26 (I. Jensen computed terms 0 to 19, H. Iwashita computed 20 and 21, R. Spaans computed 22 to 24, and H. Iwashita computed 25 and 26)
M. BousquetMélou, A. J. Guttmann and I. Jensen, Selfavoiding walks crossing a square
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtubeanimation demonstrating this sequence. In Japanese with English translation]
S. R. Finch, SelfAvoidingWalk Connective Constants
H. Iwashita, J. Kawahara, and S. Minato, ZDDBased 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 SelfAvoiding Walks
OEIS Wiki, Selfavoiding_walks
Ruben Grønning Spaans, C program
Eric Weisstein's World of Mathematics, SelfAvoiding Walk


EXAMPLE

Suppose we start at (0,0) and end at (n1,n1). 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

Main diagonal of A064298.
Cf. A064297, A271507, A001184, A000532.
Sequence in context: A243807 A006023 A039748 * A015195 A051421 A182162
Adjacent sequences: A007761 A007762 A007763 * A007765 A007766 A007767


KEYWORD

nonn,walk,hard,nice


AUTHOR

David Radcliffe and Don Knuth


EXTENSIONS

Computed to n=11 by John Van Rosendale in 1981, extended to n=12 by Don Knuth, Dec 07 1995
Extended to n=19 by Mireille BousquetMélou, 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
Extended to n=26 by Hiroaki Iwashita, Nov 18 2013


STATUS

approved



