A372640 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n>=0, read by rows.

1, 2, 3, 1, 5, 2, 1, 7, 4, 3, 2, 11, 6, 7, 5, 2, 1, 16, 13, 12, 8, 10, 3, 2, 26, 22, 23, 14, 21, 10, 9, 2, 1, 36, 36, 39, 33, 33, 28, 26, 13, 9, 2, 1, 56, 54, 67, 61, 60, 59, 56, 37, 34, 11, 13, 2, 2, 81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2

Offset: 0

Author

Alois P. Heinz, May 08 2024

Keywords

• nonn
• tabf

Comments

T(n,k) is the number of bit vectors v of length n having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that v[i] > v[floor(i/2^j)].

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) = 4: 0010, 0100, 1001, 1011.
T(4,2) = 3: 0001, 0101, 0110.
T(4,3) = 2: 0011, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   2;
   3,  1;
   5,  2,   1;
   7,  4,   3,  2;
  11,  6,   7,  5,   2,   1;
  16, 13,  12,  8,  10,   3,   2;
  26, 22,  23, 14,  21,  10,   9,  2,  1;
  36, 36,  39, 33,  33,  28,  26, 13,  9,  2,  1;
  56, 54,  67, 61,  60,  59,  56, 37, 34, 11, 13,  2,  2;
  81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2;
  ...
		

Links

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

Crossrefs

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

Row sums give A000079.

Main diagonal gives A372641.

T(2,n) gives A372642.

Cf. A306393, A370484.

Programs

Maple

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

Mathematica

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