login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

P Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6

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

(n+2)*a(n)-(2*n+2)*a(n-1)-(3*n-4)*a(n-2)+(4*n-6)*a(n-3) = 0. - 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) = 2*(2*n-5)*a(n-4) + (13-7*n)*a(n-3) + (n-4)*a(n-2) + 3*(n+1)*a(n-1), 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 04:27 EDT 2017. Contains 292403 sequences.