A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

1, 6, 37, 750, 459829, 210067308558, 44127887746326310604917, 1947270476915296449559791701269341583074001038

Offset: 0

Author

Giovanni Resta, May 05 2017

Keywords

• nonn
• easy

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
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
• Wikipedia, Types of binary trees

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

Programs

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]

Formula

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