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

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5634

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Example

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

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

Crossrefs

Column k=1 of A370484.

Cf. A323957, A372643.

Sequence in context: A058760 A239071 A085573 * A171516 A081691 A085571

Adjacent sequences: A372625 A372626 A372627 * A372629 A372630 A372631

Keyword

nonn

Author

Alois P. Heinz, May 07 2024

Status

approved