A323957 - OEIS

%I #20 May 08 2024 14:23:15

%S 0,1,2,9,28,90,360,1526,7616,32460,190800,947760,6382464,37065600,

%T 296524800,1812861600,15283107840,105015593280,1017540576000,

%U 7304720544000,74472335308800,629300251008000,7429184791142400,62417372203929600,746041213793075200

%N Number of defective (binary) heaps on n elements with exactly one defect.

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

%H Alois P. Heinz, <a href="/A323957/b323957.txt">Table of n, a(n) for n = 1..215</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>

%e a(2) = 1: 12.

%e a(3) = 2: 213, 231.

%e a(4) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.

%e a(5) = 28: 25134, 25143, 35124, 35142, 35214, 35241, 42315, 42351, 43125, 43152, 43215, 43251, 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.

%e a(6) = 90: 362451, 362541, 436125, 436215, ..., 652314, 652413, 653124, 653214.

%e (The examples use max-heaps.)

%p b:= proc(u, o) option remember; local n, g, l; n:= u+o;

%p       if n=0 then 1

%p     else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(

%p          add(add(binomial(j-1, i)*binomial(n-j, l-i)*

%p          b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+

%p          add(add(binomial(j-1, i)*binomial(n-j, l-i)*

%p          b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)

%p       fi

%p     end:

%p a:= n-> coeff(b(n, 0), x, 1):

%p seq(a(n), n=1..25);

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

%t      g = 2^(Length[IntegerDigits[n, 2]] - 1);

%t      l = Min[g - 1, n - g/2]; Expand[

%t      Sum[ Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*

%t      b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}] +

%t      Sum[Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*

%t      b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];

%t a[n_] := Coefficient[b[n, 0], x, 1];

%t Array[a, 25] (* _Jean-François Alcover_, Apr 22 2021, after _Alois P. Heinz_ *)

%Y Column k=1 of A306343.

%Y Cf. A056971, A372628, A372643.

%K nonn

%O 1,3

%A _Alois P. Heinz_, Feb 09 2019