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
Alois P. Heinz, Table of n, a(n) for n = 0..2528
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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 06 2024
STATUS
approved