A372642 Number of defective (binary) heaps on 2n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

1, 1, 3, 8, 33, 112, 370, 1186, 4338, 14999, 52175, 179159, 649132, 2415766, 8994203, 33305573, 120968991, 431067336, 1538631892, 5509192918, 19859364136, 72330631743, 265219210010, 977508697125, 3619996788047, 13376125657317, 49294003078858, 181671504803323

Offset: 0

Author

Alois P. Heinz, May 08 2024

Keywords

• nonn

Examples

			a(0) = 1: the empty heap.
a(1) = 1: 01.
a(2) = 3: 0001, 0101, 0110.
a(3) = 8: 001010, 001100, 010001, 010110, 011001, 011010, 011100, 100111.
(The examples use max-heaps.)
		

Links

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

Crossrefs

Cf. A372640.

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:
a:= n-> coeff(b(2*n, 0), x, n):
seq(a(n), n=0..27);

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

Formula

a(n) = A372640(2n,n).