A074092 Number of plane binary trees of size n+3 and contracted height n.

1, 2, 8, 40, 144, 448, 1280, 3456, 8960, 22528, 55296, 133120, 315392, 737280, 1703936, 3899392, 8847360, 19922944, 44564480, 99090432, 219152384, 482344960, 1056964608, 2306867200, 5016387584, 10871635968, 23488102400

Offset: 0

Author

Antti Karttunen, Aug 19 2002

Keywords

• nonn
• easy

Links

• Henry Bottomley and Antti Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
• Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Crossrefs

Cf. A000096, A073346

Programs

Maple

A074092 := n -> `if`((n < 2),n+1,2^(n-1)*(n+2)*(n-1));
A074092v2 := n -> `if`((n < 2),n+1,(2^n)*(binomial(n,n-2)+binomial(n-1,n-2)));

Mathematica

Table[If[n < 2, n + 1, 2^(n - 1)*(n + 2) (n - 1)], {n, 0, 26}] (* or *)
CoefficientList[Series[(1 - 4 x + 8 x^2 + 8 x^3 - 16 x^4)/(1 - 2 x)^3, {x, 0, 26}], x] (* Michael De Vlieger, Sep 22 2017 *)
LinearRecurrence[{6,-12,8},{1,2,8,40,144},30] (* Harvey P. Dale, Jun 20 2021 *)

PARI

Vec((1-4*x+8*x^2+8*x^3-16*x^4)/(1-2*x)^3+O(x^99)) \\ Charles R Greathouse IV, Mar 21 2012

Formula

a(n) = A073346(n+3, n).

a(0) = 1, a(1) = 2, a(n) = 2^(n-1)*(n+2)*(n-1) = (2^n)*(C(n, n-2)+C(n-1, n-2)) = 2^n * A000096(n-1).

a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>4. G.f.: (1-4*x+8*x^2+8*x^3-16*x^4)/(1-2*x)^3. [Colin Barker, Mar 21 2012]

For n>1, a(n) = (1/2) * Sum_{k=0..n+1} Sum_{i=0..n+1} (k-1) * C(n+1,i). - Wesley Ivan Hurt, Sep 20 2017