cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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.

Original entry on oeis.org

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

Views

Author

Alois P. Heinz, Sep 20 2011

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Programs

  • Maple
    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);
  • Mathematica
    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 *)

Formula

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

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

Original entry on oeis.org

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

Views

Author

Alois P. Heinz, Sep 20 2011

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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

Programs

  • Maple
    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);
  • Mathematica
    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 *)

Formula

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

Views

Author

Alois P. Heinz, Dec 21 2015

Keywords

Comments

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

Examples

			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;

Links

Crossrefs

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.

Programs

  • Maple
    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);
  • Mathematica
    b[n_, k_] := b[n, k] = If[n<2, If[kJean-François Alcover, Feb 19 2017, translated from Maple *)

Formula

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

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

Views

Author

Alois P. Heinz, Jun 29 2020

Keywords

Comments

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

Examples

			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
.

Links

Crossrefs

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

Programs

  • Maple
    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);
  • Mathematica
    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 *)

Formula

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 }.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.