cp's OEIS Frontend

A306356 Number of defective (binary) heaps on n elements with floor(n/2) defects.

%I A306356 #24 Feb 16 2025 08:33:55
%S A306356 1,1,1,2,9,48,250,1760,12502,111776,1017060,11165280,123760560,
%T A306356 1602344832,21025461600,314958758400,4765553385120,80958196300800,
%U A306356 1386261729792960,26344715667079680,502986050203680000,10556482426015426560,222685725334400064000
%N A306356 Number of defective (binary) heaps on n elements with floor(n/2) defects.
%C A306356 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)).
%H A306356 Alois P. Heinz, <a href="/A306356/b306356.txt">Table of n, a(n) for n = 0..190</a>
%H A306356 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A306356 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A306356 a(n) = A306343(n,floor(n/2)).
%e A306356 a(2) = 1: 12.
%e A306356 a(3) = 2: 213, 231.
%e A306356 a(4) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
%e A306356 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.
%e A306356 (The examples use max-heaps.)
%p A306356 b:= proc(u, o) option remember; local n, g, l; n:= u+o;
%p A306356       if n=0 then 1
%p A306356     else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
%p A306356          add(add(binomial(j-1, i)*binomial(n-j, l-i)*
%p A306356          b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
%p A306356          add(add(binomial(j-1, i)*binomial(n-j, l-i)*
%p A306356          b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
%p A306356       fi
%p A306356     end:
%p A306356 a:= n-> coeff(b(n, 0), x, iquo(n, 2)):
%p A306356 seq(a(n), n=0..25);
%t A306356 b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u+o; If[n == 0, 1,
%t A306356    g = 2^(Length@IntegerDigits[n, 2]-1); l = Min[g-1, n-g/2]; Expand[
%t A306356    Sum[Sum[Binomial[j-1, i]*Binomial[n-j, l-i]*
%t A306356    b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}] +
%t A306356    Sum[Sum[Binomial[j-1, i]*Binomial[n-j, l-i]*
%t A306356    b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
%t A306356 a[n_] := Coefficient[b[n, 0], x, Quotient[n, 2]];
%t A306356 a /@ Range[0, 25] (* _Jean-François Alcover_, Mar 26 2021, after _Alois P. Heinz_ *)
%Y A306356 Cf. A056971, A306343.
%K A306356 nonn
%O A306356 0,4
%A A306356 _Alois P. Heinz_, Feb 09 2019