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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A324075 Number of defective (binary) heaps on n elements having one half of their ancestor-successor pairs (rounded down) distorted. 2
1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 359520, 3590400, 39362400, 472919040, 6133670400, 85948262400, 1284106824000, 20434058444800, 345796766515200, 6188467544064000, 117398964114432000, 2341018467532800000, 49035684501872640000, 1074839883779211264000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Number of permutations p of [n] having exactly floor(A061168(n)/2) pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

Central terms (also maxima) of rows of A306393.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..100

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Wikipedia, Permutation

FORMULA

a(n) = A306393(floor(A061168(n)/2)).

a(n) <= (n-1)! for n >= 1 with equality only for n <= 9.

MAPLE

h:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+h(n-1)) end:

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:

a:= n-> coeff(b(n, 0), x, iquo(h(n), 2)):

seq(a(n), n=0..25);

MATHEMATICA

h[n_] := h[n] = If[n < 1, 0, Length[IntegerDigits[n, 2]] - 1 + h[n - 1]];

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o; If[n == 0, 1,

     g = 2^(Length[IntegerDigits[n, 2]] - 1); 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}]]]];

a[n_] := Coefficient[b[n, 0], x, Quotient[h[n], 2]];

a /@ Range[0, 25] (* Jean-Fran├žois Alcover, Apr 23 2021, after Alois P. Heinz *)

CROSSREFS

Cf. A000142, A000523, A061168, A306393.

Sequence in context: A152637 A152645 A054873 * A193936 A226440 A248841

Adjacent sequences:  A324072 A324073 A324074 * A324076 A324077 A324078

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Feb 14 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 28 17:15 EDT 2021. Contains 346335 sequences. (Running on oeis4.)