login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows. 14
1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

A defect in a defective heap is a parent-child pair not having the correct order.

T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).

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

LINKS

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

FORMULA

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

Sum_{k>=0} k * T(n,k) = A001286(n).

Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.

Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.

Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.

Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

EXAMPLE

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

T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.

T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.

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

(The examples use max-heaps.)

Triangle T(n,k) begins:

    1;

    1;

    1,    1;

    2,    2,     2;

    3,    9,     9,     3;

    8,   28,    48,    28,      8;

   20,   90,   250,   250,     90,    20;

   80,  360,  1200,  1760,   1200,   360,    80;

  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;

  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;

  ...

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(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(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)*x)

      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, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.

Row sums give A000142.

T(n,floor(n/2)) gives A306356.

Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

Sequence in context: A110910 A119532 A010583 * A238188 A051007 A240166

Adjacent sequences:  A306340 A306341 A306342 * A306344 A306345 A306346

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Feb 08 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 16 23:49 EDT 2019. Contains 325092 sequences. (Running on oeis4.)