cp's OEIS Frontend

A372642 Number of defective (binary) heaps on 2n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

%I A372642 #17 Feb 16 2025 08:34:06
%S A372642 1,1,3,8,33,112,370,1186,4338,14999,52175,179159,649132,2415766,
%T A372642 8994203,33305573,120968991,431067336,1538631892,5509192918,
%U A372642 19859364136,72330631743,265219210010,977508697125,3619996788047,13376125657317,49294003078858,181671504803323
%N A372642 Number of defective (binary) heaps on 2n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.
%H A372642 Alois P. Heinz, <a href="/A372642/b372642.txt">Table of n, a(n) for n = 0..1000</a>
%H A372642 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A372642 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A372642 a(n) = A372640(2n,n).
%e A372642 a(0) = 1: the empty heap.
%e A372642 a(1) = 1: 01.
%e A372642 a(2) = 3: 0001, 0101, 0110.
%e A372642 a(3) = 8: 001010, 001100, 010001, 010110, 011001, 011010, 011100, 100111.
%e A372642 (The examples use max-heaps.)
%p A372642 b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
%p A372642       expand(b(f, t)*b(n-1-f, t)*x^t+b(f, t+1)*b(n-1-f, t+1)
%p A372642           ))(min(g-1, n-g/2)))(2^ilog2(n)))
%p A372642     end:
%p A372642 a:= n-> coeff(b(2*n, 0), x, n):
%p A372642 seq(a(n), n=0..27);
%t A372642 b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
%t A372642    Expand[b[f, t]*b[n - 1 - f, t]*x^t + b[f, t + 1]*b[n - 1 - f, t + 1]]][
%t A372642    Min[g - 1, n - g/2]]][2^(Length@IntegerDigits[n, 2] - 1)]];
%t A372642 a[n_] := Coefficient[b[2 n, 0], x, n];
%t A372642 Table[a[n], {n, 0, 27}] (* _Jean-François Alcover_, May 09 2024, after _Alois P. Heinz_ *)
%Y A372642 Cf. A372640.
%K A372642 nonn
%O A372642 0,3
%A A372642 _Alois P. Heinz_, May 08 2024