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,3

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.

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

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

Prog

(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
(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 */

Crossrefs

Cf. A000108.

Sequence in context: A026876 A270447 A151090 * A151091 A151092 A151093

Adjacent sequences: A059275 A059276 A059277 * A059279 A059280 A059281

Keyword

nonn

Author

N. J. A. Sloane, Jan 24 2001

Status

approved