login
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).
8
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,2
LINKS
Seiichi Manyama, Rows n = 2..9, flattened
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph
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.
EXAMPLE
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.
MATHEMATICA
Flatten[Table[Tally[Length /@ FindCycle[GridGraph[{n, n}], Infinity, All]][[All, 2]], {n, 6}]] (* Eric W. Weisstein, Mar 26 2021 *)
PROG
(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
CROSSREFS
Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).
Cf. A140517 (number of cycles).
Cf. A301648 (number of longest cycles).
Sequence in context: A155693 A160705 A107851 * A098821 A363322 A374754
KEYWORD
nonn,tabf
AUTHOR
Eric W. Weisstein, Apr 05 2018
STATUS
approved