A230056 -id:A230056 - cp's OEIS frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360

Offset: 0

Alois P. Heinz, Feb 08 2019

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    1;
    1,    1;
    2,    2,     2;
    3,    9,     9,     3;
    8,   28,    48,    28,      8;
   20,   90,   250,   250,     90,    20;
   80,  360,  1200,  1760,   1200,   360,    80;
  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;
  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
  ...

Alois P. Heinz, Rows n = 0..190, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

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:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n = u + o, g, l},
     If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
     Sum[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[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}]*x]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)

T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

A229039 G.f.: Sum_{n>=0} (n+2)^n * x^n / (1 + (n+2)*x)^n.

Original entry on oeis.org

1, 3, 7, 24, 108, 600, 3960, 30240, 262080, 2540160, 27216000, 319334400, 4071513600, 56043187200, 828193766400, 13076743680000, 219689293824000, 3912561709056000, 73627297615872000, 1459741204905984000, 30411275102208000000, 664182248232222720000

Offset: 0

Paul D. Hanna, Sep 11 2013

nonn

More generally, we have the identity:
if Sum_{n>=0} a(n)*x^n = Sum_{n>=0} (b*n+c)^n * x^n / (1 + (b*n+c)*x)^n,
then Sum_{n>=0} a(n)*x^n/n! = (2 - 2*(b-c)*x + b*(b-2*c)*x^2)/(2*(1-b*x)^2)
so that a(n) = (b*n + (b+2*c)) * b^(n-1) * n!/2 for n>0 with a(0)=1.

			O.g.f.: A(x) = 1 + 3*x + 7*x^2 + 24*x^3 + 108*x^4 + 600*x^5 + 3960*x^6 +...
where
A(x) = 1 + 3*x/(1+3*x) + 4^2*x^2/(1+4*x)^2 + 5^3*x^3/(1+5*x)^3 + 6^4*x^4/(1+6*x)^4 + 7^5*x^5/(1+7*x)^5 +...
E.g.f.: E(x) = 1 + 3*x + 7*x^2/2! + 24*x^3/3! + 108*x^4/4! + 600*x^5/5! +...
where
E(x) = 1 + 3*x + 7/2*x^2 + 4*x^3 + 9/2*x^4 + 5*x^5 + 11/2*x^6 + 6*x^7 +...
which is the expansion of: (2 + 2*x - 3*x^2) / (2 - 4*x + 2*x^2).

Cf. A038720, A230056, A187735, A187738, A187739, A229039, A221160, A221161, A187740.

a[n_] := (n + 5)*n!/2; a[0] = 1; Array[a, 20, 0] (* Amiram Eldar, Dec 11 2022 *)

{a(n)=polcoeff( sum(m=0, n, ((m+2)*x)^m / (1 + (m+2)*x +x*O(x^n))^m), n)}
for(n=0, 20, print1(a(n), ", "))

{a(n)=if(n==0,1, (n+5) * n!/2 )}
for(n=0, 20, print1(a(n), ", "))

a(n) = (n+5) * n!/2 for n>0 with a(0)=1.
E.g.f.: (2 + 2*x - 3*x^2)/(2*(1-x)^2).
From Amiram Eldar, Dec 11 2022: (Start)
Sum_{n>=0} 1/a(n) = 18*e - 237/5.
Sum_{n>=0} (-1)^n/a(n) = 243/5 - 130/e. (End)

cp's OEIS Frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula