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

%I #11 Feb 27 2023 20:29:52

%S 1,3,3,6,12,6,10,33,33,10,15,78,138,78,15,21,171,533,533,171,21,28,

%T 360,2003,3568,2003,360,28,36,741,7453,23686,23686,7453,741,36,45,

%U 1506,27643,156614,277606,156614,27643,1506,45,55,3039,102432,1034875,3234373,3234373,1034875,102432,3039,55

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

%H Andrew Howroyd, <a href="/A360202/b360202.txt">Table of n, a(n) for n = 1..435</a>

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

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

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

%e Array begins:

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

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

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

%e 1 | 1 3 6 10 15 21 28 ...

%e 2 | 3 12 33 78 171 360 741 ...

%e 3 | 6 33 138 533 2003 7453 27643 ...

%e 4 | 10 78 533 3568 23686 156614 1034875 ...

%e 5 | 15 171 2003 23686 277606 3234373 37643572 ...

%e 6 | 21 360 7453 156614 3234373 66136452 1349087217 ...

%e 7 | 28 741 27643 1034875 37643572 1349087217 48136454388 ...

%e ...

%Y Main diagonal is A360203.

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

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

%K nonn,tabl

%O 1,2

%A _Andrew Howroyd_, Feb 22 2023