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

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

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

Example

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

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

Crossrefs

Main diagonal of A372640.

Sequence in context: A193726 A143022 A154100 * A002880 A225465 A248665

Adjacent sequences: A372638 A372639 A372640 * A372642 A372643 A372644

Keyword

nonn

Author

Alois P. Heinz, May 08 2024

Status

approved