|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
LINKS
|
|
|
FORMULA
|
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,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
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)]
|
|
CROSSREFS
|
Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).
Cf. A301648 (number of longest cycles).
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|