cp's OEIS Frontend

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

%I A376962 #12 Feb 16 2025 08:34:07
%S A376962 2,7,23,55,147,281,633,1241,2849,5187,11195,21369,47933,83821,174245,
%T A376962 324571,712247,1263211,2660843,4999291,11056139,19236203,39793055,
%U A376962 73882568,161646306,286178632,601791336,1129403320,2495184864,4326802772,8921711316,16528692452
%N A376962 Number of (binary) heaps of length n whose element set equals {1,2,3}.
%H A376962 Alois P. Heinz, <a href="/A376962/b376962.txt">Table of n, a(n) for n = 3..3404</a>
%H A376962 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A376962 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%e A376962 a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
%e A376962 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 A376962 (The examples use max-heaps.)
%p A376962 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A376962      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A376962              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A376962     end:
%p A376962 a:= n-> (k-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k))(3):
%p A376962 seq(a(n), n=3..35);
%Y A376962 Column k=3 of A373451.
%K A376962 nonn
%O A376962 3,1
%A A376962 _Alois P. Heinz_, Oct 10 2024