%I
%S 1,2,12,184,8512,1262816,575780564,789360053252,3266598486981642,
%T 41044208702632496804,1568758030464750013214100,
%U 182413291514248049241470885236,64528039343270018963357185158482118,69450664761521361664274701548907358996488
%N Number of nonintersecting (or selfavoiding) rook paths joining opposite corners of an n X n grid.
%C The length of the path varies.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331339.
%D D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 2728.
%D D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
%D 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
%D Shinichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 16.
%D Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).
%H I. Jensen, H. Iwashita, R. Spaans, <a href="/A007764/b007764.txt">Table of n, a(n) for n = 1..27</a> (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)
%H M. BousquetMélou, A. J. Guttmann and I. Jensen, <a href="http://arXiv.org/abs/condmat/0506341">Selfavoiding walks crossing a square</a>, arXiv:condmat/0506341 [condmat.statmech], 2005.
%H Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., <a href="http://www.youtube.com/watch?v=Q4gTV4r0zRs">Time with class! Let's count!</a> [Youtubeanimation demonstrating this sequence. In Japanese with English translation]
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/cnntv/cnntv.html">SelfAvoidingWalk Connective Constants</a>
%H H. Iwashita, J. Kawahara, and S. Minato, <a href="http://wwwalg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_12_60/tcstr_12_60.pdf">ZDDBased Computation of the Number of Paths in a Graph</a>, TCS Technical Report, TCSTRA1260, Hokkaido University, September 18, 2012.
%H H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, <a href="http://wwwalg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf">Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions</a>, TCS Technical Report, TCSTRA1364, Hokkaido University, April 26, 2013.
%H I. Jensen, <a href="http://www.ms.unimelb.edu.au/~iwan/saw/SAW_ser.html">Series Expansions for SelfAvoiding Walks</a>
%H Shinichi Minato, <a href="https://dx.doi.org/10.1587/transinf.2016LOI0002">Power of Enumeration  Recent Topics on BDD/ZDDBased Techniques for Discrete Structure Manipulation</a>, IEICE Transactions on Information and Systems, Volume E100.D (2017), Issue 8, p. 15561562.
%H OEIS Wiki, <a href="/wiki/Selfavoiding_walks#Selfavoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)">Selfavoiding_walks</a>
%H Ruben Grønning Spaans, <a href="https://github.com/stubbscroll/OEIS/blob/master/A007764fast.c">C program</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SelfAvoidingWalk.html">SelfAvoiding Walk</a>
%e Suppose we start at (1,1) and end at (n,n). Let U, D, L, R denote steps that are up, down, left, right.
%e a(2) = 2: UR or RU.
%e a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.
%Y Main diagonal of A064298.
%Y Cf. A064297, A271507, A001184, A000532.
%K nonn,walk,hard,nice
%O 1,2
%A _David Radcliffe_ and _Don Knuth_
%E Computed to n=12 by John Van Rosendale in 1981
%E Extended to n=13 by _Don Knuth_, Dec 07 1995
%E Extended to n=20 by _Mireille BousquetMélou_, A. J. Guttmann and I. Jensen
%E 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
%E 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
%E Extended to n=26 by _Hiroaki Iwashita_, Apr 11 2013
%E Extended to n=27 by _Hiroaki Iwashita_, Nov 18 2013
