login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157679 Number of subtrees of a complete binary tree. 0
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Take the complete binary tree with n labeled nodes. Here is a poor picture of the tree with 6 nodes:
R
/ \
/ \
/ \
o o
/ \ /
o o o
Then the number of rooted subtrees of the graph is a(n).
LINKS
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437, alternative link.
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(2n-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.
EXAMPLE
For n = 3, the a(3) = 4 subtrees are:
R R R R
/ \ / \
o o o o
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 *)
CROSSREFS
Sequence in context: A024787 A266648 A076922 * A057602 A171646 A074677
KEYWORD
easy,nice,nonn
AUTHOR
Paolo Bonzini, Mar 04 2009
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:12 EDT 2024. Contains 371254 sequences. (Running on oeis4.)