

A007764


Number of nonintersecting (or selfavoiding) rook paths joining opposite corners of an n X n grid.


32



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

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331338.
D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 2728.
D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
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
Shinichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 16.
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. BousquetMélou, A. J. Guttmann and I. Jensen, Selfavoiding walks crossing a square, arXiv:condmat/0506341 [condmat.statmech], 2005.
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtubeanimation demonstrating this sequence. In Japanese with English translation]
Steven R. Finch, SelfAvoidingWalk Connective Constants
H. Iwashita, J. Kawahara, and S. Minato, ZDDBased Computation of the Number of Paths in a Graph, TCS Technical Report, TCSTRA1260, 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, TCSTRA1364, Hokkaido University, April 26, 2013.
I. Jensen, Series Expansions for SelfAvoiding Walks
Shinichi Minato, Power of Enumeration  Recent Topics on BDD/ZDDBased Techniques for Discrete Structure Manipulation, IEICE Transactions on Information and Systems, Volume E100.D (2017), Issue 8, p. 15561562.
OEIS Wiki, Selfavoiding_walks
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, Isao Tanaka, Derivative structure enumeration using binary decision diagram, arXiv:2002.12603 [physics.compph], 2020.
Ruben Grønning Spaans, C program
Eric Weisstein's World of Mathematics, SelfAvoiding 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.


PROG

(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A007764(n):
if n == 1: return 1
universe = tl.grid(n  1, n  1)
GraphSet.set_universe(universe)
start, goal = 1, n * n
paths = GraphSet.paths(start, goal)
return paths.len()
print([A007764(n) for n in range(1, 10)]) # Seiichi Manyama, Mar 21 2020


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 BousquetMé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



