OFFSET
0,5
COMMENTS
A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).
LINKS
Alois P. Heinz, Rows n = 0..190, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
EXAMPLE
T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
1;
1;
1, 1;
2, 2, 2;
3, 9, 9, 3;
8, 28, 48, 28, 8;
20, 90, 250, 250, 90, 20;
80, 360, 1200, 1760, 1200, 360, 80;
210, 1526, 5922, 12502, 12502, 5922, 1526, 210;
896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
...
MAPLE
b:= proc(u, o) option remember; local n, g, l; n:= u+o;
if n=0 then 1
else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
add(add(binomial(j-1, i)*binomial(n-j, l-i)*
b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
add(add(binomial(j-1, i)*binomial(n-j, l-i)*
b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
fi
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);
MATHEMATICA
b[u_, o_] := b[u, o] = Module[{n = u + o, g, l},
If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
Sum[Sum[ Binomial[j-1, i]* Binomial[n-j, l-i]*b[i, l-i]*
b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}]+
Sum[Sum[Binomial[j - 1, i]* Binomial[n-j, l-i]*b[l-i, i]*
b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Feb 08 2019
STATUS
approved