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.

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, 8, 56, 100, 192, 120, 40, 4, 81, 162, 351, 300, 111, 18, 1, 131, 255, 631, 627, 313, 77, 13, 1, 183, 427, 1067, 1311, 821, 241, 41, 5, 287, 692, 1856, 2484, 1894, 764, 184, 28, 3

Offset: 0

Author

Alois P. Heinz, May 06 2024

Keywords

• nonn
• tabf

Comments

A defect in a defective heap is a parent-child pair not having the correct order.

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)].

T(n,0) counts perfect (binary) heaps on n elements from the set {0,1}.

T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.

Examples

			T(4,0) = 7: 0000, 1000, 1010, 1100, 1101, 1110, 1111.
T(4,1) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
T(4,2) = 3: 0011, 0110, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    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,   8;
   56, 100,  192,  120,  40,   4;
   81, 162,  351,  300, 111,  18,  1;
  131, 255,  631,  627, 313,  77, 13, 1;
  183, 427, 1067, 1311, 821, 241, 41, 5;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..250, flattened
• Eric Weisstein's World of Mathematics, Heap
• Wikipedia, Binary heap

Crossrefs

Columns k=0-1 give: A091980(n+1), A372628.

Row sums give A000079.

T(2n,n) gives A372489.

Cf. A045623, A056971, A139756, A306343, A372640.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
      expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
      min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);

Mathematica

b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
   Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
   Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

Formula

Sum_{k>=0} k * T(n,k) = A139756(n) = ceiling((n-1)*2^n/4).

Sum_{k>=0} (k+1) * T(n,k) = A045623(n) = ceiling((n+3)*2^n/4).