A360202 Array read by antidiagonals: T(m,n) is the number of (non-null) induced trees in the grid graph P_m X P_n.

1, 3, 3, 6, 12, 6, 10, 33, 33, 10, 15, 78, 138, 78, 15, 21, 171, 533, 533, 171, 21, 28, 360, 2003, 3568, 2003, 360, 28, 36, 741, 7453, 23686, 23686, 7453, 741, 36, 45, 1506, 27643, 156614, 277606, 156614, 27643, 1506, 45, 55, 3039, 102432, 1034875, 3234373, 3234373, 1034875, 102432, 3039, 55

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..435

Eric Weisstein's World of Mathematics, Grid Graph.

Eric Weisstein's World of Mathematics, Induced Subgraph.

Formula

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

Example

Array begins:
=============================================================
m\n|  1   2     3       4        5          6           7 ...
---+---------------------------------------------------------
1  |  1   3     6      10       15         21          28 ...
2  |  3  12    33      78      171        360         741 ...
3  |  6  33   138     533     2003       7453       27643 ...
4  | 10  78   533    3568    23686     156614     1034875 ...
5  | 15 171  2003   23686   277606    3234373    37643572 ...
6  | 21 360  7453  156614  3234373   66136452  1349087217 ...
7  | 28 741 27643 1034875 37643572 1349087217 48136454388 ...
     ...

Crossrefs

Main diagonal is A360203.

Rows 1..2 are A000217, 3*A125128.

Cf. A287151 (connected induced subgraphs), A116469 (spanning trees), A360196 (induced cycles), A360199 (induced paths), A360918 (maximum induced trees).

Sequence in context: A367644 A094305 A360850 * A057963 A250301 A261954

Adjacent sequences: A360199 A360200 A360201 * A360203 A360204 A360205

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 22 2023

Status

approved