cp's OEIS Frontend

A370484 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} with k defects; triangle T(n,k), n>=0, read by rows.

%I A370484 #117 Feb 16 2025 08:34:06
%S A370484 1,2,3,1,5,2,1,7,6,3,11,11,9,1,16,20,24,4,26,32,52,16,2,36,60,100,52,
%T A370484 8,56,100,192,120,40,4,81,162,351,300,111,18,1,131,255,631,627,313,77,
%U A370484 13,1,183,427,1067,1311,821,241,41,5,287,692,1856,2484,1894,764,184,28,3
%N A370484 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} with k defects; triangle T(n,k), n>=0, read by rows.
%C A370484 A defect in a defective heap is a parent-child pair not having the correct order.
%C A370484 T(n,k) is the number of bit vectors v of length n having exactly k indices i in [n] such that v[i] > v[floor(i/2)].
%C A370484 T(n,0) counts perfect (binary) heaps on n elements from the set {0,1}.
%C A370484 T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.
%H A370484 Alois P. Heinz, <a href="/A370484/b370484.txt">Rows n = 0..250, flattened</a>
%H A370484 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A370484 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A370484 Sum_{k>=0} k * T(n,k) = A139756(n) = ceiling((n-1)*2^n/4).
%F A370484 Sum_{k>=0} (k+1) * T(n,k) = A045623(n) = ceiling((n+3)*2^n/4).
%e A370484 T(4,0) = 7: 0000, 1000, 1010, 1100, 1101, 1110, 1111.
%e A370484 T(4,1) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
%e A370484 T(4,2) = 3: 0011, 0110, 0111.
%e A370484 (The examples use max-heaps.)
%e A370484 Triangle T(n,k) begins:
%e A370484     1;
%e A370484     2;
%e A370484     3,   1;
%e A370484     5,   2,    1;
%e A370484     7,   6,    3;
%e A370484    11,  11,    9,    1;
%e A370484    16,  20,   24,    4;
%e A370484    26,  32,   52,   16,   2;
%e A370484    36,  60,  100,   52,   8;
%e A370484    56, 100,  192,  120,  40,   4;
%e A370484    81, 162,  351,  300, 111,  18,  1;
%e A370484   131, 255,  631,  627, 313,  77, 13, 1;
%e A370484   183, 427, 1067, 1311, 821, 241, 41, 5;
%e A370484   ...
%p A370484 b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
%p A370484       expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
%p A370484       min(g-1, n-g/2)))(2^ilog2(n)))
%p A370484     end:
%p A370484 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
%p A370484 seq(T(n), n=0..15);
%t A370484 b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
%t A370484    Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
%t A370484    Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
%t A370484 T[n_] := CoefficientList[b[n, 1], x];
%t A370484 Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, May 09 2024, after _Alois P. Heinz_ *)
%Y A370484 Columns k=0-1 give: A091980(n+1), A372628.
%Y A370484 Row sums give A000079.
%Y A370484 T(2n,n) gives A372489.
%Y A370484 Cf. A045623, A056971, A139756, A306343, A372640.
%K A370484 nonn,tabf
%O A370484 0,2
%A A370484 _Alois P. Heinz_, May 06 2024