|
|
A306393
|
|
Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.
|
|
15
|
|
|
1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).
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,A061168(n)-k) for n > 0.
|
|
EXAMPLE
|
T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
1;
1;
1, 1;
2, 2, 2;
3, 6, 6, 6, 3;
8, 16, 24, 24, 24, 16, 8;
20, 60, 100, 120, 120, 120, 100, 60, 20;
80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
...
|
|
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:
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, g, l}, n = u + o;
If[n == 0, 1, g = 2^Floor@Log[2, n]; 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}]]]];
T[n_] := CoefficientList[b[n, 0], x];
|
|
CROSSREFS
|
Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Central terms (also maxima) of rows give A324075.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|