cp's OEIS Frontend

A373450 Number of (binary) heaps of length n whose element set is a subset of [n].

%I A373450 #24 Feb 16 2025 08:34:06
%S A373450 1,1,3,14,65,448,3136,32028,251922,2891801,30684797,464651863,
%T A373450 5434037232,92246217970,1379368317328,29135744093948,414052904722966,
%U A373450 8546218817446727,152935671938144301,3857215760145872627,70913916905782150177,1881992311219764068420
%N A373450 Number of (binary) heaps of length n whose element set is a subset of [n].
%C A373450 These heaps may contain repeated elements.
%H A373450 Alois P. Heinz, <a href="/A373450/b373450.txt">Table of n, a(n) for n = 0..444</a>
%H A373450 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373450 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373450 a(n) = A373449(n,n).
%F A373450 a(n) = Sum_{k=0..n} binomial(n,k)*A373451(n,k).
%e A373450 a(0) = 1: the empty heap.
%e A373450 a(1) = 1: 1.
%e A373450 a(2) = 3: 11, 21, 22.
%e A373450 a(3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
%e A373450 (The examples use max-heaps.)
%p A373450 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373450      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373450              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373450     end:
%p A373450 a:= n-> b(n$2):
%p A373450 seq(a(n), n=0..21);
%Y A373450 Main diagonal of A373449.
%Y A373450 Cf. A056971 (distinct elements), A373452 (gap-free element sets including 1).
%Y A373450 Cf. A007318, A373451.
%K A373450 nonn
%O A373450 0,3
%A A373450 _Alois P. Heinz_, Jun 05 2024