A090344 Number of Motzkin paths of length n with no level steps at odd level.

1, 1, 2, 3, 6, 11, 23, 47, 102, 221, 493, 1105, 2516, 5763, 13328, 30995, 72556, 170655, 403351, 957135, 2279948, 5449013, 13063596, 31406517, 75701508, 182902337, 442885683, 1074604289, 2612341856, 6361782007, 15518343597, 37912613631, 92758314874

Offset: 0

Author

Emeric Deutsch, Jan 28 2004

Keywords

• nonn

Comments

a(n) = number of Motzkin paths of length n that avoid UF. Example: a(3) counts FFF, UDF, FUD but not UFD. - David Callan, Jul 15 2004

Also, number of 1-2 trees with n edges and with thinning limbs. A 1-2 tree is an ordered tree with vertices of outdegree at most 2. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children. - Emeric Deutsch and Louis Shapiro, Nov 04 2006

Examples

			a(3)=3 because we have HHH, HUD and UDH, where U=(1,1), D=(1,-1) and H=(1,0).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
• Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
• Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).

Crossrefs

Cf. A001006, A086622, A098474, A124344, A124497.

Cf. A014137, A023431, A144700.

Programs

Magma

[(&+[Binomial(n-k, k)*Catalan(k): k in [0..Floor(n/2)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

Maple

C:=x->(1-sqrt(1-4*x))/2/x: G:=C(z^2/(1-z))/(1-z): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..36);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, (n^2-n+2)/2,
     ((2*n+2)*a(n-1) -(4*n-6)*a(n-3) +(3*n-4)*a(n-2))/(n+2))
    end:
seq(a(n), n=0..40); # Alois P. Heinz, May 17 2013

Mathematica

Table[HypergeometricPFQ[{1/2, (1-n)/2, -n/2}, {2, -n}, -16], {n, 0, 40}] (* Jean-François Alcover, Feb 20 2015, after Paul Barry *)

PARI

{a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))+x^2*A^2+x*O(x^n));polcoeff(A,n)} \\ Paul D. Hanna, Jun 24 2012

SageMath

[sum(binomial(n-k,k)*catalan_number(k) for k in (0..(n//2))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

Formula

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

G.f. satisfies: A(x) = 1/(1-x) + x^2*A(x)^2. - Paul D. Hanna, Jun 24 2012

D-finite with recurrence (n+2)*a(n) = 2*(n+1)*a(n-1) + (3*n-4)*a(n-2) - 2*(2*n-3)*a(n-3). - Vladeta Jovovic, Sep 11 2004

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*binomial(2*k, k)/(k+1). - Paul Barry, Nov 13 2004

a(n) = 1 + Sum_{k=1..n-1} a(k-1)*a(n-k-1). - Henry Bottomley, Feb 22 2005

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

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

Recurrence (an alternative): (n+2)*a(n) = 3*(n+1)*a(n-1) + (n-4)*a(n-2) - (7*n-13)*a(n-3) + 2*(2*n-5)*a(n-4), n>=4. - Fung Lam, Apr 01 2014

Asymptotics: a(n) ~ (8/(sqrt(17)-1))^n*( 1/17^(1/4) + 17^(1/4) )*17 /(16*sqrt(Pi*n^3)). - Fung Lam, Apr 01 2014

a(n) = 2*A026569(n) + A026569(n+1)/2 - A026569(n+2)/2. - Mark van Hoeij, Nov 29 2024