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

%I #30 Mar 02 2024 10:37:17

%S 1,2,8,40,144,448,1280,3456,8960,22528,55296,133120,315392,737280,

%T 1703936,3899392,8847360,19922944,44564480,99090432,219152384,

%U 482344960,1056964608,2306867200,5016387584,10871635968,23488102400

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

%H Henry Bottomley and Antti Karttunen, <a href="/A073345/a073345.txt">Notes concerning diagonals of the square arrays A073345 and A073346</a>.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-12,8).

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

%F 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).

%F 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]

%F 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

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

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

%t Table[If[n < 2, n + 1, 2^(n - 1)*(n + 2) (n - 1)], {n, 0, 26}] (* or *)

%t 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 *)

%t LinearRecurrence[{6,-12,8},{1,2,8,40,144},30] (* _Harvey P. Dale_, Jun 20 2021 *)

%o (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

%Y Cf. A000096, A073346

%K nonn,easy

%O 0,2

%A _Antti Karttunen_, Aug 19 2002