# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a007764
Showing 1-1 of 1
%I A007764 #138 Mar 31 2023 15:29:21
%S A007764 1,2,12,184,8512,1262816,575780564,789360053252,3266598486981642,
%T A007764 41044208702632496804,1568758030464750013214100,
%U A007764 182413291514248049241470885236,64528039343270018963357185158482118,69450664761521361664274701548907358996488
%N A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.
%C A007764 The length of the path varies.
%D A007764 Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.
%D A007764 Guttmann A J and Jensen I 2022 Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices Journal of Physics A: Mathematical and Theoretical 55 012345, (33pp) ; arXiv:2208.06744, Aug 2022.
%D A007764 D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 27-28.
%D A007764 D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
%D A007764 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
%D A007764 Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.
%D A007764 Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).
%H A007764 I. Jensen, H. Iwashita, and 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)
%H A007764 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.
%H A007764 Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtube-animation demonstrating this sequence. In Japanese with English translation]
%H A007764 Steven R. Finch, Self-Avoiding-Walk Connective Constants
%H A007764 Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.
%H A007764 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 A007764 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.
%H A007764 I. Jensen, Series Expansions for Self-Avoiding Walks
%H A007764 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.
%H A007764 OEIS Wiki, Self-avoiding_walks
%H A007764 Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, and Isao Tanaka, Derivative structure enumeration using binary decision diagram, arXiv:2002.12603 [physics.comp-ph], 2020.
%H A007764 Ruben Grønning Spaans, C program
%H A007764 Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.
%H A007764 Eric Weisstein's World of Mathematics, Self-Avoiding Walk
%e A007764 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 A007764 a(2) = 2: UR or RU.
%e A007764 a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.
%o A007764 (Python)
%o A007764 # Using graphillion
%o A007764 from graphillion import GraphSet
%o A007764 import graphillion.tutorial as tl
%o A007764 def A007764(n):
%o A007764 if n == 1: return 1
%o A007764 universe = tl.grid(n - 1, n - 1)
%o A007764 GraphSet.set_universe(universe)
%o A007764 start, goal = 1, n * n
%o A007764 paths = GraphSet.paths(start, goal)
%o A007764 return paths.len()
%o A007764 print([A007764(n) for n in range(1, 10)]) # _Seiichi Manyama_, Mar 21 2020
%Y A007764 Main diagonal of A064298.
%Y A007764 Cf. A064297, A271507, A001184, A000532.
%K A007764 nonn,walk,hard,nice
%O A007764 1,2
%A A007764 _David Radcliffe_ and _Don Knuth_
%E A007764 Computed to n=12 by John Van Rosendale in 1981
%E A007764 Extended to n=13 by _Don Knuth_, Dec 07 1995
%E A007764 Extended to n=20 by _Mireille Bousquet-Mélou_, A. J. Guttmann and I. Jensen
%E A007764 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 A007764 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 A007764 Extended to n=26 by _Hiroaki Iwashita_, Apr 11 2013
%E A007764 Extended to n=27 by _Hiroaki Iwashita_, Nov 18 2013
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE