|
|
A007764
|
|
Number of nonintersecting (or self-avoiding) 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. 331-338.
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. 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, 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! [Youtube-animation 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, TCS-TR-A-13-64, 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
|
|
|
|