login
Number of maximum induced trees in the n X n grid graph.
2

%I #11 Feb 16 2025 08:34:04

%S 1,4,10,32,22,4120,488,65864,166,1296,872,37652512,678412,1858036816,

%T 337856

%N Number of maximum induced trees in the n X n grid graph.

%C A maximum induced tree is an induced tree of greatest size.

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

%e The a(3) = 10 maximum induced trees are the following subgraphs and their rotations and reflections.

%e O O O O O O O O O

%e O O O O

%e O O O O O O O O

%e .

%e The a(4) = 32 maximum induced trees are the following subgraphs and their rotations and reflections.

%e O O O O O O O O O O O O O O

%e O O O O O O O O O O

%e O O O O O O O O O O O O

%e O O O O O O O O O O O O

%Y Main diagonal of A360918.

%Y Cf. A360203 (induced trees), A360921 (maximum sizes).

%K nonn,more,changed

%O 1,2

%A _Andrew Howroyd_, Feb 26 2023