A157679 Number of subtrees of a complete binary tree.
0, 1, 2, 4, 6, 9, 15, 25, 35, 49, 70, 100, 160, 256, 416, 676, 936, 1296, 1800, 2500, 3550, 5041, 7171, 10201, 16261, 25921, 41377, 66049, 107169, 173889, 282309, 458329, 634349, 877969, 1215289, 1682209, 2335897, 3243601, 4504301, 6255001, 8881051, 12609601
Offset: 0
Examples
For n = 3, the a(3) = 4 subtrees are:
R R R R
/ \ / \
o o o o
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..5971
- A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
- A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
- Index entries for sequences related to rooted trees
Programs
-
Maple
a:= proc(n) option remember; `if`(n<2, n, (h-> (1+a(h))*(1+a(n-1-h)))(iquo(n, 2))) end: seq(a(n), n=0..50); # Alois P. Heinz, Jan 02 2022 -
Mathematica
a[0] = 0; a[1] = 1; a[n_?EvenQ] := a[n] = (1 + a[n/2 - 1])*(1 + a[n/2]); a[n_?OddQ] := a[n] = (1 + a[(n-1)/2])^2; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Oct 19 2011 *)
Formula
a(0) = 0, a(1) = 1.
a(n) = 1 + a(floor((n-1)/2)) + a(ceiling((n-1)/2)) + a(floor((n-1)/2)) * a(ceiling((n-1)/2)) = (1+a(floor((n-1)/2))) * (1+a(ceiling((n-1)/2))).
If b(n) is sequence A005468, then a(n)=b(n+1)-1. From the definition of A005468, a(n) = b(floor((n+1)/2))*b(ceiling((n+1)/2)). So for every odd n a(n) is a square: a(2*n-1)=b(n)^2.
If c(n) is sequence A004019, then c(n)=a(2^n-1).
A004019 (and Aho and Sloane) give a closed formula for c(n) that translates to a(n) = nearest integer to b^((n+1)/2) - 1" where b = 2.25851...; the formula gives the asymptotic behavior of this sequence, however it does not compute the correct values for a(n) unless n+1 is a power of two.
Comments