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.

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

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

A317012 Total number of elements in all permutations of [n], [n+1], ... that result in a binary search tree of height n.

Original entry on oeis.org

0, 1, 10, 1316, 840124672, 6110726696100443604557936, 439451426203104201222708341688051362423089952907263634936946272224
Offset: 0

Views

Author

Alois P. Heinz, Jul 18 2018

Keywords

Comments

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

Examples

			a(2) = 10 = 2 + 3 + 3 + 2:
.
         2           2           1
        / \         / \         / \
       1   o       1   3       o   2
      / \         ( ) ( )         / \
     o   o        o o o o        o   o
      (2,1)   (2,1,3) (2,3,1)   (1,2)
.

Links

Crossrefs

Cf. A195581, A227822, A244108, A335922.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`(n<2, `if`(k b(n, k)-b(n, k-1):
a:= k-> add(T(n, k)*n, n=k..2^k-1):
seq(a(n), n=0..6);
  • 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}]];
T[n_, k_] := b[n, k] - b[n, k-1];
a[k_] := Sum[T[n, k] n, {n, k, 2^k - 1}];
a /@ Range[0, 6] (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

Formula

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