|
%I #52 Oct 04 2019 11:41:52
%S 1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,3,3,2,1,1,1,3,4,4,2,1,1,1,4,6,6,5,2,
%T 1,1,1,4,7,8,7,5,2,1,1,1,5,10,12,11,8,5,2,1,1,1,5,11,16,17,13,9,5,2,1,
%U 1,1,6,15,23,27,24,16,10,5,2,1,1,1,6,16,27,34,34,27,18,11,5,2,1,1
%N Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.
%C The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).
%H Alois P. Heinz, <a href="/A309049/b309049.txt">Rows 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 Sum_{k=0..n} k * T(n,k) = A309051(n).
%F Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
%F Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
%F Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
%F Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
%F T(m,m-n) = A000108(n) for m >= 2^n-1 = A000225(n).
%F T(2^n-1,k) = A202019(n+1,k+1).
%e T(6,0) = 1: 111111.
%e T(6,1) = 3: 111011, 111101, 111110.
%e T(6,2) = 4: 110110, 111001, 111010, 111100.
%e T(6,3) = 4: 101001, 110010, 110100, 111000.
%e T(6,4) = 2: 101000, 110000.
%e T(6,5) = 1: 100000.
%e T(6,6) = 1: 000000.
%e T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
%e Triangle T(n,k) begins:
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 1, 2, 1, 1;
%e 1, 2, 2, 1, 1;
%e 1, 3, 3, 2, 1, 1;
%e 1, 3, 4, 4, 2, 1, 1;
%e 1, 4, 6, 6, 5, 2, 1, 1;
%e 1, 4, 7, 8, 7, 5, 2, 1, 1;
%e 1, 5, 10, 12, 11, 8, 5, 2, 1, 1;
%e 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1;
%e 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1;
%e 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
%e ...
%p b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
%p x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
%p seq(T(n), n=0..14);
%t b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
%t T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
%t T /@ Range[0, 14] // Flatten (* _Jean-François Alcover_, Oct 04 2019, after _Alois P. Heinz_ *)
%Y Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
%Y Row sums give A091980(n+1).
%Y T(2n,n) gives A309050.
%Y Rows reversed converge to A000108.
%Y Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.
%K nonn,tabl
%O 0,8
%A _Alois P. Heinz_, Jul 09 2019
|
