cp's OEIS Frontend

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%I A373451 #41 Feb 16 2025 08:34:06
%S A373451 1,0,1,0,1,1,0,1,3,2,0,1,5,7,3,0,1,9,23,23,8,0,1,14,55,92,70,20,0,1,
%T A373451 24,147,386,502,320,80,0,1,34,281,1004,1861,1880,985,210,0,1,54,633,
%U A373451 3128,8113,12008,10237,4690,896,0,1,79,1241,8039,27456,54900,66730,48650,19600,3360
%N A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C A373451 These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
%C A373451 T(n,k) is defined for n,k >= 0.  The triangle contains only the terms with k<=n.  T(n,k) = 0 for k>n.
%H A373451 Alois P. Heinz, <a href="/A373451/b373451.txt">Rows n = 0..150, flattened</a>
%H A373451 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A373451 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A373451 T(n,k) = Sum_{j=0..k} binomial(k,j) * (-1)^j * A373449(n,k-j).
%F A373451 Sum_{k=0..n} (-1)^k * T(n,n-k) = A019590(n+1).
%e A373451 T(4,1) = 1: 1111.
%e A373451 T(4,2) = 5: 2111, 2121, 2211, 2212, 2221.
%e A373451 T(4,3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
%e A373451 T(4,4) = 3: 4231, 4312, 4321.
%e A373451 (The examples use max-heaps.)
%e A373451 Triangle T(n,k) begins:
%e A373451   1;
%e A373451   0, 1;
%e A373451   0, 1,  1;
%e A373451   0, 1,  3,   2;
%e A373451   0, 1,  5,   7,    3;
%e A373451   0, 1,  9,  23,   23,    8;
%e A373451   0, 1, 14,  55,   92,   70,    20;
%e A373451   0, 1, 24, 147,  386,  502,   320,    80;
%e A373451   0, 1, 34, 281, 1004, 1861,  1880,   985,  210;
%e A373451   0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896;
%e A373451   ...
%p A373451 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A373451      (g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
%p A373451              )(min(g-1, n-g/2)))(2^ilog2(n)))
%p A373451     end:
%p A373451 T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
%p A373451 seq(seq(T(n, k), k=0..n), n=0..12);
%t A373451 b[n_, k_] := b[n, k] = If[n == 0, 1,
%t A373451    Function[g, Function[f, Sum[b[f, j]*b[n-1-f, j], {j, 1, k}]][
%t A373451       Min[g-1, n-g/2]]][2^(Length@IntegerDigits[n, 2]-1)]];
%t A373451 T[n_, k_] := Sum[Binomial[k, j]*(-1)^j*b[n, k-j], {j, 0, k}];
%t A373451 Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Sep 20 2024, after _Alois P. Heinz_ *)
%Y A373451 Columns k=0-4 give A000007, A057427, A091980(n+1)-2, A376962, A376963.
%Y A373451 Row sums give A373452.
%Y A373451 Row maxima give A373608.
%Y A373451 Main diagonal gives A056971.
%Y A373451 First lower diagonal gives A373496.
%Y A373451 T(2n,n) gives A373500.
%Y A373451 Antidiagonal sums give A373632.
%Y A373451 Antidiagonal maxima give A373897.
%Y A373451 Cf. A019590, A373449.
%K A373451 nonn,tabl
%O A373451 0,9
%A A373451 _Alois P. Heinz_, Jun 05 2024