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

1, 0, 0, 0, 0, 1, 2, 2, 9, 11, 36, 71, 151, 306, 591, 1228, 2469, 4966, 10025, 19591, 38946, 75977, 148585, 291027, 579981, 1152385, 2280696, 4470814, 8817933, 17244969, 33819425, 65976444, 129933731, 254791662, 499516984, 977417823, 1914394157, 3745482924

Offset: 0

Author

Alois P. Heinz, May 08 2024

Keywords

• nonn

Examples

			a(5) = 1: 00111.
a(6) = 2: 000111, 001111.
a(7) = 2: 0011111, 0101111.
a(8) = 9: 00010111, 00011011, 00011101, 00011110, 00101111, 00111011, 00111101, 01001111, 01011111.
a(9) = 11: 000011101, 000011110, 001001111, 001010011, 001101111, 001110011, 001111101, 001111110, 010001111, 010111111, 011011111.
(The examples use max-heaps.)
		

Links

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

Crossrefs

Main diagonal of 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(n, 0),x,n):
seq(a(n), n=0..37);

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

Formula

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