A372628 Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.

0, 0, 1, 2, 6, 11, 20, 32, 60, 100, 162, 255, 427, 692, 1093, 1738, 2800, 4507, 6951, 11032, 17224, 27553, 42276, 67639, 103989, 165856, 251312, 401236, 608112, 968380, 1465934, 2354752, 3525880, 5585826, 8370796, 13394396, 19937564, 31632664, 47478092

Offset: 0

Author

Alois P. Heinz, May 07 2024

Keywords

• nonn

Comments

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

a(n) is the number of bit vectors v of length n having exactly one index i in [n] with v[i] > v[floor(i/2)].

Examples

			a(2) = 1: 01.
a(3) = 2: 001, 010.
a(4) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
a(5) = 11: 00001, 00010, 00100, 01000, 01001, 01010, 01011, 10001, 10010, 10101, 10110.
(The examples use max-heaps.)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5634
• Eric Weisstein's World of Mathematics, Heap
• Wikipedia, Binary heap

Crossrefs

Column k=1 of A370484.

Cf. A323957, A372643.

Programs

Maple

b:= proc(n, t) option remember; convert(series(`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))), x, 2), polynom)
    end:
a:= n-> coeff(b(n, 1), x, 1):
seq(a(n), n=0..38);

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)]];
a[n_] := Coefficient[b[n, 1], x, 1];
Table[a[n], {n, 0, 38}] (* Jean-François Alcover, May 11 2024, after Alois P. Heinz *)