A376962 - OEIS

%I #12 Feb 16 2025 08:34:07

%S 2,7,23,55,147,281,633,1241,2849,5187,11195,21369,47933,83821,174245,

%T 324571,712247,1263211,2660843,4999291,11056139,19236203,39793055,

%U 73882568,161646306,286178632,601791336,1129403320,2495184864,4326802772,8921711316,16528692452

%N Number of (binary) heaps of length n whose element set equals {1,2,3}.

%H Alois P. Heinz, <a href="/A376962/b376962.txt">Table of n, a(n) for n = 3..3404</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>

%e a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.

%e a(5) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321.

%e (The examples use max-heaps.)

%p b:= proc(n, k) option remember; `if`(n=0, 1,

%p      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)

%p              )(min(g-1, n-g/2)))(2^ilog2(n)))

%p     end:

%p a:= n-> (k-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k))(3):

%p seq(a(n), n=3..35);

%Y Column k=3 of A373451.

%K nonn,changed

%O 3,1

%A _Alois P. Heinz_, Oct 10 2024