OFFSET
0,2
COMMENTS
A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of bit vectors v of length n having exactly k indices i in [n] such that v[i] > v[floor(i/2)].
T(n,0) counts perfect (binary) heaps on n elements from the set {0,1}.
T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.
LINKS
Alois P. Heinz, Rows n = 0..250, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
EXAMPLE
T(4,0) = 7: 0000, 1000, 1010, 1100, 1101, 1110, 1111.
T(4,1) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
T(4,2) = 3: 0011, 0110, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
1;
2;
3, 1;
5, 2, 1;
7, 6, 3;
11, 11, 9, 1;
16, 20, 24, 4;
26, 32, 52, 16, 2;
36, 60, 100, 52, 8;
56, 100, 192, 120, 40, 4;
81, 162, 351, 300, 111, 18, 1;
131, 255, 631, 627, 313, 77, 13, 1;
183, 427, 1067, 1311, 821, 241, 41, 5;
...
MAPLE
b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
min(g-1, n-g/2)))(2^ilog2(n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);
MATHEMATICA
b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, May 06 2024
STATUS
approved