login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 15
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, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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)).

T(n,0) counts perfect (binary) heaps on n elements (A056971).

LINKS

Alois P. Heinz, Rows n = 0..100, flattened

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Wikipedia, Permutation

FORMULA

T(n,k) = T(n,A061168(n)-k) for n > 0.

Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).

EXAMPLE

T(4,0) = 3: 4231, 4312, 4321.

T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.

T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.

T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.

T(4,4) = 3: 1234, 1243, 1324.

T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.

(The examples use max-heaps.)

Triangle T(n,k) begins:

   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,  60,  20;

  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;

  ...

MAPLE

b:= proc(u, o) option remember; local n, g, l; n:= u+o;

      if n=0 then 1

    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(

         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*

         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+

         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*

         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))

      fi

    end:

T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):

seq(T(n), n=0..10);

MATHEMATICA

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;

     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[

     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*

     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +

     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*

     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];

T[n_] := CoefficientList[b[n, 0], x];

T /@ Range[0, 10] // Flatten (* Jean-Fran├žois Alcover, Feb 15 2021, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.

Row sums give A000142.

Central terms (also maxima) of rows give A324075.

Cf. A000523, A008302, A061168, A120385, A306343, A324074.

Sequence in context: A193450 A109906 A104856 * A324763 A038715 A293518

Adjacent sequences:  A306390 A306391 A306392 * A306394 A306395 A306396

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Feb 12 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 28 00:54 EDT 2021. Contains 346316 sequences. (Running on oeis4.)