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

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

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

Example

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

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

Crossrefs

Cf. A372640.

Sequence in context: A258690 A091831 A284963 * A148916 A148917 A120892

Adjacent sequences: A372639 A372640 A372641 * A372643 A372644 A372645

Keyword

nonn

Author

Alois P. Heinz, May 08 2024

Status

approved