|
%I #48 Feb 17 2021 15:19:24
%S 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,
%T 1760,1200,360,80,210,1526,5922,12502,12502,5922,1526,210,896,7616,
%U 34160,82880,111776,82880,34160,7616,896,3360,32460,185460,576060,1017060,1017060,576060,185460,32460,3360
%N 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.
%C A defect in a defective heap is a parent-child pair not having the correct order.
%C 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)).
%C T(n,0) counts perfect (binary) heaps on n elements (A056971).
%H Alois P. Heinz, <a href="/A306343/b306343.txt">Rows n = 0..190, flattened</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F T(n,k) = T(n,n-1-k) for n > 0.
%F Sum_{k>=0} k * T(n,k) = A001286(n).
%F Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
%F Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
%F Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
%F Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.
%e T(4,0) = 3: 4231, 4312, 4321.
%e T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
%e T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
%e T(4,3) = 3: 1234, 1243, 1324.
%e (The examples use max-heaps.)
%e Triangle T(n,k) begins:
%e 1;
%e 1;
%e 1, 1;
%e 2, 2, 2;
%e 3, 9, 9, 3;
%e 8, 28, 48, 28, 8;
%e 20, 90, 250, 250, 90, 20;
%e 80, 360, 1200, 1760, 1200, 360, 80;
%e 210, 1526, 5922, 12502, 12502, 5922, 1526, 210;
%e 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
%e ...
%p b:= proc(u, o) option remember; local n, g, l; n:= u+o;
%p if n=0 then 1
%p else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
%p add(add(binomial(j-1, i)*binomial(n-j, l-i)*
%p b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
%p add(add(binomial(j-1, i)*binomial(n-j, l-i)*
%p b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
%p fi
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p seq(T(n), n=0..10);
%t b[u_, o_] := b[u, o] = Module[{n = u + o, g, l},
%t If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
%t Sum[Sum[ Binomial[j-1, i]* Binomial[n-j, l-i]*b[i, l-i]*
%t b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}]+
%t Sum[Sum[Binomial[j - 1, i]* Binomial[n-j, l-i]*b[l-i, i]*
%t b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
%t T[n_] := CoefficientList[b[n, 0], x];
%t T /@ Range[0, 10] // Flatten (* _Jean-François Alcover_, Feb 17 2021, after _Alois P. Heinz_ *)
%Y Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
%Y Row sums give A000142.
%Y T(n,floor(n/2)) gives A306356.
%Y Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.
%K nonn,tabf
%O 0,5
%A _Alois P. Heinz_, Feb 08 2019
|
