A195581 -id:A195581 - cp's OEIS frontend

A195582 Numerator of the average height of a binary search tree on n elements.

0, 1, 2, 8, 10, 19, 64, 1471, 3161, 3028, 6397, 27956, 58307, 168652, 190031, 794076401, 817191437, 57056556523, 65776878541, 112508501827291, 32836043478431, 24620974441660973, 30663050241335933, 280904716386831931, 1713934856212591039, 12438570098319186469

Offset: 0

Alois P. Heinz, Sep 20 2011

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

			0/1, 1/1, 2/1, 8/3, 10/3, 19/5, 64/15, 1471/315, 3161/630, 3028/567, 6397/1134, 27956/4725, 58307/9450, 168652/26325, 190031/28665 ... = A195582/A195583
For n = 3 there are 2 permutations of {1,2,3} resulting in a binary search tree of height 2 and 4 permutations resulting in a tree of height 3.  The average height is (2*2+4*3)/3! = (4+12)/6 = 16/6 = 8/3.

Alois P. Heinz, Table of n, a(n) for n = 0..478
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

Denominators: A195583.

Cf. A000142, A195581, A195596, A195597, A195598, A195599, A195600, A195601, A244108, A316944.

b:= proc(n,k) option remember;
      if n=0 then 1
    elif n=1 then `if`(k>0, 1, 0)
    else add(binomial(n-1,r-1) *b(r-1,k-1) *b(n-r,k-1), r=1..n)
      fi
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n,k)*k, k=0..n)/n!:
seq(numer(a(n)), n=0..30);

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]; a[n_] := Sum[T[n, k]*k, {k, 0, n}]/n!; Table[ Numerator[a[n]], {n, 0, 30}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

A195582(n)/A195583(n) = 1/n! * Sum_{k=1..n} k * A195581(n,k).
A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with alpha = 4.311... (A195596) and beta = 1.953... (A195599).
A195582(n)/A195583(n) = A316944(n) / A000142(n).

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

A076615 Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height.

Original entry on oeis.org

1, 1, 2, 2, 16, 40, 80, 80, 11360, 55040, 253440, 1056000, 3801600, 10982400, 21964800, 21964800, 857213660160, 7907423180800, 72155129446400, 645950912921600, 5622693241651200, 47110389109555200, 375570435981312000, 2811021970538496000, 19445103757787136000

Offset: 0

Jeffrey Shallit, Oct 22 2002

nonn

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

			a(3) = 2 because only the permutations (2,1,3) and (2,3,1) result in a binary search tree of minimal height. In both cases you will get the following binary search tree:
        2
      /   \
     1     3
    / \   / \
   o   o o   o

Alois P. Heinz, Table of n, a(n) for n = 0..511 (first 50 terms from Michal Forisek)
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Leftmost nonzero elements in rows of A195581, A244108.

Cf. A076616, A328349.

b:= proc(n,k) option remember;
      if n=0 then 1
    elif n=1 then `if`(k>0, 1, 0)
    else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n)
      fi
    end:
a:= n-> b(n, ilog2(n)+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 20 2011

b[n_, k_] := b[n, k] = Which[n==0, 1, n==1, If[k>0, 1, 0], True, Sum[ Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]]; a[n_] := b[n, Floor @ Log[2, n]+1]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 19 2017, after Alois P. Heinz *)

from math import factorial as f, log, floor
B= {}
def b(n,x):
    if (n,x) in B: return B[(n,x)]
    if n<=1: B[(n,x)] = int(x>=0)
    else: B[(n,x)]=sum([b(i,x-1)*b(n-1-i,x-1)*f(n-1)//f(i)//f(n-1-i) for i in range(n)])
    return B[(n,x)]
for n in range(1,51): print(b(n,floor(log(n,2))))
# Michal Forisek, Sep 19 2011

Let b(n,k) be the number of permutations of {1,2,...,n} that produce a binary search tree of depth at most k. We have:
b(0,k) = 1 for k>=0,
b(1,0) = 0,
b(1,k) = 1 for k>0,
b(n,k) = Sum_{r=1..n} C(n-1,r-1) * b(r-1,k-1) * b(n-r,k-1) for n>=2, k>=0.
Then a(n) = b(n,floor(log_2(n))+1).

Extended beyond a(8) and efficient formula by Michal Forisek, Sep 19 2011

a(0)=1 prepended by Alois P. Heinz, Jul 18 2018

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

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Original entry on oeis.org

1, 1, 2, 80, 21964800, 74836825861835980800000, 2606654998899867556195703676289609067340669424836280320000000000

Offset: 0

Eric W. Weisstein

nonn

A sequence {a_i}{i=1..N} forms a (binary) heap if it satisfies a_i<a{2i} and a_i

a(n) is also the number of knockout tournament seedings that satisfy the increasing competitive intensity property. - Alexander Karpov, Aug 18 2015

a(n) is the number of coalescence sequences, or labeled histories, for a binary, leaf-labeled, rooted tree topology with 2^n leaves (Rosenberg 2006, Theorem 3.3 for a completely symmetric tree with 2^n leaves, dividing by Theorem 3.2 for 2^n leaves). - Noah A Rosenberg, Feb 12 2019

a(n+1) is also the number of random walk labelings of the perfect binary tree of height n, that begin at the root. - Sela Fried, Aug 02 2023

If a bracket of 2^n teams is specified for a single-elimination tournament, a(n) is the number of sequences in which the games of the tournament can be played in a single arena. - Noah A Rosenberg, Jan 01 2025

			There is 1 heap on 2^0-1=0 elements, 1 heap on 2^1-1=1 element and there are 2 heaps on 2^2-1=3 elements and so on.

Alois P. Heinz, Table of n, a(n) for n = 0..9
Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Sela Fried and Toufik Mansour, Random walk labelings of perfect trees and other graphs, arXiv:2308.00315 [math.CO], 2023.
Alexander Karpov, A theory of knockout tournament seedings, Heidelberg University, AWI Discussion Paper Series, No. 600.
Matthew C. King and Noah A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.
Egor Lappo and Noah A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
Noah A. Rosenberg, The Mean and Variance of the Numbers of r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees, Ann. Combinator. 10 (2006), 129-146.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000225, A056971, A195581.

Column k=2 of A273712.

a:= n-> (2^n-1)!/mul((2^k-1)^(2^(n-k)), k=1..n):
seq(a(i), i=0..6);  # Alois P. Heinz, Nov 22 2007

s[1] := 1; s[l_] := s[l] := Binomial[2^l-2, 2^(l-1)-1]s[l-1]^2; Table[s[l], {l, 10}]

from math import prod, factorial
def A056972(n): return factorial((1<Chai Wah Wu, May 06 2024

a(n) = A056971(A000225(n)).
a(n) = A195581(2^n-1,n).
a(n) = binomial(2^n-2, 2^(n-1)-1)*a(n-1)^2. - Robert Israel, Aug 18 2015, from the Mathematica program
a(n) = (2^n-1)!/Product_{k=1..n} (2^k-1)^(2^(n-k)). - Robert Israel, Aug 18 2015, from the Maple program

A076616 Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height).

Original entry on oeis.org

0, 0, 0, 2, 16, 64, 208, 608, 1664, 4352, 11008, 27136, 65536, 155648, 364544, 843776, 1933312, 4390912, 9895936, 22151168, 49283072, 109051904, 240123904, 526385152, 1149239296, 2499805184, 5419040768, 11710496768, 25232932864, 54223962112, 116232552448

Offset: 0

Jeffrey Shallit, Oct 22 2002

			a(3) = 2 because only the permutations (2,1,3) and (2,3,1) result in a search tree of height 2 (notice we count empty external nodes in determining the height). The largest such trees are of height 3.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Lower diagonal of A195581 or of A244108.

Cf. A049611, A076615, A084851, A100312.

a:= n-> max(-(<<0|1|0>, <0|0|1>, <8|-12|6>>^n. <<1/2, 1, 1>>)[1$2], 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 20 2011

Join[{0, 0, 0}, LinearRecurrence[{6, -12, 8}, {2, 16, 64}, 40]] (* Jean-François Alcover, Jan 09 2025 *)

concat(vector(3), Vec(2*x^3*(1+2*x-4*x^2)/(1-2*x)^3 + O(x^50))) \\ Colin Barker, May 16 2016

G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - Alois P. Heinz, Sep 20 2011
From Colin Barker, May 16 2016: (Start)
a(n) = 2^(n-3)*(n^2-n-4) for n>2.
a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>5.
(End)
From Alois P. Heinz, May 31 2022: (Start)
a(n) = 2 * A100312(n-3) for n>=3.
a(n) = 16 * A049611(n-3) = 16 * A084851(n-4) for n>=4. (End)

More terms from Alois P. Heinz, Sep 20 2011

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

Showing 1-10 of 19 results. Next

cp's OEIS Frontend

A195582 Numerator of the average height of a binary search tree on n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A076615 Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

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

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A076616 Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

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.