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
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;
...
-
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 *)
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
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;
-
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 *)
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
a(2) = 7 = 2 + 3 + 2:
.
2 2 1
/ \ / \ / \
1 o 1 3 o 2
/ \ ( ) ( ) / \
o o o o o o o o
.
-
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);
-
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 *)
A227822
Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.
Original entry on oeis.org
1, 1, 4, 220, 60092152, 203720181459953921762400, 7088043372247785801830314829178419617696182324188730917543544992
Offset: 0
a(2) = 4, because 4 permutations of {1,2}, {1,2,3}, ... result in a binary search tree of height 2:
(1,2): 1 (2,1): 2 (2,1,3), (2,3,1): 2
/ \ / \ / \
o 2 1 o 1 3
/ \ / \ / \ / \
o o o o o o o o
-
b:= proc(n, k) option remember; `if`(n<2, `if`(k add(b(k, n)-b(k, n-1), k=n..2^n-1):
seq(a(n), n=0..6);
-
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[b[k, n] - b[k, n - 1], {k, n, 2^n - 1}];
a /@ Range[0, 6] (* Jean-François Alcover, Apr 02 2021, after Alois P. Heinz *)
Showing 1-4 of 4 results.
Comments