cp's OEIS Frontend

A140517 Number of cycles in an n X n grid.

%I A140517 #53 Feb 16 2025 08:33:08
%S A140517 0,1,13,213,9349,1222363,487150371,603841648931,2318527339461265,
%T A140517 27359264067916806101,988808811046283595068099,
%U A140517 109331355810135629946698361371,36954917962039884953387868334644457,38157703688577845304445530851242055267353,120285789340533859558405124213592877516931371715
%N A140517 Number of cycles in an n X n grid.
%C A140517 Or, number of simply connected and rookwise connected regions of an (n-1) X (n-1) grid.
%D A140517 D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.
%H A140517 Artem M. Karavaev and Hiroaki Iwashita, <a href="/A140517/b140517.txt">Table of n, a(n) for n = 0..26</a> (A. Karavaev computed terms 10 to 19)
%H A140517 Fawaz Alazemi, Arash Azizimazreah, Bella Bose, and Lizhong Chen, <a href="http://web.engr.oregonstate.edu/~chenliz/publications/2018_HPCA_Routerless%20NoC.pdf">Routerless Networks-on-Chip</a>, U.S. Patent Application No. 15,445,736, 2017.
%H A140517 H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, <a href="http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf">Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions</a>, TCS Technical Report, TCS -TR-A-13-64, Division of Computer Science, Hokkaido University, Report Series A, April 26 2013.
%H A140517 Artem M. Karavaev, <a href="https://web.archive.org/web/20161015201520/http://flowproblem.ru/cycles/all-simple-cycles">FlowProblem.Ru: All Simple Cycles</a>
%H A140517 Kimberly Villalobos, Vilim Štih, Amineh Ahmadinejad, Shobhita Sundaram, Jamell Dozier, Andrew Francl, Frederico Azevedo, Tomotake Sasaki, and Xavier Boix, <a href="https://cbmm.mit.edu/publications/do-neural-networks-segmentation-understand-insideness">Do Neural Networks for Segmentation Understand Insideness?</a>, MIT Center for Brains, Minds + Machines, CBMM Memo (2020) No. 105.
%H A140517 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>
%H A140517 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A140517 Wikipedia, <a href="https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram">ZDD</a>
%t A140517 Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* _Eric W. Weisstein_, Mar 07 2023 *)
%o A140517 (Python)
%o A140517 # Using graphillion
%o A140517 from graphillion import GraphSet
%o A140517 import graphillion.tutorial as tl
%o A140517 def A140517(n):
%o A140517     if n == 0: return 0
%o A140517     universe = tl.grid(n, n)
%o A140517     GraphSet.set_universe(universe)
%o A140517     cycles = GraphSet.cycles()
%o A140517     return cycles.len()
%o A140517 print([A140517(n) for n in range(9)])  # _Seiichi Manyama_, Mar 23 2020
%Y A140517 Corner-to-corner paths in this grid are enumerated in A007764.
%Y A140517 Main diagonal of A231829.
%K A140517 nonn
%O A140517 0,3
%A A140517 _Don Knuth_, Jul 26 2008
%E A140517 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
%E A140517 a(10)-a(19) calculated using a transfer matrix method by _Artem M. Karavaev_, Jun 03 2009, Oct 20 2009
%E A140517 a(20)-a(26) calculated by _Hiroaki Iwashita_, Apr 26 2013, Nov 18 2013
%E A140517 Edited by _Max Alekseyev_, Jan 24 2018