A395109 - OEIS

A395109

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

1, 3, 7, 21, 37, 105, 169, 465, 721, 1953, 2977, 8001, 12097, 32385, 48769, 130305, 195841, 522753, 784897, 2094081, 3142657, 8382465, 12576769, 33542145, 50319361, 134193153, 201302017, 536821761, 805257217, 2147385345, 3221127169, 8589737985, 12884705281, 34359345153, 51539214337, 137438167041

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

OFFSET

0,2

COMMENTS

A regular H-Tree is taller than necessary, at odd n > 1, in order to maintain the size of the core at n+1. This results in a larger bounding box, 2^(n-2)-1 by 2^(n-2)-3, than a minimal H-Tree, 2^(n-2)-1 by 2^(n-3)-1, 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 (1,6,-6,-8,8).

FORMULA

G.f.: (-2*x^3+2*x^2-2*x-1)/((x-1)*(2*x-1)*(2*x+1)*(2*x^2-1)).

a(n) = (2^floor(n/2) + 2^floor((n-1)/2) - 2)*2^(floor((n+3)/2))+2^ceiling(n/2)+1.

a(n) = A027383(n-2)*2^A004526(n+3) + A051032(n+1).

a(n) = A027383(n-2)*A016116(n+3) + A051032(n+1).

a(2n) = 3*2^n*(2^n-1) + 1, n >= 0; a(2n-1) = binomial(2^(n+1)-1,2), n > 0.

MATHEMATICA

LinearRecurrence[{1, 6, -6, -8, 8}, {1, 3, 7, 21, 37}, 50] (* Paolo Xausa, Apr 21 2026 *)

PROG

(PARI) a(n)=(2^floor(n/2) + 2^floor((n-1)/2) - 2)*2^(floor((n+3)/2))+2^ceil(n/2)+1;