A302337 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).

1, 4, 4, 5, 9, 12, 26, 52, 76, 32, 6, 16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226, 25, 40, 110, 332, 1070, 3504, 11144, 32172, 77874, 146680, 217470, 255156, 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

Offset: 2

Author

Eric W. Weisstein, Apr 05 2018

Keywords

• nonn
• tabf

Examples

			Triangle begins:
   1;
   4,  4,  5;
   9, 12, 26,  52,  76,   32,    6;
  16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226;
  ...
So for example, the 3 X 3 grid graph has 4 4-cycles, 4 6-cycles, and 5 8-cycles.
		

Links

• Seiichi Manyama, Rows n = 2..9, flattened
• Eric Weisstein's World of Mathematics, Graph Cycle
• Eric Weisstein's World of Mathematics, Grid Graph

Crossrefs

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

Cf. A140517 (number of cycles).

Cf. A301648 (number of longest cycles).

Programs

Mathematica

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

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A302337(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return [cycles.len(2 * k).len() for k in range(2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A302337(n)])  # Seiichi Manyama, Mar 29 2020

Formula

Row sums equal A140517(n).

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

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

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

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

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

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

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

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

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