

A007764


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


43



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.
Guttmann A J and Jensen I 2022 Selfavoiding 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. 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, 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)
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtubeanimation demonstrating this sequence. In Japanese with English translation]
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.


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


CROSSREFS



KEYWORD

nonn,walk,hard,nice


AUTHOR



EXTENSIONS

Computed to n=12 by John Van Rosendale in 1981
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


STATUS

approved



