This site is supported by donations to The OEIS Foundation.



"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

(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. 28
1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488 (list; graph; refs; listen; history; text; internal format)



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)


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.

Shin-ichi Minato, The power of enumeration - BDD/ZDD-based algorithms for tackling combinatorial explosion, Chapter 3 of Applications of Zero-Suppressed Decision Diagrams, ed. T. Satsoa and J. t. Butler, Morgan & Claypool Publishers, 2014

Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.

Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).


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-Mélou, 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


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.


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




David Radcliffe and Don Knuth


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 Bousquet-Mé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



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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 21 16:03 EDT 2017. Contains 290890 sequences.