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.

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

Views

Author

Alois P. Heinz, Jun 29 2020

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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.

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):
seq(seq(T(n, k), k=g(n)..n), n=0..12);
  • Mathematica
    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 *)

Formula

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

Views

Author

Alois P. Heinz, Jun 29 2020

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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.

Programs

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

Formula

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

Views

Author

Alois P. Heinz, Jul 17 2018

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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

Programs

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

Formula

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

A335922 Total number of internal nodes in all binary search trees of height n.

Original entry on oeis.org

0, 1, 7, 97, 6031, 8760337, 8245932762607, 3508518207942911995940881, 311594265746788494170059418351454897488270152687
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(2) = 7 = 2 + 3 + 2:
.
         2        2        1
        / \      / \      / \
       1   o    1   3    o   2
      / \      ( ) ( )      / \
     o   o     o o o o     o   o
.

Links

Crossrefs

Cf. A317012, A335919, A335920, A335921.

Programs

  • Maple
    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:= k-> add(T(n, k)*n, n=k..2^k-1):
seq(a(n), n=0..10);
  • Mathematica
    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[k_] := Sum[T[n, k]*n, {n, k, 2^k - 1}];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Apr 26 2022, after Alois P. Heinz *)

Formula

a(n) = Sum_{k=n..2^n-1} k * A335919(k,n) = Sum_{k=n..2^n-1} k * A335920(k,n).
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.