

A285934


Number of connected induced (nonnull) subgraphs of the perfect binary tree of height n.


3




OFFSET

0,2


COMMENTS

A perfect (sometimes called complete) binary tree of height k has 2^(k+1)1 nodes.
a(8) has 91 digits and thus it is not reported.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..11
Wikipedia, Types of binary trees
Eric Weisstein's World of Mathematics, VertexInduced Subgraph


FORMULA

Let b(0)=1 and b(n) = 1+b(n1)^2. Then, a(0)=1 and a(n) = b(n)^2 + 2*a(n1). Note that b(n) = A003095(n+1).


MATHEMATICA

a[1]=b[1]=1; b[n_] := b[n] = 1 + b[n  1]^2; a[n_] := a[n] = b[n]^2 + 2 a[n  1]; Array[a, 8]


CROSSREFS

Cf. A003095, A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).
Sequence in context: A240324 A283636 A211988 * A083373 A320988 A015492
Adjacent sequences: A285931 A285932 A285933 * A285935 A285936 A285937


KEYWORD

nonn,easy


AUTHOR

Giovanni Resta, May 05 2017


STATUS

approved



