cp's OEIS Frontend

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

%I A286304 #31 Feb 16 2025 08:33:44
%S A286304 1,3,6,10,17,24,37,51,78,110,173,229,340,477,750,1024,1571,2253,3616,
%T A286304 5024,7839,11356,18389,25173,38740,55697,89610,124870,195389,283536,
%U A286304 459829,636123,988710,1429442,2310905,3227617,5061040,7352817,11936370,16526444
%N A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with n nodes.
%H A286304 Alois P. Heinz, <a href="/A286304/b286304.txt">Table of n, a(n) for n = 1..5651</a> (first 255 terms from Andrew Howroyd)
%H A286304 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%H A286304 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees">Types of binary trees</a>
%F A286304 a(2^k-1) = A285934(k-1).
%t A286304 Join[{1}, Table[g=KaryTree[n]; -1 + ParallelSum[Boole@ConnectedGraphQ@Subgraph[g, s], {s, Subsets@Range[n]}], {n, 2, 16}]]
%t A286304 (* Second program: *)
%t A286304 l[n_] := With[{h = 2^Floor[Log[2, n]]}, Min[h - 1, n - h/2]];
%t A286304 b[n_] := b[n] = 1 + If[n <= 1, n, b[l[n]]*b[n - 1 - l[n]]];
%t A286304 a[n_] := a[n] = If[n <= 1, n, b[n] - 1 + a[l[n]] + a[n - 1 - l[n]]];
%t A286304 Array[a, 40] (* _Jean-François Alcover_, Nov 01 2017, after _Andrew Howroyd_ *)
%o A286304 (PARI)
%o A286304 l(n)={my(h=2^floor(log(n)/log(2))); min(h-1,n-h/2)}
%o A286304 b(n)=1+if(n<=1,n,b(l(n))*b(n-1-l(n)));
%o A286304 a(n)=if(n<=1,n,b(n)-1 + a(l(n)) + a(n-1-l(n))); \\ _Andrew Howroyd_, May 22 2017
%Y A286304 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).
%K A286304 nonn
%O A286304 1,2
%A A286304 _Giovanni Resta_, May 05 2017
%E A286304 Terms a(35) and beyond from _Andrew Howroyd_, May 22 2017