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

Author

Giovanni Resta, May 05 2017

Keywords

• nonn

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

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).

Programs

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 *)

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

Formula

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

Extensions

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