|
%I #23 Jun 08 2024 01:46:35
%S 1,1,0,1,1,0,1,2,1,0,1,3,3,1,0,1,4,6,5,1,0,1,5,10,14,7,1,0,1,6,15,30,
%T 25,11,1,0,1,7,21,55,65,53,16,1,0,1,8,28,91,140,173,100,26,1,0,1,9,36,
%U 140,266,448,400,222,36,1,0,1,10,45,204,462,994,1225,1122,386,56,1,0
%N Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C These heaps may contain repeated elements.
%H Alois P. Heinz, <a href="/A373449/b373449.txt">Antidiagonals n = 0..200, flattened</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A(n,k) = Sum_{j=0..k} binomial(k,j) * A373451(n,k-j).
%e A(3,1) = 1: 111.
%e A(3,2) = 5: 111, 211, 212, 221, 222.
%e A(3,3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
%e (The examples use max-heaps.)
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
%e 0, 1, 3, 6, 10, 15, 21, 28, 36, ...
%e 0, 1, 5, 14, 30, 55, 91, 140, 204, ...
%e 0, 1, 7, 25, 65, 140, 266, 462, 750, ...
%e 0, 1, 11, 53, 173, 448, 994, 1974, 3606, ...
%e 0, 1, 16, 100, 400, 1225, 3136, 7056, 14400, ...
%e 0, 1, 26, 222, 1122, 4147, 12428, 32028, 73644, ...
%e 0, 1, 36, 386, 2336, 10036, 34242, 98922, 251922, ...
%p A:= proc(n, k) option remember; `if`(n=0, 1,
%p (g-> (f-> add(A(f, j)*A(n-1-f, j), j=1..k)
%p )(min(g-1, n-g/2)))(2^ilog2(n)))
%p end:
%p seq(seq(A(n, d-n), n=0..d), d=0..12);
%t A[n_, k_] := A[n, k] = If[n == 0, 1,
%t Function[g, Function[f, Sum[A[f, j]*A[n-1-f, j], {j, 1, k}]][
%t Min[g-1, n-g/2]]][2^(Length[IntegerDigits[n, 2]]-1)]];
%t Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Jun 08 2024, after _Alois P. Heinz_ *)
%Y Columns k=0-2 give: A000007, A000012, A091980(n+1).
%Y Rows n=0-6 give: A000012, A001477, A000217, A000330, A001296, A207361, A001249(k-1).
%Y Main diagonal gives A373450.
%Y Cf. A373451.
%K nonn,tabl
%O 0,8
%A _Alois P. Heinz_, Jun 05 2024
|
