|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
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];
|
|
CROSSREFS
|
Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|