login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with graph n nodes. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 12:00 EDT 2019. Contains 327170 sequences. (Running on oeis4.)