A302337 - OEIS

%I #22 Feb 16 2025 08:33:53

%S 1,4,4,5,9,12,26,52,76,32,6,16,24,61,164,446,1100,2102,2436,1874,900,

%T 226,25,40,110,332,1070,3504,11144,32172,77874,146680,217470,255156,

%U 233786,158652,69544,13732,1072,36,60,173,556,1942,7092,26424,97624,346428,1136164,3313812,8342388,18064642,33777148,54661008,76165128,89790912,86547168,64626638,34785284,12527632,2677024,255088

%N Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

%H Seiichi Manyama, <a href="/A302337/b302337.txt">Rows n = 2..9, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%F Row sums equal A140517(n).

%F Length of row n equals A047838(n) = floor(n^2/2) - 1.

%F T(n,2) =    1 -   2*n +     n^2 = (n-1)^2.

%F T(n,3) =    4 -   6*n +   2*n^2 = A046092(n-2).

%F T(n,4) =   26 -  28*n +   7*n^2 for n > 2.

%F T(n,5) =  164 - 140*n +  28*n^2 for n > 3.

%F T(n,6) = 1046 - 740*n + 124*n^2 for n > 4.

%F T(n,k) = A302335(k) - A302336(k)*n + A002931(k)*n^2 for n > k-2.

%F T(n,floor(n^2/2)) = A301648(n).

%F T(n,n^2/2) = A003763(n) for n even.

%e Triangle begins:

%e    1;

%e    4,  4,  5;

%e    9, 12, 26,  52,  76,   32,    6;

%e   16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226;

%e   ...

%e So for example, the 3 X 3 grid graph has 4 4-cycles, 4 6-cycles, and 5 8-cycles.

%t Flatten[Table[Tally[Length /@ FindCycle[GridGraph[{n, n}], Infinity, All]][[All, 2]], {n, 6}]] (* _Eric W. Weisstein_, Mar 26 2021 *)

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o import graphillion.tutorial as tl

%o def A302337(n):

%o     universe = tl.grid(n - 1, n - 1)

%o     GraphSet.set_universe(universe)

%o     cycles = GraphSet.cycles()

%o     return [cycles.len(2 * k).len() for k in range(2, n * n // 2 + 1)]

%o print([i for n in range(2, 8) for i in A302337(n)])  # _Seiichi Manyama_, Mar 29 2020

%Y Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).

%Y Cf. A140517 (number of cycles).

%Y Cf. A301648 (number of longest cycles).

%K nonn,tabf,changed

%O 2,2

%A _Eric W. Weisstein_, Apr 05 2018