login
A360196
Array read by antidiagonals: T(m,n) is the number of induced cycles in the grid graph P_m X P_n.
9
1, 2, 2, 3, 5, 3, 4, 9, 9, 4, 5, 14, 24, 14, 5, 6, 20, 58, 58, 20, 6, 7, 27, 125, 229, 125, 27, 7, 8, 35, 251, 749, 749, 251, 35, 8, 9, 44, 490, 2180, 3436, 2180, 490, 44, 9, 10, 54, 948, 6188, 13350, 13350, 6188, 948, 54, 10, 11, 65, 1823, 17912, 50203, 65772, 50203, 17912, 1823, 65, 11
OFFSET
2,2
COMMENTS
Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4).
LINKS
Eric Weisstein's World of Mathematics, Chordless Cycle.
Eric Weisstein's World of Mathematics, Grid Graph.
FORMULA
T(m,n) = T(n,m).
EXAMPLE
Array begins:
========================================================
m\n| 2 3 4 5 6 7 8 9 ...
---+----------------------------------------------------
2 | 1 2 3 4 5 6 7 8 ...
3 | 2 5 9 14 20 27 35 44 ...
4 | 3 9 24 58 125 251 490 948 ...
5 | 4 14 58 229 749 2180 6188 17912 ...
6 | 5 20 125 749 3436 13350 50203 196918 ...
7 | 6 27 251 2180 13350 65772 308212 1535427 ...
8 | 7 35 490 6188 50203 308212 1743247 10614143 ...
9 | 8 44 948 17912 196918 1535427 10614143 78586742 ...
...
CROSSREFS
Main diagonal is A297664.
Rows 2..5 are A000027(n-1), A000096(n-1), A360197, A360198.
Cf. A231829 (undirected cycles), A287151 (connected induced subgraphs), A360199 (induced paths), A360202 (induced trees), A360913 (maximum induced cycles).
Sequence in context: A128141 A252829 A014430 * A225622 A196436 A197199
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Jan 29 2023
STATUS
approved