A195581 -id:A195581 - cp's OEIS frontend

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

1, 1, 1, 1, 4, 5, 5, 10, 15, 18, 102, 114, 246, 394, 1051, 3044, 50263, 111686, 128162, 273256, 583069, 927699, 7299350, 10833746, 15187876, 67314562, 2141820499, 4969978969, 10131201410, 49316153957, 221808008142, 275241196373, 1466049587038, 3406190692970

Offset: 1

Alois P. Heinz, Sep 21 2011

nonn

alpha = 4.31107040700100503504707609644689027839156299804028805066937... is used to measure the expected height of random binary search trees.

Cf. A006784 for definition of Engel expansion.

F. Engel, Entwicklung der Zahlen nach Stammbrüchen, Verhandlungen der 52. Versammlung deutscher Philologen und Schulmänner in Marburg, 1913, pp. 190-191.

F. Engel, Entwicklung der Zahlen nach Stammbruechen, Verhandlungen der 52. Versammlung deutscher Philologen und Schulmaenner in Marburg, 1913, pp. 190-191. English translation by Georg Fischer, included with his permission.
P. Erdős and Jeffrey Shallit, New bounds on the length of finite Pierce and Engel series, Sem. Theor. Nombres Bordeaux (2) 3 (1991), no. 1, 43-53.
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Eric Weisstein's World of Mathematics, Engel Expansion
Wikipedia, Engel Expansion
Index entries for sequences related to Engel expansions

Cf. A195596 (decimal expansion), A195597 (continued fraction), A195581, A195582, A195583, A195599, A195600, A195601.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
engel:= (r, n)-> `if`(n=0 or r=0, NULL, [ceil(1/r), engel(r*ceil(1/r)-1, n-1)][]):
Digits:=400: engel(evalf(alpha), 39);

alpha = -1/W(-exp(-1)/2), where W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with beta = 1.953... (A195599).

A335919 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.

Original entry on oeis.org

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, 94, 3340, 10856, 15248, 14272, 9600, 4352, 1024, 60, 5976, 27672, 47104, 50784, 40576, 24064

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, Rows n = 0..200, 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, A073429 (another version with 0's), A076615, A195581, A244108, A335920 (the same read by columns), A335921, 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):
seq(seq(T(n, k), k=g(n)..n), n=0..12);

g[n_] := If[n == 0, 0, Floor@Log[2, 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];
Table[Table[T[n, k], {k, g[n], n}], {n, 0, 12}] // 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).

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

A316944 Total height of the binary search trees summed over all permutations of [n].

Original entry on oeis.org

0, 1, 4, 16, 80, 456, 3072, 23536, 202304, 1937920, 20470400, 236172288, 2955465216, 39893618688, 577937479680, 8944476580864, 147277509541888, 2570740210700288, 47418288632692736, 921669646969167872, 18829500772271472640, 403390045252173381632

Offset: 0

Alois P. Heinz, Jul 17 2018

nonn

Each permutation of [n] generates a binary search tree of height h (floor(log_2(n))+1 <= h <= n) when its elements are inserted in that order into the initially empty tree. The average height of a binary search tree on n elements is A195582(n)/A195583(n).

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

			a(3) = 16 = 3 + 3 + (2+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   (2,1,3)   o   o         o   o
     (3,2,1)     (3,1,2)  (2,3,1)    (1,3,2)   (1,2,3)
.

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

Cf. A000142, A000523, A195581, A195582, A195583, A244108, A335921.

b:= proc(n, k) option remember; `if`(n<2, `if`(k add(k*(b(n, k)-b(n, k-1)), k=0..n):
seq(a(n), n=0..25);

b[n_, k_] := b[n, k] = If[n < 2, If[k < n, 0, 1], Sum[Binomial[n - 1, r]* b[r, k - 1] b[n - 1 - r, k - 1], {r, 0, n - 1}]];
a[n_] := Sum[k(b[n, k] - b[n, k - 1]), {k, 0, n}];
a /@ Range[0, 25] (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} k * A195581(n,k) = Sum_{k=0..n} k * A244108(n,k).

a(n) = A000142(n) * A195582(n)/A195583(n).

A317012 Total number of elements in all permutations of [n], [n+1], ... that result in a binary search tree of height n.

Original entry on oeis.org

0, 1, 10, 1316, 840124672, 6110726696100443604557936, 439451426203104201222708341688051362423089952907263634936946272224

Offset: 0

Alois P. Heinz, Jul 18 2018

nonn

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

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

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

Cf. A195581, A227822, A244108, A335922.

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

b[n_, k_] := b[n, k] = If[n < 2, If[k < n, 0, 1],
  Sum[Binomial[n-1, r] b[r, k-1] b[n-1-r, k-1], {r, 0, n-1}]];
T[n_, k_] := b[n, k] - b[n, k-1];
a[k_] := Sum[T[n, k] n, {n, k, 2^k - 1}];
a /@ Range[0, 6] (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

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

A227822 Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.

Original entry on oeis.org

1, 1, 4, 220, 60092152, 203720181459953921762400, 7088043372247785801830314829178419617696182324188730917543544992

Offset: 0

Alois P. Heinz, Jul 31 2013

nonn

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

			a(2) = 4, because 4 permutations of {1,2}, {1,2,3}, ... result in a binary search tree of height 2:
  (1,2):   1      (2,1):   2    (2,1,3), (2,3,1):    2
          / \             / \                      /   \
         o   2           1   o                    1     3
            / \         / \                      / \   / \
           o   o       o   o                    o   o o   o

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

Column sums of A195581 and of A244108.

Cf. A317012.

b:= proc(n, k) option remember; `if`(n<2, `if`(k add(b(k, n)-b(k, n-1), k=n..2^n-1):
seq(a(n), n=0..6);

b[n_, k_] := b[n, k] = If[n < 2, If[k < n, 0, 1],
   Sum[Binomial[n - 1, r]*b[r, k - 1]*b[n - 1 - r, k - 1], {r, 0, n - 1}]];
a[n_] := Sum[b[k, n] - b[k, n - 1], {k, n, 2^n - 1}];
a /@ Range[0, 6] (* Jean-François Alcover, Apr 02 2021, after Alois P. Heinz *)

a(n) = Sum_{k=n..2^n-1} A195581(k,n).

Terms corrected by Alois P. Heinz, Dec 08 2015

A265846 Number of permutations of {1,2,...,2n} that result in a binary search tree of height n.

Original entry on oeis.org

1, 0, 0, 80, 11360, 1508032, 197163648, 27624399104, 4256968553472, 724948555548672, 136034167652859904, 27976811931437752320, 6269253131872946298880, 1522110257603797873737728, 398311795891656532955725824, 111813044381693547723191418880

Offset: 0

Alois P. Heinz, Dec 21 2015

nonn

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

Cf. A195581, A244108.

b:= proc(n, k) option remember; `if`(n<2, `if`(k b(2*n, n)-b(2*n, n-1):
seq(a(n), n=0..20);

b[n_, k_] := b[n, k] = If[n<2, If[kJean-François Alcover, Feb 25 2017, translated from Maple *)

a(n) = A195581(2n,n) = A244108(2n,n).

a(n) ~ c * d^n * (n-1)!, where d = -16*LambertW(-1, -exp(-1/2)/2)^2 / (1 + 2*LambertW(-1, -exp(-1/2)/2)) = 19.643259858273023595006139220961408..., c = 1/(2^(5/2)*Pi*sqrt(-1 - LambertW(-1, -exp(-1/2)/2))) = 0.0646979349409396546649864277836... . - Vaclav Kotesovec, Jan 02 2016, updated Mar 17 2024 and May 14 2025

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

A242461 Decimal expansion of the first positive solution to exp(1-1/x)/x = 1/2, a binary search tree constant.

Original entry on oeis.org

3, 7, 3, 3, 6, 4, 6, 1, 7, 7, 0, 1, 6, 7, 4, 0, 8, 4, 2, 4, 8, 4, 4, 8, 4, 3, 6, 6, 7, 9, 2, 7, 0, 5, 9, 5, 0, 0, 2, 5, 7, 6, 4, 6, 7, 0, 0, 4, 2, 7, 7, 3, 8, 4, 4, 4, 4, 9, 3, 8, 5, 7, 0, 3, 1, 5, 1, 3, 0, 5, 6, 5, 5, 1, 3, 3, 5, 3, 3, 3, 5, 5, 8, 8, 8, 1, 6, 9, 8, 8, 9, 0, 6, 5, 0, 3, 8, 8, 6, 8

Offset: 0

Jean-François Alcover, May 15 2014

The saturation level S_n of a binary search tree defined by a random n-permutation is such that S_n/log(n) converges to 0.3733646... in probability.

			0.373364617701674084248448436679270595...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 349-352.

Luc Devroye, A Note on the Height of Binary Search Trees. McGill University, Montreal, Canada (1986).

Cf. A076615, A076616, A195581, A195582, A195596.

RealDigits[-1/ProductLog[-1, -1/(2*E)], 10, 100] // First

-1/W(-1, -1/(2*e)) where W is the Lambert W function (ProductLog).

cp's OEIS Frontend

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alpha*log((2*e)/alpha)=1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

A335919 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A316944 Total height of the binary search trees summed over all permutations of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317012 Total number of elements in all permutations of [n], [n+1], ... that result in a binary search tree of height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A227822 Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A265846 Number of permutations of {1,2,...,2n} that result in a binary search tree of height n.

Views

Author

Keywords

Links

Crossrefs

Programs

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.