A335919 -id:A335919 - cp's OEIS frontend

A001699 Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutative and non-associative.

1, 1, 3, 21, 651, 457653, 210065930571, 44127887745696109598901, 1947270476915296449559659317606103024276803403, 3791862310265926082868235028027893277370233150300118107846437701158064808916492244872560821

Offset: 0

N. J. A. Sloane and Jeffrey Shallit

Approaches 1.5028368...^(2^n), see A077496. Row sums of A065329 as square array. - Henry Bottomley, Oct 29 2001. Also row sum of square array A073345 (AK).

			G.f. = 1 + x + 3*x^2 + 21*x^3 + 651*x^4 + 457653*x^5 + ... - _Michael Somos_, Jun 02 2019

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
T. K. Moon, Enumerations of binary trees, types of trees and the number of reversible variable length codes, submitted to Discrete Applied Mathematics, 2000.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

David Wasserman, Table of n, a(n) for n = 0..12 [Shortened file because terms grow rapidly: see Wasserman link below for an additional term]
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!)
Mayfawny Bergmann, Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 2, Article 1. (2014).
Henry Bottomley, Illustration of initial terms
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Claude Lenormand, Arbres et permutations II, see p. 6
David E. Narváez, Proof of polynomial recursive equation of order 2, Jun 05 2025.
David Wasserman, Table of n, a(n) for n = 0..13
Eric Weisstein's World of Mathematics, Binary Tree
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for sequences related to parenthesizing
Index entries for sequences of form a(n+1)=a(n)^2 + ...

Row sums of A065329.
Column sums of A335919, A335920.
Cf. A002658, A056207, A002449, A003095.
Cf. A004019, A077496, A076949, A213437.

s := proc(n) local i,j,ans; ans := [ 1 ]; for i to n do ans := [ op(ans),2*(add(j,j=ans)-ans[ i ])*ans[ i ]+ans[ i ]^2 ] od; RETURN(ans); end; s(10);

a[0] = 1; a[n_] := a[n] = 2*a[n-1]*Sum[a[k], {k, 0, n-2}] + a[n-1]^2; Table[a[n], {n, 0, 9}] (* Jean-François Alcover, May 16 2012 *)
a[ n_] := If[ n < 2, Boole[n >= 0], With[{u = a[n - 1], v = a[n - 2]}, u (u + v + u/v)]]; (* Michael Somos, Jun 02 2019 *)

{a(n) = if( n<=1, n>=0, a(n-1) * (a(n-1) + a(n-2) + a(n-1) / a(n-2)))}; /* Michael Somos, 2000 */

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return 1 if n <= 1 else a(n-1) * (a(n-1) + a(n-2) + a(n-1)//a(n-2))
print([a(n) for n in range(10)]) # Michael S. Branicky, Nov 10 2022 after Michael Somos

a(n+1) = 2*a(n)*(a(0) + ... + a(n-1)) + a(n)^2.
a(n+1) = a(n)^2 + a(n) + a(n)*sqrt(4*a(n)-3), if n > 0.
a(n) = A003095(n+1) - A003095(n) = A003095(n)^2 - A003095(n) + 1. - Henry Bottomley, Apr 26 2001; offset of LHS corrected by Anindya Bhattacharyya, Jun 21 2013
a(n) = A059826(A003095(n-1)).
From Peter Bala, Feb 03 2017: (Start)
a(n) = Product_{k = 1..n} A213437(k).
a(n) + a(n-1) = A213437(n+1) - A213437(n). (End)
a(n) = -a(n-2)^3 + a(n-1)^2 + 3*a(n-1)*a(n-2) + 2*a(n-2)^2 + 2*a(n-1) - 4*a(n-2) (see Narváez link for proof). - Boštjan Gec, Oct 10 2024

Minor edits by Vaclav Kotesovec, Oct 04 2014

A335920 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 6, 4, 1, 8, 20, 40, 68, 94, 114, 116, 94, 60, 28, 8, 1, 16, 56, 152, 376, 844, 1744, 3340, 5976, 10040, 15856, 23460, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 32, 144, 480, 1440, 4056

Offset: 0

Alois P. Heinz, Jun 29 2020

Empty external nodes are counted in determining the height of a search tree.

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.

			Triangle T(n,k) begins:
  1;
     1;
        2;
        1, 4;
           6,   8;
           6,  20,   16;
           4,  40,   56,   32;
           1,  68,  152,  144,   64;
               94,  376,  480,  352,  128;
              114,  844, 1440, 1376,  832,  256;
              116, 1744, 4056, 4736, 3712, 1920, 512;
  ...

Alois P. Heinz, Columns k = 0..10, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000108.
Column sums give A001699.
Main diagonal gives A011782.
T(n+3,n+2) gives A014480.
T(n,max(0,A000523(n)+1)) = A328349(n).
Cf. A073345, A076615, A195581, A244108, A335919 (the same read by rows), A335921, A335922.

b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
seq(seq(T(n, k), n=k..2^k-1), k=0..6);

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
Table[Table[T[n, k], {n, k, 2^k - 1}], {k, 0, 6}] // Flatten (* Jean-François Alcover, Feb 08 2021, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A335921(n).

Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).

A335921 Total height of all binary search trees with n internal nodes.

Original entry on oeis.org

0, 1, 4, 14, 50, 178, 644, 2347, 8624, 31908, 118768, 444308, 1669560, 6298280, 23842032, 90531032, 344702646, 1315726218, 5033357852, 19294463682, 74099098212, 285056401796, 1098314920968, 4237879802726, 16373796107092, 63341371265892, 245315823125496

Offset: 0

Alois P. Heinz, Jun 29 2020

nonn

Empty external nodes are counted in determining the height of a search tree.

			a(3) = 14 = 3 + 3 + 2 + 3 + 3:
.
          3         3        2        1         1
         / \       / \      / \      / \       / \
        2   o     1   o    1   3    o   3     o   2
       / \       / \      ( ) ( )      / \       / \
      1   o     o   2     o o o o     2   o     o   3
     / \           / \               / \           / \
    o   o         o   o             o   o         o   o
.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A083420, A316944, A335919, A335920, A335922.

g:= n-> `if`(n=0, 0, ilog2(n)+1):
b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n, k)*k, k=g(n)..n):
seq(a(n), n=0..35);

g[n_] := If[n == 0, 0, Floor@Log2[n] + 1];
b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
a[n_] := Sum[T[n, k]*k, {k, g[n], n}];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Apr 26 2022, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} k * A335919(n,k) = Sum_{k=0..n} k * A335920(n,k).

a(n) is odd <=> n in { A083420 }.

A335922 Total number of internal nodes in all binary search trees of height n.

Original entry on oeis.org

0, 1, 7, 97, 6031, 8760337, 8245932762607, 3508518207942911995940881, 311594265746788494170059418351454897488270152687

Offset: 0

Alois P. Heinz, Jun 29 2020

nonn

Empty external nodes are counted in determining the height of a search tree.

			a(2) = 7 = 2 + 3 + 2:
.
         2        2        1
        / \      / \      / \
       1   o    1   3    o   2
      / \      ( ) ( )      / \
     o   o     o o o o     o   o
.

Alois P. Heinz, Table of n, a(n) for n = 0..12
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A317012, A335919, A335920, A335921.

b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= k-> add(T(n, k)*n, n=k..2^k-1):
seq(a(n), n=0..10);

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
a[k_] := Sum[T[n, k]*n, {n, k, 2^k - 1}];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Apr 26 2022, after Alois P. Heinz *)

a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n).

A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 4, 1, 94, 114, 116, 94, 60, 28, 8, 1, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 5193067630, 6939692682, 8948546308, 11120136162, 13299362332, 15286065700, 16859410792, 17813777994, 17999433372

Offset: 0

Viktar Karatchenia, Oct 13 2019

For any BST node p, p.left.value < p.value and p.right.value > p.value provided that the left (right) node exists.

			a(1) = 1 - the trivial tree having 1 node.
a(2) = 2 - two trees: one {1,2} rooted at node 1, and {2,1} - at 2.
a(3) = 1 - one BST tree of height 1 with edges {1,2}, {2,3} rooted at the node 2.
      2
    1   3
a(4) = 6. Optimal BST height is 2. When the root is 1, the remaining nodes {2,3,4} can form 1 subtree having height 1. Taking 2 as the root, 1 must go to the left, and {3,4} - right; there can be 2 trees on {3,4}. The cases for root 4,3 are symmetric. Thus, a(4) = 2*(1+1*2) = 6. The 6 BSTs of the optimal height 2 are: ({1,3},{3,2},{3,4}), ({2,1},{2,3},{3,4}), ({2,1},{2,4},{4,3}), ({3,4},{3,2},{2,1}), ({3,4},{3,1},{1,2}), ({4,2},{2,1},{2,3}).
a(5) = 1+1+2*2 = 6. Height=2. Nodes 1,5 cannot be the root, because the remaining 4 nodes cannot be compressed into a BST of height 1. Node 2 as the root implies {3,4,5} must follow to the right (left) producing 1 tree. Node 4 similarly adds 1 more BST. Finally, 3 as the root allows the formation of 2 trees consisting of {1,2} to the left of the root, and 2 trees of {4,5} to the right giving 2*2 = 4 trees.
a(6) = 4. Here height = 2. The nodes 1,2,5,6 can't be the root. When rooting at the third node, {1,2} will form 2 trees, and {4,5,6} to the right will make 1 possible tree of height 1. The node 4 is similar to 3. In total, a(6) = 2*1*2 = 4.

Alois P. Heinz, Table of n, a(n) for n = 0..1023
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000225, A000523, A076615, A195581, A244108, A335919, A335920.

# after C++ program
const _cache = Dict{Tuple{Int, Int}, Int}()
function f(k::Int, level::Int)
    (k >= 1 << level) && return 0
    level = min(k, level)
    haskey(_cache, (k, level)) && return _cache[(k, level)]
    r = 0
    for root in 1:k
        left  = root == 1 ? 1 : f(root - 1, level - 1)
        right = root == k ? 1 : f(k - root, level - 1)
        r += left * right
    end
    return _cache[k, level] = r
end
BinaryIntegerLength(n) = n == 0 ? 1 : floor(Int, log2(n)) + 1
[f(n, BinaryIntegerLength(n)) for n in 1:40] |> println # Peter Luschny, Oct 14 2019

b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
a:= n-> b(n, ilog2(n)+1):
seq(a(n), n=0..42);  # Alois P. Heinz, Jun 28 2020

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n<2^h, Sum[b[j-1, h-1] b[n-j, h-1], {j, 1, n}], 0]];
a[n_] := b[n, Floor@Log[2, n]+1];
a /@ Range[0, 42] (* Jean-François Alcover, Nov 15 2020, after Alois P. Heinz *)

a(n) = 1 when n = 2^m - 1, m > 0 because the optimal BST represents a full binary tree thus precisely 1 tree is possible.
a(n) = 2^(m-1) when n = 2^m - 2, m > 1. Here the BST is full BST minus 1 node, which must be at the last level. The last level of a full BST has 2^(m-1) nodes. Once the "missing" node is chosen at the last level, there is only 1 BST.
a(n) = f(n, 1+floor(log_2(n))) where f(k, level) is 0 when there are too many nodes (k >= 2^ level), otherwise f(k, level) = Sum_{root=1..n}(root=1 ? 1 : f(root-1, level-1)) * (root=k ? 1 : f(k-root, level-1))).
a(n) = A335919(n,max(0,A000523(n)+1)) = A335920(n,max(0,A000523(n)+1)). - Alois P. Heinz, Jun 29 2020

a(0)=1 prepended by Alois P. Heinz, Jun 28 2020

cp's OEIS Frontend

A001699 Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutative and non-associative.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A335920 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335921 Total height of all binary search trees with n internal nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335922 Total number of internal nodes in all binary search trees of height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

Extensions