|
%I #48 Mar 07 2023 10:35:59
%S 0,1,13,213,9349,1222363,487150371,603841648931,2318527339461265,
%T 27359264067916806101,988808811046283595068099,
%U 109331355810135629946698361371,36954917962039884953387868334644457
%N Number of cycles in an n X n grid.
%C Or, number of simply connected and rookwise connected regions of an (n-1) X (n-1) grid.
%D D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.
%H 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram">ZDD</a>
%t Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* _Eric W. Weisstein_, Mar 07 2023 *)
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o import graphillion.tutorial as tl
%o def A140517(n):
%o if n == 0: return 0
%o universe = tl.grid(n, n)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles()
%o return cycles.len()
%o print([A140517(n) for n in range(9)]) # _Seiichi Manyama_, Mar 23 2020
%Y Corner-to-corner paths in this grid are enumerated in A007764.
%Y Main diagonal of A231829.
%K nonn
%O 0,3
%A _Don Knuth_, Jul 26 2008
%E 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 a(10)-a(19) calculated using a transfer matrix method by _Artem M. Karavaev_, Jun 03 2009, Oct 20 2009
%E a(20)-a(26) calculated by _Hiroaki Iwashita_, Apr 26 2013, Nov 18 2013
%E Edited by _Max Alekseyev_, Jan 24 2018
| 