|
%I #52 Jan 21 2024 13:56:53
%S 1,1,1,1,2,2,2,3,6,6,6,3,8,16,24,24,24,16,8,20,60,100,120,120,120,100,
%T 60,20,80,240,480,640,720,720,720,640,480,240,80,210,840,1890,3150,
%U 4200,4830,5040,5040,4830,4200,3150,1890,840,210
%N Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.
%C T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).
%C T(n,0) counts perfect (binary) heaps on n elements (A056971).
%H Alois P. Heinz, <a href="/A306393/b306393.txt">Rows n = 0..100, flattened</a>
%H Marko Riedel, math.stackexchange.com, <a href="https://math.stackexchange.com/questions/4848403/">Average number of inversions in a random binary heap on 2^n-1 elements</a>.
%H Marko Riedel, <a href="/A306393/a306393.pdf">Average number of inversions in a random binary heap on 2^n-1 elements (PDF)</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>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>.
%F T(n,k) = T(n,A061168(n)-k) for n > 0.
%F Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).
%e T(4,0) = 3: 4231, 4312, 4321.
%e T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
%e T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
%e T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
%e T(4,4) = 3: 1234, 1243, 1324.
%e T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
%e (The examples use max-heaps.)
%e Triangle T(n,k) begins:
%e 1;
%e 1;
%e 1, 1;
%e 2, 2, 2;
%e 3, 6, 6, 6, 3;
%e 8, 16, 24, 24, 24, 16, 8;
%e 20, 60, 100, 120, 120, 120, 100, 60, 20;
%e 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
%e ...
%p b:= proc(u, o) option remember; local n, g, l; n:= u+o;
%p if n=0 then 1
%p else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
%p add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
%p b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
%p add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
%p b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
%p fi
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p seq(T(n), n=0..10);
%t b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
%t If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
%t Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
%t b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
%t Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
%t b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
%t T[n_] := CoefficientList[b[n, 0], x];
%t T /@ Range[0, 10] // Flatten (* _Jean-François Alcover_, Feb 15 2021, after _Alois P. Heinz_ *)
%Y Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
%Y Row sums give A000142.
%Y Central terms (also maxima) of rows give A324075.
%Y Cf. A000523, A008302, A061168, A120385, A306343, A324074.
%Y Average number of inversions of a full binary heap on 2^n-1 elements is A000337.
%K nonn,tabf
%O 0,5
%A _Alois P. Heinz_, Feb 12 2019
|
