login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Array read by antidiagonals: T(m,n) is the number of induced cycles in the grid graph P_m X P_n.
9

%I #14 Feb 27 2023 13:38:28

%S 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,

%T 7,8,35,251,749,749,251,35,8,9,44,490,2180,3436,2180,490,44,9,10,54,

%U 948,6188,13350,13350,6188,948,54,10,11,65,1823,17912,50203,65772,50203,17912,1823,65,11

%N Array read by antidiagonals: T(m,n) is the number of induced cycles in the grid graph P_m X P_n.

%C Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4).

%H Andrew Howroyd, <a href="/A360196/b360196.txt">Table of n, a(n) for n = 2..497</a>

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">Cycle (graph theory)</a>.

%F T(m,n) = T(n,m).

%e Array begins:

%e ========================================================

%e m\n| 2 3 4 5 6 7 8 9 ...

%e ---+----------------------------------------------------

%e 2 | 1 2 3 4 5 6 7 8 ...

%e 3 | 2 5 9 14 20 27 35 44 ...

%e 4 | 3 9 24 58 125 251 490 948 ...

%e 5 | 4 14 58 229 749 2180 6188 17912 ...

%e 6 | 5 20 125 749 3436 13350 50203 196918 ...

%e 7 | 6 27 251 2180 13350 65772 308212 1535427 ...

%e 8 | 7 35 490 6188 50203 308212 1743247 10614143 ...

%e 9 | 8 44 948 17912 196918 1535427 10614143 78586742 ...

%e ...

%Y Main diagonal is A297664.

%Y Rows 2..5 are A000027(n-1), A000096(n-1), A360197, A360198.

%Y Cf. A231829 (undirected cycles), A287151 (connected induced subgraphs), A360199 (induced paths), A360202 (induced trees), A360913 (maximum induced cycles).

%K nonn,tabl

%O 2,2

%A _Andrew Howroyd_, Jan 29 2023