login
A372489
Number of defective (binary) heaps on 2n elements from the set {0,1} with exactly n defects.
2
1, 1, 3, 4, 8, 18, 41, 104, 253, 579, 1370, 3184, 7331, 16720, 38720, 91720, 218038, 518268, 1259464, 3141644, 7687556, 18460394, 45409204, 115174672, 283748621, 680088840, 1665189408, 4207220068, 10403856572, 25304979704, 62881939100, 161253396400, 396959041273
OFFSET
0,3
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 2n having exactly n indices i in [2n] such that v[i] > v[floor(i/2)].
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = A370484(2n,n).
EXAMPLE
a(0) = 1: the empty heap.
a(1) = 1: 01.
a(2) = 3: 0011, 0110, 0111.
a(3) = 4: 000111, 001110, 001111, 100111.
a(4) = 8: 00001111, 00011110, 00011111, 01000111, 01001111, 10001111, 10011110, 10011111.
a(5) = 18: 0000011111, 0000111110, 0000111111, 0100001111, 0100010111, 0100011011, 0100011101, 0100011110, 0100111110, 0100111111, 0110000111, 0110001111, 0110010111, 0110011111, 1000011111, 1000111110, 1000111111, 1100011111.
(The examples use max-heaps.)
MAPLE
b:= proc(n, t) option remember; `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)))
end:
a:= n-> coeff(b(2*n, 1), x, n):
seq(a(n), n=0..32);
CROSSREFS
Cf. A091980 (no defects), A370484.
Sequence in context: A192474 A183494 A107429 * A061273 A254715 A107328
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 06 2024
STATUS
approved