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

Last modified March 20 09:35 EDT 2019. Contains 321345 sequences. (Running on oeis4.)