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

 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.

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