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,2

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.

Links

Alois P. Heinz, Rows n = 0..250, flattened

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

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

Example

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;
  ...

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 *)

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.

Sequence in context: A372640 A229961 A189074 * A255973 A169615 A076791

Adjacent sequences: A370481 A370482 A370483 * A370485 A370486 A370487

Keyword

nonn,tabf

Author

Alois P. Heinz, May 06 2024

Status

approved