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

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

Offset

1,2

Comments

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

Links

Table of n, a(n) for n=1..15.

Eric Weisstein's World of Mathematics, Grid Graph.

Example

The a(3) = 10 maximum induced trees are the following subgraphs and their rotations and reflections.
   O O O    O O O    O O O
   O        O   O      O
   O O O      O O    O O O
.
The a(4) = 32 maximum induced trees are the following subgraphs and their rotations and reflections.
    O O O O    O O O      O O O O    O O   O
    O     O    O   O O      O   O      O O O
    O O   O    O O   O    O O   O    O O   O
    O   O O    O   O O    O   O O    O   O O

Crossrefs

Main diagonal of A360918.

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

Sequence in context: A289447 A135831 A213106 * A015796 A318562 A034717

Adjacent sequences: A360916 A360917 A360918 * A360920 A360921 A360922

Keyword

nonn,more

Author

Andrew Howroyd, Feb 26 2023

Status

approved