login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid. 14
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 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..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. 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,changed

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

Extended to n=26 by Hiroaki Iwashita, Nov 18 2013

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 23 13:43 EDT 2014. Contains 240929 sequences.