cp's OEIS Frontend

A373496 Number of (binary) heaps with element set [n] and length n+1.

%I A373496 #19 Feb 16 2025 08:34:06
%S A373496 0,1,3,7,23,70,320,985,4690,19600,121920,549600,3775200,21964800,
%T A373496 186700800,983954400,7898290400,53301248000,523712716800,
%U A373496 3600440064000,37065077913600,315001589760000,3848127528960000,30288467049984000,357688760600371200,3481899302289408000
%N A373496 Number of (binary) heaps with element set [n] and length n+1.
%C A373496 These heaps contain exactly one repeated element.
%H A373496 Alois P. Heinz, <a href="/A373496/b373496.txt">Table of n, a(n) for n = 0..527</a>
%H A373496 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373496 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373496 a(n) = A373451(n+1,n).
%e A373496 a(1) = 1: 11.
%e A373496 a(2) = 3: 211, 212, 221.
%e A373496 a(3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
%e A373496 a(4) = 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 A373496 (The examples use max-heaps.)
%p A373496 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373496      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373496              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373496     end:
%p A373496 a:= n-> add(binomial(n, j)*(-1)^j*b(n+1, n-j), j=0..n):
%p A373496 seq(a(n), n=0..29);
%Y A373496 First lower diagonal of A373451.
%Y A373496 Cf. A056971 (without repeated elements).
%K A373496 nonn
%O A373496 0,3
%A A373496 _Alois P. Heinz_, Jun 06 2024