

A140517


Number of cycles in an n X n grid.


17



0, 1, 13, 213, 9349, 1222363, 487150371, 603841648931, 2318527339461265, 27359264067916806101, 988808811046283595068099, 109331355810135629946698361371, 36954917962039884953387868334644457
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Or, number of simply connected and rookwise connected regions of an (n1) X (n1) grid.


REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.


LINKS

Fawaz Alazemi, Arash Azizimazreah, Bella Bose, and Lizhong Chen, Routerless NetworksonChip, U.S. Patent Application No. 15,445,736, 2017.
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 TRA1364, Division of Computer Science, Hokkaido University, Report Series A, April 26 2013.
Kimberly Villalobos, Vilim Štih, Amineh Ahmadinejad, Shobhita Sundaram, Jamell Dozier, Andrew Francl, Frederico Azevedo, Tomotake Sasaki, and Xavier Boix, Do Neural Networks for Segmentation Understand Insideness?, MIT Center for Brains, Minds + Machines, CBMM Memo (2020) No. 105.


MATHEMATICA

Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* Eric W. Weisstein, Mar 07 2023 *)


PROG

(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
if n == 0: return 0
universe = tl.grid(n, n)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()


CROSSREFS

Cornertocorner paths in this grid are enumerated in A007764.


KEYWORD

nonn


AUTHOR



EXTENSIONS

a(9) calculated using the ZDD technique described in Knuth's The Art of Computer Programming, Exercises 7.1.4, by Ashutosh Mehra, Dec 19 2008
a(10)a(19) calculated using a transfer matrix method by Artem M. Karavaev, Jun 03 2009, Oct 20 2009


STATUS

approved



