cp's OEIS Frontend

A157679 Number of subtrees of a complete binary tree.

%I A157679 #33 Jan 09 2025 09:53:56
%S A157679 0,1,2,4,6,9,15,25,35,49,70,100,160,256,416,676,936,1296,1800,2500,
%T A157679 3550,5041,7171,10201,16261,25921,41377,66049,107169,173889,282309,
%U A157679 458329,634349,877969,1215289,1682209,2335897,3243601,4504301,6255001,8881051,12609601
%N A157679 Number of subtrees of a complete binary tree.
%C A157679 Take the complete binary tree with n labeled nodes. Here is a poor picture of the tree with 6 nodes:
%C A157679         R
%C A157679        / \
%C A157679       /   \
%C A157679      /     \
%C A157679     o       o
%C A157679    / \     /
%C A157679   o   o   o
%C A157679 Then the number of rooted subtrees of the graph is a(n).
%H A157679 Alois P. Heinz, <a href="/A157679/b157679.txt">Table of n, a(n) for n = 0..5971</a>
%H A157679 A. V. Aho and N. J. A. Sloane, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/11-4/aho-a.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
%H A157679 A. V. Aho and N. J. A. Sloane, <a href="/A000058/a000058.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
%H A157679 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A157679 a(0) = 0, a(1) = 1.
%F A157679 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))).
%F A157679 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.
%F A157679 If c(n) is sequence A004019, then c(n)=a(2^n-1).
%F A157679 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.
%e A157679 For n = 3, the a(3) = 4 subtrees are:
%e A157679   R   R   R      R
%e A157679      /     \    / \
%e A157679     o       o  o   o
%p A157679 a:= proc(n) option remember; `if`(n<2, n,
%p A157679      (h-> (1+a(h))*(1+a(n-1-h)))(iquo(n, 2)))
%p A157679     end:
%p A157679 seq(a(n), n=0..50);  # _Alois P. Heinz_, Jan 02 2022
%t A157679 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 *)
%Y A157679 Cf. A004019, A005468.
%K A157679 easy,nice,nonn
%O A157679 0,3
%A A157679 _Paolo Bonzini_, Mar 04 2009