login
A372628
Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.
4
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
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.
Sequence in context: A058760 A239071 A085573 * A171516 A081691 A085571
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 07 2024
STATUS
approved