A372489 Number of defective (binary) heaps on 2n elements from the set {0,1} with exactly n defects.

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

Author

Alois P. Heinz, May 06 2024

Keywords

• nonn

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

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2528
• Eric Weisstein's World of Mathematics, Heap
• Wikipedia, Binary heap

Crossrefs

Cf. A091980 (no defects), A370484.

Programs

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

Formula

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