A187256 Number of peakless Motzkin paths of length n, assuming that the (1,0)-steps come in 2 colors.

1, 2, 4, 10, 28, 82, 248, 770, 2440, 7858, 25644, 84618, 281844, 946338, 3199728, 10885122, 37230352, 127951714, 441633812, 1530242954, 5320853260, 18560408050, 64932101224, 227767796482, 800928670232, 2822814469394, 9969770245948, 35280714655498

Offset: 0

Author

Emeric Deutsch, May 03 2011

Keywords

• nonn

Comments

Ordinary peakless Motzkin paths are counted by A004148.

Also the number of Catalan words of length n avoiding the consecutive pattern 010. - Sela Fried, May 21 2025

Examples

			a(4)=28 because, denoting U=(1,1), D=(1,-1), and H=(1,0), we have 2^4=16 paths of shape HHHH, 2^2=4 paths of shape HUHD, 2^2 = 4 paths of shape UHDH, and 4 paths of shape UHHD.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv:1107.5490 [math.CO], 2011.
• Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
• Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.

Crossrefs

Cf. A004148, A328504

Column k=0 of A114848 (shifted). - Alois P. Heinz, Mar 31 2016

Programs

Maple

eq := G = 1+2*z*G+z^2*G*(G-1): G := RootOf(eq, G): Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 0 .. 27);

Mathematica

CoefficientList[Series[(1 + (x-2)*x - Sqrt[(1 + (x-4)*x)*(1+x^2)])/(2*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Jun 02 2014 *)
a[n_] := 2^n HypergeometricPFQ[{-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2}, {2, -n, -n + 1}, 4]; Array[a, 28, 0] (* Peter Luschny, Jan 25 2020 *)

Maxima

a(n):=sum(((-1)^i*binomial(n-i,i)*binomial(2*n-4*i+2,n-2*i))/(n-2*i+1),i,0,(n)/2); /* Vladimir Kruchinin, Jun 01 2014 */

PARI

my(x='x+O('x^50)); Vec((1 + (x-2)*x - sqrt((1 + (x-4)*x)*(1+x^2))) /( 2*x^2)) \\ G. C. Greubel, Feb 12 2017

Formula

G.f.: G(z) satisfies the equation G = 1 + 2*z*G + z^2*G*(G-1).

Conjecture: (n+2)*a(n) -2*(2*n+1)*a(n-1) +2*(n-1)*a(n-2) +2*(5-2*n)*a(n-3) +(n-4)*a(n-4) = 0. - R. J. Mathar, Nov 16 2011

a(n) = Sum_{i=0..n/2} (-1)^i*binomial(n-i,i)*binomial(2*n-4*i+2,n-2*i)/(n-2*i+1). - Vladimir Kruchinin, Jun 01 2014

a(n) ~ sqrt(24+14*sqrt(3)) * (2+sqrt(3))^n / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 02 2014

a(n) = 2^n*hypergeom([-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2], [2, -n, -n + 1], 4). - Peter Luschny, Jan 25 2020