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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A135339 Number of Dyck paths of semilength n having no DUDU's starting at level 1. 4
1, 1, 2, 4, 11, 32, 99, 318, 1051, 3550, 12200, 42520, 149930, 533890, 1917181, 6934722, 25243539, 92405718, 339940116, 1256122632, 4660081434, 17350844808, 64814186646, 242838410652, 912333763806, 3436240272972, 12972454874704, 49078874293528, 186051766180496 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Column 0 of A135333. - Emeric Deutsch, Dec 13 2007

Apparently for n>0 the number of Motzkin paths of length n-1 with two colors of flat step (F,f) and avoiding FF at level 0. e.g for a(3)=4 the paths are UD, ff, fF and Ff. - David Scambler, Jun 27 2013

Number of standard Young tableaux of shape n^2 that avoid the consecutive pattern [12][34][56], read by columns. - Ran Pan, Sep 27 2015

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

FORMULA

G.f.: (2*z*C-z+C)/(1+z*C), where C=(1-sqrt(1-4*z))/(2*z) is the g.f. of the Catalan numbers (A000108). - Emeric Deutsch, Dec 13 2007

a(n) = binomial(2*n-2,n-1)/n + ( Sum_{j=0..n-2} (-1)^j*(j+3)*binomial(2*n-j-2,n) )/(n+1) for n>=1. - Emeric Deutsch, Dec 13 2007

a(n) = A000958(n-1)+A000958(n). - Philippe Deléham, Dec 02 2009

a(n) ~ 25*4^(n-1)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

Conjecture: 2*(n+1)*a(n) +(-5*n+1)*a(n-1) +(-11*n+28)*a(n-2) +2*(-2*n+7)*a(n-3)=0. - R. J. Mathar, Oct 20 2015

EXAMPLE

a(4)=11 because among the 14 (=A000108(4)) Dyck paths of semilength 4 the following paths do not qualify: UDUDUUDD, UUDDUDUD and UDUDUDUD.

MAPLE

G:=(2*z*C-z+C)/(1+z*C): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=series(G, z=0, 30): seq(coeff(Gser, z, n), n=0..25); # Emeric Deutsch, Dec 13 2007

a:= proc (n) options operator, arrow: binomial(2*n-2, n-1)/n+(sum((-1)^j*(j+3)*binomial(2*n-j-2, n), j=0..n-2))/(n+1) end proc: 1, seq(a(n), n=1..25); # Emeric Deutsch, Dec 13 2007

# third Maple program:

a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],

     ((5*n-1)*a(n-1)+(11*n-28)*a(n-2)+(4*n-14)*a(n-3))/(2*n+2))

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Sep 28 2015

MATHEMATICA

CoefficientList[Series[(2*x*(1-Sqrt[1-4*x])/(2*x)-x+(1-Sqrt[1-4*x])/(2*x))/(1+x*(1-Sqrt[1-4*x])/(2*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

CROSSREFS

Cf. A000108, A135333.

Sequence in context: A059305 A191586 A120848 * A148170 A156043 A268322

Adjacent sequences:  A135336 A135337 A135338 * A135340 A135341 A135342

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Dec 07 2007

EXTENSIONS

Edited and extended by Emeric Deutsch, Dec 13 2007

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 26 06:54 EDT 2017. Contains 292502 sequences.