cp's OEIS Frontend

A373500 Number of (binary) heaps of length 2n whose element set equals [n].

%I A373500 #14 Feb 16 2025 08:34:06
%S A373500 1,1,5,55,1004,27456,1077657,59699950,3944644671,319905929418,
%T A373500 32390662046661,4181039787994506,602128996908467070,
%U A373500 102537208988632300118,20497804459093071390108,4978144718604701947160364,1232227300264551117529973052,335016989869301170468736520008
%N A373500 Number of (binary) heaps of length 2n whose element set equals [n].
%C A373500 These heaps contain repeated elements and their element sets are gap-free and contain 1 (if nonempty).
%H A373500 Alois P. Heinz, <a href="/A373500/b373500.txt">Table of n, a(n) for n = 0..254</a>
%H A373500 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373500 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373500 a(n) = A373451(2n,n).
%e A373500 a(0) = 1: the empty heap.
%e A373500 a(1) = 1: 11.
%e A373500 a(2) = 5: 2111, 2121, 2211, 2212, 2221.
%e A373500 a(3) = 55: 312111, 312112, 313112, 321111, ..., 333221, 333231, 333312, 333321.
%e A373500 a(4) = 1004: 41311121, 41311211, 41311221, 41311231, ... 44444213, 44444231, 44444312, 44444321.
%e A373500 (The examples use max-heaps.)
%p A373500 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373500      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373500              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373500     end:
%p A373500 a:= n-> add(binomial(n, j)*(-1)^j*b(2*n, n-j), j=0..n):
%p A373500 seq(a(n), n=0..17);
%Y A373500 Cf. A056971, A373451.
%K A373500 nonn
%O A373500 0,3
%A A373500 _Alois P. Heinz_, Jun 06 2024