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,3

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

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).

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

Example

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

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 *)

Prog

(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
(Magma) [(&+[Binomial(n-k, k)*Catalan(k): k in [0..Floor(n/2)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022
(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

Crossrefs

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

Cf. A014137, A023431, A144700.

Sequence in context: A274937 A359392 A199142 * A277795 A198662 A198620

Adjacent sequences: A090341 A090342 A090343 * A090345 A090346 A090347

Keyword

nonn

Author

Emeric Deutsch, Jan 28 2004

Status

approved