login
This site is supported by donations to The OEIS 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);

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:  A306389 A306390 A306392 * A306394 A306395 A306398

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 March 20 09:35 EDT 2019. Contains 321345 sequences. (Running on oeis4.)