A120588 G.f. is 1 + x*c(x), where c(x) is the g.f. of the Catalan numbers (A000108).

1, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152

Offset: 0

Author

Paul D. Hanna, Jun 16 2006, Jan 24 2008

Keywords

• nonn
• easy

Comments

Previous name was: G.f. satisfies: 3*A(x) = 2 + x + A(x)^2, with A(0) = 1.

This is essentially a duplicate of entry A000108, the Catalan numbers (a(n) = A000108(n-1) for n>0).

In order for the g.f. of an integer sequence to satisfy a functional equation of the form: r*A(x) = c + b*x + A(x)^n, where n > 1, it is necessary that the sequence start with [1, d, m*n*(n-1)/2], where d divides m*n*(n-1)/2 (m>0) and that the coefficients are given by r = n + d^2/m, c = r-1 and b = d^3/m. The remaining terms may then be integer and still satisfy: a_n(k) = r*a(k), where a_n(k) is the k-th term of the n-th self-convolution of the sequence.

Examples

			A(x) = 1 + x + x^2 + 2*x^3 + 5*x^4 + 14*x^5 + 42*x^6 + 132*x^7 +...
A(x)^3 = 1 + 2*x + 3*x^2 + 6*x^3 + 15*x^4 + 42*x^5 + 126*x^6 + 396*x^7 +..
More generally, given the functional equation:
r*A(x) = r-1 + b*x + A(x)^n
the series solution is:
A(x) = Sum_{i>=0} C(n*i,i)/(n*i-i+1)*(r-1+bx)^(n*i-i+1)/r^(n*i+1)
which can be expressed as:
A(x) = G( (r-1+bx)^(n-1)/r^n ) * (r-1+bx)/r
where G(x) satisfies: G(x) = 1 + x*G(x)^n .
Also we have:
A(x) = 1 + Series_Reversion[ (1 + r*x - (1+x)^n )/b ].
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000108, A120589 (A(x)^2); A120590 - A120607.

Cf. A001850, A026641.

Programs

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (3 - Sqrt(1-4*x))/2 )); // G. C. Greubel, Feb 18 2019

Mathematica

a[ n_] := SeriesCoefficient[ 1 + (1 - Sqrt[1 - 4 x]) / 2, {x, 0, n}]; (* Michael Somos, May 18 2015 *)

PARI

{a(n)=local(A=1+x+x^2+x*O(x^n));for(i=0,n,A=A-3*A+2+x+A^2);polcoeff(A,n)}

PARI

{a(n) = my(A); if( n<1, n==0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 23 2011 */

Sage

((3-sqrt(1-4*x))/2).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 18 2019

Formula

G.f.: A(x) = 1 + Series_Reversion(1+3*x - (1+x)^2).

Lagrange Inversion yields g.f.: A(x) = Sum_{n>=0} C(2*n,n)/(n+1)*(2+x)^(n+1)/3^(2*n+1).

G.f.: (3 - sqrt(1-4*x))/2. - Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009

a(n) = Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011

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

G.f.: 2 - G(0), where G(k)= 1 - x/G(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Jul 19 2013

a(n) ~ 2^(2*n-2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 19 2013

Given g.f. A(x), A001850(n-1) = coefficient of x^n in A(x)^n if n>0, the derivative of log(A(x)) is the g.f. for A026641. - Michael Somos, May 18 2015

A(x) = (1 + 2*Sum_{n >= 1} Catalan(n)*x^n)/(1 + Sum_{n >= 1} Catalan(n)*x^n) = (1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016

D-finite with recurrence n*a(n) +2*(-2*n+3)*a(n-1)=0. - R. J. Mathar, Nov 22 2024

Extensions

New name by Wolfdieter Lang, Feb 06 2020