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

 

Logo


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. 28
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.

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.

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).

LINKS

I. Jensen, H. Iwashita, R. Spaans, Table of n, a(n) for n = 1..27 (I. Jensen computed terms 1 to 20, H. Iwashita computed 21 and 22, R. Spaans computed 23 to 25, and H. Iwashita computed 26 and 27)

M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, arXiv:cond-mat/0506341 [cond-mat.stat-mech], 2005.

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, TCS Technical Report, TCS-TR-A-12-60, Hokkaido University, September 18, 2012.

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, TCS Technical Report, TCS-TR-A-13-64, Hokkaido University, April 26, 2013.

I. Jensen, Series Expansions for Self-Avoiding Walks

Shin-ichi Minato, Power of Enumeration - Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation, IEICE Transactions on Information and Systems, Volume E100.D (2017), Issue 8, p. 1556-1562.

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 (1,1) and end at (n,n). 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=12 by John Van Rosendale in 1981

Extended to n=13 by Don Knuth, Dec 07 1995

Extended to n=20 by Mireille Bousquet-Mélou, A. J. Guttmann and I. Jensen

Extended to n=22 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=25 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=26 by Hiroaki Iwashita, Apr 11 2013

Extended to n=27 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 | 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 October 19 10:27 EDT 2018. Contains 316353 sequences. (Running on oeis4.)