The OEIS is supported by the many generous donors to the OEIS Foundation.



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
Or, number of simply connected and rookwise connected regions of an (n-1) X (n-1) grid.
D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.
Artem M. Karavaev and Hiroaki Iwashita, Table of n, a(n) for n = 0..26 (A. Karavaev computed terms 10 to 19)
Fawaz Alazemi, Arash Azizimazreah, Bella Bose, and Lizhong Chen, Routerless Networks-on-Chip, 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 -TR-A-13-64, 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.
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, ZDD
Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* Eric W. Weisstein, Mar 07 2023 *)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A140517(n):
if n == 0: return 0
universe = tl.grid(n, n)
cycles = GraphSet.cycles()
return cycles.len()
print([A140517(n) for n in range(9)]) # Seiichi Manyama, Mar 23 2020
Corner-to-corner paths in this grid are enumerated in A007764.
Main diagonal of A231829.
Sequence in context: A251093 A132542 A069989 * A096141 A218475 A294982
Don Knuth, Jul 26 2008
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
a(20)-a(26) calculated by Hiroaki Iwashita, Apr 26 2013, Nov 18 2013
Edited by Max Alekseyev, Jan 24 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 07:10 EST 2023. Contains 367689 sequences. (Running on oeis4.)