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-3 of 3 results.

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

Views

Author

Jeffrey Shallit, Oct 22 2002

Keywords

Comments

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

Examples

			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

Links

Crossrefs

Leftmost nonzero elements in rows of A195581, A244108.
Cf. A076616, A328349.

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:
a:= n-> b(n, ilog2(n)+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 20 2011
  • Mathematica
    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 *)
  • Python
    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

Formula

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

Extensions

Extended beyond a(8) and efficient formula by Michal Forisek, Sep 19 2011
a(0)=1 prepended by Alois P. Heinz, Jul 18 2018

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).
Showing 1-3 of 3 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.