login
A324074
Total number of distorted ancestor-successor pairs in all defective (binary) heaps on n elements.
2
0, 0, 1, 6, 48, 360, 2880, 25200, 262080, 2903040, 34473600, 439084800, 5987520000, 87178291200, 1351263513600, 22230464256000, 397533007872000, 7469435990016000, 147254595231744000, 3041127510220800000, 65688354220769280000, 1481637322979573760000
OFFSET
0,4
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = Sum_{k=0..A061168(n)} k * A306393(n,k).
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(x^(n-j)*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(x^(j-1)*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))
fi
end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=0..degree(p)))(b(n, 0)):
seq(a(n), n=0..25);
MATHEMATICA
b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o; If[n == 0, 1,
g = 2^(Length[IntegerDigits[n, 2]]-1); l = Min[g-1, n-g/2]; Expand[
Sum[x^(n - j)*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[x^(j - 1)*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}]]]];
a[n_] := With[{p=b[n, 0]}, CoefficientList[p, x].Range[0, Exponent[p, x]]];
a /@ Range[0, 25] (* Jean-François Alcover, Apr 23 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Feb 14 2019
STATUS
approved