A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with n nodes.

1, 3, 6, 10, 17, 24, 37, 51, 78, 110, 173, 229, 340, 477, 750, 1024, 1571, 2253, 3616, 5024, 7839, 11356, 18389, 25173, 38740, 55697, 89610, 124870, 195389, 283536, 459829, 636123, 988710, 1429442, 2310905, 3227617, 5061040, 7352817, 11936370, 16526444

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..5651 (first 255 terms from Andrew Howroyd)

Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Wikipedia, Types of binary trees

Formula

a(2^k-1) = A285934(k-1).

Mathematica

Join[{1}, Table[g=KaryTree[n]; -1 + ParallelSum[Boole@ConnectedGraphQ@Subgraph[g, s], {s, Subsets@Range[n]}], {n, 2, 16}]]
(* Second program: *)
l[n_] := With[{h = 2^Floor[Log[2, n]]}, Min[h - 1, n - h/2]];
b[n_] := b[n] = 1 + If[n <= 1, n, b[l[n]]*b[n - 1 - l[n]]];
a[n_] := a[n] = If[n <= 1, n, b[n] - 1 + a[l[n]] + a[n - 1 - l[n]]];
Array[a, 40] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

Prog

(PARI)
l(n)={my(h=2^floor(log(n)/log(2))); min(h-1, n-h/2)}
b(n)=1+if(n<=1, n, b(l(n))*b(n-1-l(n)));
a(n)=if(n<=1, n, b(n)-1 + a(l(n)) + a(n-1-l(n))); \\ Andrew Howroyd, May 22 2017

Crossrefs

Cf. A285934, 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: A094272 A236326 A308699 * A005045 A189376 A069241

Adjacent sequences: A286301 A286302 A286303 * A286305 A286306 A286307

Keyword

nonn

Author

Giovanni Resta, May 05 2017

Extensions

Terms a(35) and beyond from Andrew Howroyd, May 22 2017

Status

approved