cp's OEIS Frontend

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

%I A376963 #10 Feb 16 2025 08:34:07
%S A376963 3,23,92,386,1004,3128,8039,24725,56825,159665,383447,1113059,2366723,
%T A376963 6191435,14145653,39253721,84455981,223305485,513899477,1435302869,
%U A376963 2999680197,7717870961,17422727232,47809866678,102098766668,268024219452,613622726480,1705588304448
%N A376963 Number of (binary) heaps of length n whose element set equals {1,2,3,4}.
%H A376963 Alois P. Heinz, <a href="/A376963/b376963.txt">Table of n, a(n) for n = 4..2614</a>
%H A376963 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A376963 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%e A376963 a(4) = 3: 4231, 4312, 4321.
%e A376963 a(5) = 23: 42311, 42312, 42321, 43112, 43121, 43122, 43123, 43132, 43211, 43212, 43213, 43221, 43231, 43312, 43321, 43412, 43421, 44123, 44132, 44213, 44231, 44312, 44321.
%e A376963 (The examples use max-heaps.)
%p A376963 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A376963      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A376963              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A376963     end:
%p A376963 a:= n-> (k-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k))(4):
%p A376963 seq(a(n), n=4..35);
%Y A376963 Column k=4 of A373451.
%K A376963 nonn
%O A376963 4,1
%A A376963 _Alois P. Heinz_, Oct 10 2024