|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
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];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
