cp's OEIS Frontend

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

%I A372489 #26 Feb 16 2025 08:34:06
%S A372489 1,1,3,4,8,18,41,104,253,579,1370,3184,7331,16720,38720,91720,218038,
%T A372489 518268,1259464,3141644,7687556,18460394,45409204,115174672,283748621,
%U A372489 680088840,1665189408,4207220068,10403856572,25304979704,62881939100,161253396400,396959041273
%N A372489 Number of defective (binary) heaps on 2n elements from the set {0,1} with exactly n defects.
%C A372489 A defect in a defective heap is a parent-child pair not having the correct order.
%C A372489 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)].
%H A372489 Alois P. Heinz, <a href="/A372489/b372489.txt">Table of n, a(n) for n = 0..2528</a>
%H A372489 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A372489 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A372489 a(n) = A370484(2n,n).
%e A372489 a(0) = 1: the empty heap.
%e A372489 a(1) = 1: 01.
%e A372489 a(2) = 3: 0011, 0110, 0111.
%e A372489 a(3) = 4: 000111, 001110, 001111, 100111.
%e A372489 a(4) = 8: 00001111, 00011110, 00011111, 01000111, 01001111, 10001111, 10011110, 10011111.
%e A372489 a(5) = 18: 0000011111, 0000111110, 0000111111, 0100001111, 0100010111, 0100011011, 0100011101, 0100011110, 0100111110, 0100111111, 0110000111, 0110001111, 0110010111, 0110011111, 1000011111, 1000111110, 1000111111, 1100011111.
%e A372489 (The examples use max-heaps.)
%p A372489 b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
%p A372489       expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
%p A372489       min(g-1, n-g/2)))(2^ilog2(n)))
%p A372489     end:
%p A372489 a:= n-> coeff(b(2*n, 1), x, n):
%p A372489 seq(a(n), n=0..32);
%Y A372489 Cf. A091980 (no defects), A370484.
%K A372489 nonn
%O A372489 0,3
%A A372489 _Alois P. Heinz_, May 06 2024