A395108 - OEIS

A395108

Number of points covered by a minimal level n H-Tree on a square lattice.

1, 3, 7, 17, 37, 81, 169, 353, 721, 1473, 2977, 6017, 12097, 24321, 48769, 97793, 195841, 392193, 784897, 1570817, 3142657, 6287361, 12576769, 25157633, 50319361, 100646913, 201302017, 402620417, 805257217, 1610547201, 3221127169, 6442319873, 12884705281, 25769541633, 51539214337, 103078690817

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

A minimal H-Tree covers the fewest possible points on a square lattice. This results in a smaller bounding box, 2^(n-2)-1 by 2^(n-3)-1, than a regular H-Tree, 2^(n-2)-1 by 2^(n-2)-3, at odd n > 1.

LINKS

David Cleaver, Table of n, a(n) for n = 0..1000

David Cleaver, Illustration of a(0)-a(6)

Neil Robertson and P. D. Seymour, Graph Minors. I. Excluding a Forest, Journal of Combinatorial Theory, Series B, Volume 35, Issue 1, August 1983, Pages 39-61 (see H6 in Fig. 3 on p. 52).

Wikipedia, H tree.

Index entries for linear recurrences with constant coefficients, signature (3,0,-6,4).

FORMULA

a(2n) = A169726(n).

G.f.: -(2*x^3-2*x^2+1)/((x-1)*(2*x-1)*(2*x^2-1)). - Joerg Arndt, Apr 12 2026

a(n) = 1 + 3*2^n - 2^((n-3)/2)*(4 + 3*sqrt(2) + (-1)^n*(3*sqrt(2) - 4)). - Stefano Spezia, Apr 15 2026

MATHEMATICA

a[n_]:=1+3*2^n-2^((n-3)/2)*(4+3Sqrt[2]+(-1)^n*(3*Sqrt[2]-4)); Array[a, 36, 0] (* Stefano Spezia, Apr 15 2026 *)

PROG

(PARI) a(n)={my(T=1); for(i=1, n, T=T+2^floor((n-i)/2)*2^i); T};

CROSSREFS

Cf. A169726, A395109.