A024358 Sum of the sizes of binary subtrees of the perfect binary tree of height n.

0, 1, 8, 105, 6136, 8766473, 8245941529080, 3508518207951157937469961, 311594265746788494170062926869662848646207622648, 1217308491239906829392988008143949647398943617188660186130545502913055217344025410733271773705

Offset: 0

Author

Cyril Banderier, Jun 09 2000

Keywords

• easy
• nonn

Comments

Size of binary tree = number of internal nodes.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..12
• Cyril Banderier, On the sum of the sizes of binary subtrees of a perfect binary tree, personal note, 2000.

Crossrefs

Cf. A003095, A309049, A309052.

Programs

Maple

B:= proc(n) B(n):= `if`(n<0, 0, expand(1+x*B(n-1)^2)) end:
a:= n-> subs(x=1, diff(B(n), x)):
seq(a(n), n=0..9);  # Alois P. Heinz, Jul 12 2019

Mathematica

B[n_] := If[n<0, 0, Expand[1+x*B[n-1]^2]];
a[n_] := D[B[n], x] /. x -> 1;
Table[a[n], {n, 0, 9}] (* Jean-François Alcover, Oct 13 2022, after Alois P. Heinz *)

Formula

a(n) = B'n(1) where B{n+1}(x) = 1 + x*B_n(x)^2.

From Alois P. Heinz, Jul 12 2019: (Start)

a(n) = Sum_{k=0..2^n-1} (2^n-1-k) * A309049(2^n-1,k).

a(n) = A309052(2^n-1). (End)

Extensions

a(0) changed to 0 by Alois P. Heinz, Jul 12 2019