This site is supported by donations to The OEIS Foundation.

 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.

Last modified July 16 23:49 EDT 2019. Contains 325092 sequences. (Running on oeis4.)