cp's OEIS Frontend

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.

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