cp's OEIS Frontend

A372628 Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.

%I A372628 #22 Feb 16 2025 08:34:06
%S A372628 0,0,1,2,6,11,20,32,60,100,162,255,427,692,1093,1738,2800,4507,6951,
%T A372628 11032,17224,27553,42276,67639,103989,165856,251312,401236,608112,
%U A372628 968380,1465934,2354752,3525880,5585826,8370796,13394396,19937564,31632664,47478092
%N A372628 Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.
%C A372628 A defect in a defective heap is a parent-child pair not having the correct order.
%C A372628 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)].
%H A372628 Alois P. Heinz, <a href="/A372628/b372628.txt">Table of n, a(n) for n = 0..5634</a>
%H A372628 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A372628 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%e A372628 a(2) = 1: 01.
%e A372628 a(3) = 2: 001, 010.
%e A372628 a(4) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
%e A372628 a(5) = 11: 00001, 00010, 00100, 01000, 01001, 01010, 01011, 10001, 10010, 10101, 10110.
%e A372628 (The examples use max-heaps.)
%p A372628 b:= proc(n, t) option remember; convert(series(`if`(n=0, 1, (g->
%p A372628       (f-> expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
%p A372628            min(g-1, n-g/2)))(2^ilog2(n))), x, 2), polynom)
%p A372628     end:
%p A372628 a:= n-> coeff(b(n, 1), x, 1):
%p A372628 seq(a(n), n=0..38);
%t A372628 b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function[f,
%t A372628    Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
%t A372628    Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
%t A372628 a[n_] := Coefficient[b[n, 1], x, 1];
%t A372628 Table[a[n], {n, 0, 38}] (* _Jean-François Alcover_, May 11 2024, after _Alois P. Heinz_ *)
%Y A372628 Column k=1 of A370484.
%Y A372628 Cf. A323957, A372643.
%K A372628 nonn
%O A372628 0,4
%A A372628 _Alois P. Heinz_, May 07 2024