cp's OEIS Frontend

A373897 Number of (binary) heaps of length n-k whose element set equals [k], where k is chosen so as to maximize this number.

%I A373897 #21 Feb 16 2025 08:34:06
%S A373897 1,0,1,1,1,3,5,9,23,55,147,386,1004,3128,8113,27456,111574,321433,
%T A373897 1150885,4888981,17841912,80566518,332583340,1188065665,5473922425,
%U A373897 21725492503,99894124075,548452369329,2185136109838,11339193480666,59140581278157,288137011157366
%N A373897 Number of (binary) heaps of length n-k whose element set equals [k], where k is chosen so as to maximize this number.
%C A373897 These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
%H A373897 Alois P. Heinz, <a href="/A373897/b373897.txt">Table of n, a(n) for n = 0..711</a>
%H A373897 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373897 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373897 a(n) = max({ A373451(n-j,j) : 0 <= j <= floor(n/2) }).
%e A373897 a(6) = 5: 2111, 2121, 2211, 2212, 2221 (with k=2).
%e A373897 a(7) = 9: 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221 (with k=2).
%e A373897 a(8) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321 (with k=3).
%e A373897 (The examples use max-heaps.)
%p A373897 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373897      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373897              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373897     end:
%p A373897 T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
%p A373897 a:= n-> max(seq(T(n-j, j), j=0..n/2)):
%p A373897 seq(a(n), n=0..31);
%Y A373897 Antidiagonal maxima of A373451.
%Y A373897 Cf. A373632.
%K A373897 nonn
%O A373897 0,6
%A A373897 _Alois P. Heinz_, Jun 21 2024