This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A306393 #55 Feb 16 2025 08:33:55
%S A306393 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 A306393 60,20,80,240,480,640,720,720,720,640,480,240,80,210,840,1890,3150,
%U A306393 4200,4830,5040,5040,4830,4200,3150,1890,840,210
%N A306393 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 A306393 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 A306393 T(n,0) counts perfect (binary) heaps on n elements (A056971).
%H A306393 Alois P. Heinz, <a href="/A306393/b306393.txt">Rows n = 0..100, flattened</a>
%H A306393 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 A306393 Marko Riedel, <a href="/A306393/a306393.pdf">Average number of inversions in a random binary heap on 2^n-1 elements (PDF)</a>.
%H A306393 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>,
%H A306393 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>.
%H A306393 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>.
%F A306393 T(n,k) = T(n,A061168(n)-k) for n > 0.
%F A306393 Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).
%e A306393 T(4,0) = 3: 4231, 4312, 4321.
%e A306393 T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
%e A306393 T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
%e A306393 T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
%e A306393 T(4,4) = 3: 1234, 1243, 1324.
%e A306393 T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
%e A306393 (The examples use max-heaps.)
%e A306393 Triangle T(n,k) begins:
%e A306393 1;
%e A306393 1;
%e A306393 1, 1;
%e A306393 2, 2, 2;
%e A306393 3, 6, 6, 6, 3;
%e A306393 8, 16, 24, 24, 24, 16, 8;
%e A306393 20, 60, 100, 120, 120, 120, 100, 60, 20;
%e A306393 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
%e A306393 ...
%p A306393 b:= proc(u, o) option remember; local n, g, l; n:= u+o;
%p A306393 if n=0 then 1
%p A306393 else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
%p A306393 add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
%p A306393 b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
%p A306393 add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
%p A306393 b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
%p A306393 fi
%p A306393 end:
%p A306393 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p A306393 seq(T(n), n=0..10);
%t A306393 b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
%t A306393 If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
%t A306393 Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
%t A306393 b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
%t A306393 Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
%t A306393 b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
%t A306393 T[n_] := CoefficientList[b[n, 0], x];
%t A306393 T /@ Range[0, 10] // Flatten (* _Jean-François Alcover_, Feb 15 2021, after _Alois P. Heinz_ *)
%Y A306393 Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
%Y A306393 Row sums give A000142.
%Y A306393 Central terms (also maxima) of rows give A324075.
%Y A306393 Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
%Y A306393 Average number of inversions of a full binary heap on 2^n-1 elements is A000337.
%K A306393 nonn,tabf
%O A306393 0,5
%A A306393 _Alois P. Heinz_, Feb 12 2019