login
A306343
Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.
15
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, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360
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
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.
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
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Sequence in context: A110910 A119532 A010583 * A238188 A360693 A051007
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Feb 08 2019
STATUS
approved