

A090344


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


14



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 12 trees with n edges and with thinning limbs. A 12 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, Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
P Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6


FORMULA

G.f.: (1xsqrt(12*x3*x^2+4*x^3))/(2*x^2*(1x)).
G.f. satisfies: A(x) = 1/(1x) + x^2*A(x)^2.  Paul D. Hanna, Jun 24 2012
Dfinite with recurrence (n+2)*a(n)(2*n+2)*a(n1)(3*n4)*a(n2)+(4*n6)*a(n3) = 0.  Vladeta Jovovic, Sep 11 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(nk, k)*binomial(2*k, k)/(k+1)).  Paul Barry, Nov 13 2004
a(n) = 1 + Sum_{k=1..n1} a(k1)a(nk1).  Henry Bottomley, Feb 22 2005
G.f.: 1/(1xx^2/(1x^2/(1xx^2/(1x^2/(1xx^2/(1x^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) = 2*(2*n5)*a(n4) + (137*n)*a(n3) + (n4)*a(n2) + 3*(n+1)*a(n1), 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>(1sqrt(14*x))/2/x: G:=C(z^2/(1z))/(1z): 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^2n+2)/2,
((2*n+2)*a(n1) (4*n6)*a(n3) +(3*n4)*a(n2))/(n+2))
end:
seq(a(n), n=0..40); # Alois P. Heinz, May 17 2013


MATHEMATICA

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


PROG

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


CROSSREFS

Cf. A001006, A098474, A124497, A124344, A086622.
Sequence in context: A001190 A274937 A199142 * A277795 A198662 A198620
Adjacent sequences: A090341 A090342 A090343 * A090345 A090346 A090347


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Jan 28 2004


STATUS

approved



