A090345 Number of Motzkin paths of length n with no level steps at even level.

1, 0, 1, 1, 3, 5, 12, 24, 55, 119, 272, 612, 1411, 3247, 7565, 17667, 41561, 98099, 232696, 553784, 1322813, 3169065, 7614583, 18342921, 44294991, 107200829, 259983346, 631718606, 1537737567, 3749440151, 9156561590, 22394270034, 54845701243, 134497468359

Offset: 0

Author

Emeric Deutsch, Jan 28 2004

Keywords

• nonn

Comments

Hankel transform of a(n) is A000012. Hankel transform of a(n+1) is 0,-1,0,1,0,-1,0,... or -[x^n](x/(1+x^2)). Hankel transform of a(n+2) is A008619(n+1). - Paul Barry, Mar 23 2011

Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k and down steps D = (1,-1). For instance, for n=5, we have the 5 paths: U(4)D, U(2)U(1)DD, U(1)U(2)DD, U(2)DU(1)D, U(1)DU(2)D. - José Luis Ramírez Ramírez, Apr 19 2015

Examples

			a(5)=5 because we have UHDUD, UDUHD, UHUDD, UUDHD and UHHHD, where U=(1,1), D=(1,-1) and H=(1,0).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• David Callan, Some bijections for lattice paths, arXiv:2112.05241 [math.CO], 2021.
• Emeric Deutsch, Emanuele Munarini and Simone Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs, Journal of Statistical Planning and Inference, Vol. 140, Issue 6, June 2010, pp. 1550-1562.

Crossrefs

Cf. A001006.

First differences of A090344.

Programs

Mathematica

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

Formula

G.f.: (1 - z - sqrt(1 - 2*z - 3*z^2 + 4*z^3))/(2*z^2).

G.f. A(x) satisfies A(x) = A(x/(x-1)). - Vladeta Jovovic, Jul 07 2004

Also (x*A)^2 = (1-x)*(A-1). - Vladeta Jovovic, Jul 07 2004

G.f.: 1/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Apr 08 2009

G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z=x^2/(1-x) (continued fraction); in other words, g.f.: C(x^2/(1-x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011

a(0) = 1, a(n) = Sum_{k=0..floor(n/2)} (k/(n-k))*binomial(n-k,k)*A000108(k). - Paul Barry, Jul 01 2009

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1, n-2k)*A000108(k). - Paul Barry, Mar 23 2011

The sequence starting with offset 1 = iterates of M*V, leftmost column. M = an infinite tridiagonal matrix with all 1's in the sub and superdiagonals and [0,1,0,1,0,1,0,1,...] as the main diagonal; and the rest zeros. V = vector [1,0,0,0,...]. - Gary W. Adamson, Jun 08 2011

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

a(n) ~ sqrt(34+2*sqrt(17)) * ((1+sqrt(17))/2)^n / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014

a(0) = 1, a(1) = 0; a(n) = a(n-1) + Sum_{k=0..n-2} a(k) * a(n-k-2). - Ilya Gutkovskiy, Jul 20 2021