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

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.

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Example

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

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

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.

Sequence in context: A214055 A066909 A095195 * A229961 A189074 A370484

Adjacent sequences: A372637 A372638 A372639 * A372641 A372642 A372643

Keyword

nonn,tabf

Author

Alois P. Heinz, May 08 2024

Status

approved