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

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

Author

Andrew Howroyd, Jan 29 2023

Keywords

• nonn
• tabl

Comments

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

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..497
• Eric Weisstein's World of Mathematics, Chordless Cycle.
• Eric Weisstein's World of Mathematics, Grid Graph.
• Wikipedia, Cycle (graph theory).

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

Formula

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