A195582 -id:A195582 - cp's OEIS frontend

A195581 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 0, 2, 0, 0, 2, 4, 0, 0, 0, 16, 8, 0, 0, 0, 40, 64, 16, 0, 0, 0, 80, 400, 208, 32, 0, 0, 0, 80, 2240, 2048, 608, 64, 0, 0, 0, 0, 11360, 18816, 8352, 1664, 128, 0, 0, 0, 0, 55040, 168768, 104448, 30016, 4352, 256, 0, 0, 0, 0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512

Offset: 0

Alois P. Heinz, Sep 20 2011

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

			T(3,3) = 4, because 4 permutations of {1,2,3} result in a binary search tree of height 3:
  (1,2,3):   1       (1,3,2):   1     (3,1,2):   3   (3,2,1):   3
            / \                / \              / \            / \
           o   2              o   3            1   o          2   o
              / \                / \          / \            / \
             o   3              2   o        o   2          1   o
                / \            / \              / \        / \
               o   o          o   o            o   o      o   o
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0, 2;
  0, 0, 2,  4;
  0, 0, 0, 16,      8;
  0, 0, 0, 40,     64,      16;
  0, 0, 0, 80,    400,     208,      32;
  0, 0, 0, 80,   2240,    2048,     608,     64;
  0, 0, 0,  0,  11360,   18816,    8352,   1664,   128;
  0, 0, 0,  0,  55040,  168768,  104448,  30016,  4352,   256;
  0, 0, 0,  0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000142. Column sums give A227822.
Main diagonal gives A011782, lower diagonal gives A076616.
T(n,A000523(n)+1) = A076615(n).
T(2^n-1,n) = A056972(n).
T(2n,n) = A265846(n).
Cf. A195582, A195583, A244108 (the same read by columns), A316944, A317012.

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

b[n_, k_] := b[n, k] = If[n == 0, 1, If[n == 1, If[k > 0, 1, 0], Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}] ] ]; t [n_, k_] := b[n, k] - If[k > 0, b[n, k-1], 0]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

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

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

A195583 Denominator of the average height of a binary search tree on n elements.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 15, 315, 630, 567, 1134, 4725, 9450, 26325, 28665, 116093250, 116093250, 7894341000, 8881133625, 14849255421000, 4242644406000, 3118343638410000, 3811308891390000, 34301780022510000, 205810680135060000, 1470076286679000000, 2702564486622000000

Offset: 0

Alois P. Heinz, Sep 20 2011

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

See A195582 for more information.

Maple
```
seq(denom(a(n)), n=0..25);
```

A244108 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Original entry on oeis.org

1, 1, 2, 2, 4, 16, 40, 80, 80, 8, 64, 400, 2240, 11360, 55040, 253440, 1056000, 3801600, 10982400, 21964800, 21964800, 16, 208, 2048, 18816, 168768, 1508032, 13501312, 121362560, 1099169280, 10049994240, 92644597760, 857213660160, 7907423180800, 72155129446400

Offset: 0

Alois P. Heinz, Dec 21 2015

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

			Triangle T(n,k) begins:
: 1;
:    1;
:       2;
:       2,  4;
:          16,      8;
:          40,     64,      16;
:          80,    400,     208,      32;
:          80,   2240,    2048,     608,     64;
:               11360,   18816,    8352,   1664,   128;
:               55040,  168768,  104448,  30016,  4352,   256;
:              253440, 1508032, 1277568, 479040, 99200, 11008, 512;

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

Row sums give A000142.
Column sums give A227822.
Main diagonal gives A011782, lower diagonal gives A076616.
T(n,A000523(n)+1) = A076615(n).
T(2^n-1,n) = A056972(n).
T(2n,n) = A265846(n).
Cf. A195581 (the same read by rows), A195582, A195583, A316944, A317012.

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

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

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

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

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

Original entry on oeis.org

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

Offset: 1

Alois P. Heinz, Sep 21 2011

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

			4.31107040700100503504707609644689027839156299804028805066937...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.13 Binary search tree constants, p. 352.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Luc Devroye, A note on the height of binary search trees, Journal of the ACM, Vol. 33, No. 3 (1986), pp. 489-498.
Bruce Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
John Michael Robson, The height of binary search trees, Australian Computer Journal, Vol. 11, No. 4 (1979), pp. 151-153. [broken link]
Larry Shepp, Doron Zeilberger and Cun-Hui Zhang, Pick up sticks, arXiv preprint arXiv:1210.5642 [math.CO] (2012).
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A195597 (continued fraction), A195598 (Engel expansion), A195581, A195582, A195583, A195599, A195600, A195601.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
as:= convert(evalf(alpha/10, 130), string):
seq(parse(as[n+1]), n=1..120);

RealDigits[ -1/ProductLog[-1/(2*E)] , 10, 105] // First (* Jean-François Alcover, Feb 19 2013 *)

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

A195599 Decimal expansion of beta = 3/(2*log(alpha/2)), where alpha = A195596.

Original entry on oeis.org

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

Offset: 1

Alois P. Heinz, Sep 21 2011

beta is used to measure the expected height of random binary search trees.

			1.95302570335815413945406288542575380414251340201036319609354...

Alois P. Heinz, Table of n, a(n) for n = 1..10000
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A195600 (continued fraction), A195601 (Engel expansion), A195581, A195582, A195583, A195596, A195597, A195598.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
bs:= convert(evalf(beta/10, 130), string):
seq(parse(bs[n+1]), n=1..120);

RealDigits[ 3/(2 + 2*ProductLog[-1/(2*E)]) , 10, 105] // First (* Jean-François Alcover, Feb 19 2013 *)

beta = 3/(2*log(alpha/2)) = 3*alpha/(2*alpha-2), where alpha = A195596 = -1/W(-exp(-1)/2) and W is the Lambert W function.

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

A195600 Continued fraction for beta = 3/(2*log(alpha/2)); alpha = A195596.

Original entry on oeis.org

1, 1, 20, 3, 2, 7, 1, 1, 1, 12, 1, 5, 1, 91, 1, 1, 3, 87, 2, 1, 1, 1, 1, 3, 1, 9, 3, 2, 1, 1, 1, 1, 190, 1, 3, 1, 82, 2, 1, 1, 1, 2, 1, 1, 1, 6, 1, 2, 12, 6, 2, 2, 2, 3, 2, 1, 1, 1, 2, 3, 21, 1, 1, 12, 1, 7, 3, 2, 26, 3, 2, 1, 1, 1, 9, 1, 15, 4, 3, 3, 1, 3, 1

Offset: 0

Alois P. Heinz, Sep 21 2011

beta is used to measure the expected height of random binary search trees.

			1.95302570335815413945406288542575380414251340201036319609354...

B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.

Cf. A195599 (decimal expansion), A195601 (Engel expansion), A195581, A195582, A195583, A195596, A195597, A195598.

with(numtheory):
alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
cfrac(evalf(beta, 130), 100, 'quotients')[];

beta = 3/(2+2*ProductLog[-1/(2*E)]); ContinuedFraction[beta, 83] (* Jean-François Alcover, Jun 20 2013 *)

beta = 3/(2*log(alpha/2)) = 3*alpha/(2*alpha-2), where alpha = A195596 = -1/W(-exp(-1)/2) and W is the Lambert W function.

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

Offset changed by Andrew Howroyd, Jul 03 2024

A195601 Engel expansion of beta = 3/(2*log(alpha/2)); alpha = A195596.

Original entry on oeis.org

1, 2, 2, 2, 2, 5, 5, 5, 20, 36, 78, 842, 5291, 10373, 17340, 28619, 35586, 93572, 98045, 2470364, 13603654, 14328528, 16490766, 833971648, 1788088151, 9592330101, 10952282168, 40005288076, 54302548920, 118523737357, 776601533408, 1241894797770, 24485470725324

Offset: 1

Alois P. Heinz, Sep 21 2011

nonn

beta = 1.95302570335815413945406288542575380414251340201036319609354... 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.

G. C. Greubel, Table of n, a(n) for n = 1..1000
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. A195599 (decimal expansion), A195600 (continued fraction), A195581, A195582, A195583, A195596, A195597, A195598.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
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(beta), 39);

f:= N[-1/ProductLog[-1/(2*E)], 500001]; EngelExp[A_, n_]:= Join[Array[1 &, Floor[A]], First@Transpose@NestList[{Ceiling[1/Expand[#[[1]] #[[2]] - 1]], Expand[#[[1]] #[[2]] - 1]} &, {Ceiling[1/(A - Floor[A])], A - Floor[A]}, n - 1]]; EngelExp[N[3/(2*Log[f/2]), 500000], 25] (* G. C. Greubel, Oct 21 2016 *)

beta = 3/(2*log(alpha/2)) = 3*alpha/(2*alpha-2), where alpha = A195596 = -1/W(-exp(-1)/2) and W is the Lambert W function.

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

A195597 Continued fraction for alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

Original entry on oeis.org

4, 3, 4, 1, 1, 1, 11, 2, 19, 1, 3, 1, 1, 1, 14, 1, 3, 5, 58, 3, 1, 10, 1, 1, 6, 5, 13, 127, 1, 1, 7, 13, 1, 2, 1, 2, 2, 1, 2, 2, 4, 2, 4, 1, 1, 6, 9, 3, 1, 16, 1, 3, 2, 32, 3, 1, 1, 2, 11, 1, 13, 4, 2, 1, 1, 1, 1, 2, 2, 6, 1, 1, 1, 2, 25, 1, 5, 5, 1, 1, 1, 1, 5, 2, 3, 2, 5, 25, 1, 190, 2, 1, 5, 3, 1, 20, 1, 1, 2, 1, 3

Offset: 0

Alois P. Heinz, Sep 21 2011

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

			4.31107040700100503504707609644689027839156299804028805066937...

B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.

Cf. A195596 (decimal expansion), A195598 (Engel expansion), A195581, A195582, A195583, A195599, A195600, A195601.

with(numtheory):
alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
cfrac(evalf(alpha, 130), 100, 'quotients')[];

alpha = -1/ProductLog[-1/(2*E)]; ContinuedFraction[alpha, 101] (* Jean-François Alcover, Jun 20 2013 *)

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

Offset changed by Andrew Howroyd, Jul 03 2024

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

Original entry on oeis.org

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

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

cp's OEIS Frontend

A195581 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195583 Denominator of the average height of a binary search tree on n elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A244108 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; 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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195599 Decimal expansion of beta = 3/(2*log(alpha/2)), where alpha = A195596.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195600 Continued fraction for beta = 3/(2*log(alpha/2)); alpha = A195596.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A195601 Engel expansion of beta = 3/(2*log(alpha/2)); alpha = A195596.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

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

A195597 Continued fraction for alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

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