A059278 G.f. is G(x*(1-x)/(1-2*x)) where G(x) is g.f. for Catalan numbers A000108.

1, 1, 3, 11, 43, 175, 735, 3167, 13935, 62383, 283311, 1302271, 6047679, 28332991, 133752191, 635618431, 3038326911, 14599154431, 70474889471, 341624867071, 1662254107391, 8115717976831, 39747223425791, 195219110182911, 961330824858623

Offset: 0

Author

N. J. A. Sloane, Jan 24 2001

Keywords

• nonn

Links

• Robert Israel, Table of n, a(n) for n = 0..1000
• Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 18.

Crossrefs

Cf. A000108.

Programs

Maple

f:= gfun:-rectoproc({(4+8*n)*a(n)+(-36-24*n)*a(1+n)+(60+24*n)*a(n+2)+(-33-9*n)*a(n+3)+(5+n)*a(n+4), a(0) = 1, a(1) = 1, a(2) = 3, a(3) = 11},a(n),remember):
map(f, [$0..30]); # Robert Israel, Mar 04 2016

Mathematica

CoefficientList[Series[(2*x-1+Sqrt[(1-2*x)*(1-6*x+4*x^2)])/(2*x*(x-1)), {x, 0, 20}], x] (* Vaclav Kotesovec, Jun 19 2014 *)
Table[Sum[CatalanNumber[k] Sum[2^i Binomial[k, n - k - i] Binomial[k + i - 1, i] (-1)^(n - k - i), {i, 0, n - k}], {k, 0, n}], {n, 0, 24}] (* Michael De Vlieger, Mar 04 2016 *)

Maxima

a(n):=sum((binomial(2*k,k)*sum(2^i*binomial(k,n-k-i)*binomial(k+i-1,i)*(-1)^(n-k-i),i,0,n-k))/(k+1),k,0,n); /* Vladimir Kruchinin, Mar 04 2016 */

PARI

a(n)=polcoeff((2*x-1 +sqrt((1-2*x)*(1-6*x+4*x^2)+x^2*O(x^n))) /(2*x^2-2*x), n);

PARI

x='x+O('x^100); Vec((2*x-1+sqrt((1-2*x)*(1-6*x+4*x^2)))/(2*x*(x-1))) \\ Altug Alkan, Mar 05 2016

Formula

G.f.: (2*x-1+sqrt((1-2*x)*(1-6*x+4*x^2)))/(2*x*(x-1)).

G.f.: W(0), where W(k) = 1 + (4*k+1)*x*(1-x)/( (k+1)*(1-2*x) - 2*x*(1-x)*(1-2*x)*(k+1)*(4*k+3)/(2*x*(1-x)*(4*k+3) + (2*k+3)*(1-2*x)/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013

Recurrence: (n+1)*a(n) = 3*(3*n-1)*a(n-1) - 12*(2*n-3)*a(n-2) + 12*(2*n-5)*a(n-3) - 4*(2*n-7)*a(n-4). - Vaclav Kotesovec, Jun 19 2014

a(n) ~ sqrt(10-2*sqrt(5)) * (3+sqrt(5))^n / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 19 2014. Equivalently, a(n) ~ 5^(1/4) * 2^n * phi^(2*n - 1/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 06 2021

a(n) = Sum_{k=0..n} C(k)*Sum_{i=0..n-k} 2^i*binomial(k,n-k-i)*binomial(k+i-1,i)*(-1)^(n-k-i), where C(k) is the k-th Catalan number. - Vladimir Kruchinin, Mar 04 2016