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!)
A306356 Number of defective (binary) heaps on n elements with floor(n/2) defects. 2
1, 1, 1, 2, 9, 48, 250, 1760, 12502, 111776, 1017060, 11165280, 123760560, 1602344832, 21025461600, 314958758400, 4765553385120, 80958196300800, 1386261729792960, 26344715667079680, 502986050203680000, 10556482426015426560, 222685725334400064000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

LINKS

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

FORMULA

a(n) = A306343(n,floor(n/2)).

EXAMPLE

a(2) = 1: 12.

a(3) = 2: 213, 231.

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

a(5) = 48: 14523, 14532, 15234, 15243, 15324, 15342, 15423, 15432, 24135, 24153, 24513, 24531, 25314, 25341, 25413, 25431, 31245, 31254, 32145, 32154, 32415, 32451, 32514, 32541, 34125, 34152, 34215, 34251, 34512, 34521, 35412, 35421, 41235, 41253, 41325, 41352, 42135, 42153, 42513, 42531, 51234, 51243, 51324, 51342, 51423, 51432, 52134, 52143.

(The examples use max-heaps.)

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:

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

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

CROSSREFS

Cf. A056971, A306343.

Sequence in context: A289576 A223832 A323958 * A188818 A047139 A190315

Adjacent sequences:  A306353 A306354 A306355 * A306357 A306358 A306359

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Feb 09 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 February 19 13:03 EST 2020. Contains 332044 sequences. (Running on oeis4.)