login
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.
16

%I #54 May 08 2024 12:11:52

%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, A372640.

%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