A005468 -id:A005468 - cp's OEIS frontend

A005469 a(n) = 1 + a(floor(n/2))*a(ceiling(n/2)) for n > 1, a(1) = 2.

2, 5, 11, 26, 56, 122, 287, 677, 1457, 3137, 6833, 14885, 35015, 82370, 194300, 458330, 986390, 2122850, 4570610, 9840770, 21435122, 46689890, 101709206, 221563226, 521198276, 1226050226, 2884185551, 6784816901, 16004491001, 37752490001, 89053519001

Offset: 1

Colin Mallows

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A005468.

a:= proc(n) option remember; `if`(n=1, 2,
      1+(t->a(t)*a(n-t))(iquo(n, 2)))
    end:
seq(a(n), n=1..35);  # Alois P. Heinz, Jul 04 2019

a[n_] := a[n] = If[n==1, 2, 1 + a[Floor[n/2]] a[Ceiling[n/2]]];
a /@ Range[35] (* Jean-François Alcover, Nov 16 2020 *)

A157679 Number of subtrees of a complete binary tree.

Original entry on oeis.org

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

Paolo Bonzini, Mar 04 2009

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).

			For n = 3, the a(3) = 4 subtrees are:
  R   R   R      R
     /     \    / \
    o       o  o   o

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

Cf. A004019, A005468.

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

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 *)

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.

A005510 a(n) = 1 + a(floor(n/2))*a(ceiling(n/2)) for n > 1, a(1) = 3.

Original entry on oeis.org

3, 10, 31, 101, 311, 962, 3132, 10202, 31412, 96722, 299183, 925445, 3012985, 9809425, 31952665, 104080805, 320465225, 986713745, 3038231465, 9355145285, 28937578127, 89510467490, 276877411436, 856448448026, 2788351903326, 9078078610226, 29555650383626

Offset: 1

Colin Mallows

All terms are congruent to 3 mod 7.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A005468, A005469.

a:= proc(n) option remember; `if`(n=1, 3,
      1+(t->a(t)*a(n-t))(iquo(n, 2)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jul 04 2019

cp's OEIS Frontend

A005469 a(n) = 1 + a(floor(n/2))*a(ceiling(n/2)) for n > 1, a(1) = 2.

Views

Author

Keywords

References

Crossrefs

Programs

Maple

Mathematica

A157679 Number of subtrees of a complete binary tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005510 a(n) = 1 + a(floor(n/2))*a(ceiling(n/2)) for n > 1, a(1) = 3.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple