cp's OEIS Frontend

A373632 Number of (binary) heaps where n is the sum of their length and the size of the element set [k].

%I A373632 #20 Feb 16 2025 08:34:06
%S A373632 1,0,1,1,2,4,8,17,41,103,282,792,2239,6680,21143,70647,245357,871255,
%T A373632 3202552,12334046,49635128,205403510,856780528,3601169551,15507530896,
%U A373632 69267381313,320345619798,1518428936730,7345400773513,36469929240960,186875135258481
%N A373632 Number of (binary) heaps where n is the sum of their length and the size of the element set [k].
%C A373632 These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
%H A373632 Alois P. Heinz, <a href="/A373632/b373632.txt">Table of n, a(n) for n = 0..710</a>
%H A373632 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373632 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373632 a(n) = Sum_{j=0..floor(n/2)} A373451(n-j,j).
%e A373632 a(0) = 1: the empty heap.
%e A373632 a(2) = 1: 1.
%e A373632 a(3) = 1: 11.
%e A373632 a(4) = 2: 111, 21.
%e A373632 a(5) = 4: 1111, 211, 212, 221.
%e A373632 a(6) = 8: 11111, 2111, 2121, 2211, 2212, 2221, 312, 321.
%e A373632 a(7) = 17: 111111, 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221, 3121, 3211, 3212, 3221, 3231, 3312, 3321.
%e A373632 (The examples use max-heaps.)
%p A373632 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373632      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373632              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373632     end:
%p A373632 T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
%p A373632 a:= n-> add(T(n-j, j), j=0..n/2):
%p A373632 seq(a(n), n=0..30);
%Y A373632 Antidiagonal sums of A373451.
%K A373632 nonn
%O A373632 0,5
%A A373632 _Alois P. Heinz_, Jun 11 2024