A076616 -id:A076616 - 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).

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

A127276 Hankel transform of A127275.

Original entry on oeis.org

1, 1, -2, -16, -64, -208, -608, -1664, -4352, -11008, -27136, -65536, -155648, -364544, -843776, -1933312, -4390912, -9895936, -22151168, -49283072, -109051904, -240123904, -526385152, -1149239296, -2499805184, -5419040768

Offset: 0

Paul Barry, Jan 10 2007

sign

The inverse binomial transform of this sequence yields 1, 0, -3, -8,..., which is 1 followed by the negated terms of A005563. [Paul Curtz, Dec 07 2010]

The smallest odd prime divisor of a(n) is >= 13. - Vladimir Shevelev, Feb 03 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A076616, A176126, A236999.

[2^n-n*(n+1)*2^(n-2): n in [0..30]]; // Vincenzo Librandi, Aug 11 2011

A127276:=n->2^n - n*(n + 1)*2^(n - 2); seq(A127276(n), n=0..26); # Wesley Ivan Hurt, Dec 02 2013

Table[2^n - n*(n + 1)*2^(n - 2), {n, 0, 26}] (* Wesley Ivan Hurt, Dec 02 2013 *)

Conjecture: G.f.: -(4*x-1)*(x-1) / ( (2*x-1)^3 ) and a(n) = 2^n-n*(n+1)*2^(n-2). - R. J. Mathar, Dec 11 2010

a(n) = A178987(n) - A178987(n+1). - Klaus Brockhaus, Jan 08 2011

A350816 Number of minimum dominating sets in the 2 X n king graph.

Original entry on oeis.org

2, 4, 2, 16, 12, 4, 64, 32, 8, 208, 80, 16, 608, 192, 32, 1664, 448, 64, 4352, 1024, 128, 11008, 2304, 256, 27136, 5120, 512, 65536, 11264, 1024, 155648, 24576, 2048, 364544, 53248, 4096, 843776, 114688, 8192, 1933312, 245760, 16384, 4390912, 524288, 32768

Offset: 1

Andrew Howroyd, Jan 17 2022

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Index entries for linear recurrences with constant coefficients, signature (0,0,6,0,0,-12,0,0,8).

Row 2 of A350815.

Cf. A000079, A001787, A076616, A347558, A347633.

Vec(2*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3 + O(x^45))

a(n) = {my(t=n\3); 2^t*if(n%3==0, 1, if(n%3==1, t^2 + 5*t + 2, 2*t + 4))}

a(n) = 6*a(n-3) - 12*a(n-6) + 8*a(n-9) for n > 9.
G.f.: 2*x*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3.
a(3*n) = 2^n; a(3*n+1) = (n^2 + 5*n + 2)*2^n; a(3*n+2) = (n + 2)*2^(n+1).
a(3*n) = A000079(n); a(3*n+1) = A076616(n+3); a(3*n+2) = A001787(n+2).

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

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

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

A127276 Hankel transform of A127275.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A350816 Number of minimum dominating sets in the 2 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula