A101499 A Chebyshev transform of the Catalan numbers.

1, 1, 1, 3, 9, 25, 73, 223, 697, 2217, 7161, 23427, 77457, 258417, 868881, 2941311, 10016241, 34289041, 117935473, 407344771, 1412307481, 4913508489, 17148100569, 60018592735, 210619695913, 740910077497, 2612194773481

Offset: 0

Author

Paul Barry, Dec 04 2004

Keywords

• easy
• nonn

Comments

A Chebyshev transform of A000108. Under the Chebyshev transform, we map a g.f. g(x) to (1/(1+x^2))g(x/(1+x^2)). Also equivalent to a Catalan transform followed by the Chebyshev transform to 1/(1-x), where the Catalan transform maps h(x)->h(xc(x)), c(x) the g.f. of A000108.

a(n) is the number of peakless Motzkin paths of length n in which the (1,0)-steps at level >=1 come in 2 colors. Example: a(4)=9 because, denoting u=(1,1), h=(1,0), and d=(1,-1), we have 1 path of shape hhhh, 2 paths of shape huhd, 2 paths of shape uhdh, and 2^2=4 paths of shape uhhd. - Emeric Deutsch, May 03 2011

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
• Jean-Luc Baril and Paul Barry, Two kinds of partial Motzkin paths with air pockets, arXiv:2212.12404 [math.CO], 2022.
• Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, Consecutive pattern-avoidance in Catalan words according to the last symbol, Univ. Bourgogne (France 2023).

Crossrefs

Cf. A000108, A049310.

Programs

Mathematica

CoefficientList[Series[(Sqrt[1+x^2]-Sqrt[1-4*x+x^2])/(2*x*Sqrt[1+x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 08 2014 *)

PARI

{a(n)=local(A); if(n<0, 0, n++; A=serreverse(x-x^2+x*O(x^n)); polcoeff( subst(A, x, x/(1+x^2)), n))} /* Michael Somos, Sep 18 2006 */

Formula

G.f.: (sqrt(1+x^2)-sqrt(1-4x+x^2))/(2x*sqrt(1+x^2)); a(n)=sum{k=0..floor(n/2), binomial(n-k, k)C(n-2k)}; a(n)=sum{k=0..floor(n/2), sum{i=0..n-2k, sum{j=0..n-2k, ((2i+1)/(n-2k+i+1))(-1)^(i-j)C(2n-4k, n-2k-i)C(i, j)}}}.

Given g.f. A(x) then B(x)=x*A(x) satisfies 0=f(x, B(x)) where f(x, y)= x-(1+x^2)*(y-y^2) . - Michael Somos, Sep 18 2006

Given g.f. A(x) then B(x)=x*A(x) satisfies 0=f(B(x), B(x^2), B(x^4)) where f(u, v, w)= w -v^2*w^2 -(1-v)*w*(v+w) +(u-u^2)^2*(v^2+w^2-v-w). - Michael Somos, Sep 18 2006

Given g.f. A(x) then B(x)=x*A(x) satisfies 0=f(B(x), B(x^2)) where f(u, v)= (v-v^2) -(u-u^2)^2*(1+2*(v-v^2)). - Michael Somos, Sep 18 2006

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

a(n) ~ (5+3*sqrt(3)) * sqrt(2*sqrt(3)-3) * (2 + sqrt(3))^n / (8 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 08 2014