|
| |
|
|
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
(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
|
Table of n, a(n) for n=0..32.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.
Index entries for sequences related to rooted trees
|
|
|
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 example, for n = 3 the a(3) = 4 subtrees are:
R...R...R......R
.../.....\..../.\
..o.......o..o...o
|
|
|
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}] (* From Jean-François Alcover, Oct 19 2011 *)
|
|
|
CROSSREFS
|
Cf. A004019, A005468
Sequence in context: A127740 A024787 A076922 * A057602 A171646 A006498
Adjacent sequences: A157676 A157677 A157678 * A157680 A157681 A157682
|
|
|
KEYWORD
|
easy,nice,nonn
|
|
|
AUTHOR
|
Paolo Bonzini, Mar 04 2009, Mar 09 2009
|
|
|
STATUS
|
approved
|
| |
|
|
