A135337 Number of Dyck paths of semilength n with no DUUU's starting at level 1.

1, 1, 2, 5, 13, 36, 105, 320, 1011, 3289, 10957, 37216, 128435, 449142, 1588228, 5669505, 20403322, 73945553, 269647630, 988642372, 3642310793, 13476857235, 50059454347, 186598634398, 697777187275, 2616919372356, 9840647362248

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn

Comments

Column 0 of A135331. - Emeric Deutsch, Dec 14 2007

Examples

			a(4)=13 because among the 14 (=A000108(4)) Dyck paths of semilength 14 only UDUUUDDD does not qualify.
a(4) = 13 since the top row of M^3 = [4, 5, 3, 1, 0, 0, 0, ...] with 13 = (4 + 5 + 3 + 1).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A000108, A135331.

Programs

Maple

a := -2*x+1-sqrt(1-4*x); b := 2*(sqrt(1-4*x)*x+x^2);
series((2*a+b)/(a+b), x=0, 30): seq(coeff(%,x,n), n=0..26); # after V. Kotesovec, Peter Luschny, Mar 20 2014

Mathematica

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

Maxima

a(n):=sum(sum(k*binomial(2*m-k+1,m-k+1)*binomial(n-m-1,n-m-k),k,0,n-m)/(m+1),m,0,n); /* Vladimir Kruchinin, Jan 16 2018 */

PARI

x='x+O('x^25); Vec(1+x*((1-sqrt(1-4*x))/(2*x))^2/(1+x^3*((1-sqrt(1-4*x))/(2*x))^4)) \\ G. C. Greubel, Feb 11 2017

Formula

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

From Gary W. Adamson, Jul 26 2011: (Start)

a(n) = sum of top row terms of M^(n-1), M = an infinite square production matrix as follows, in which a column of [1,1,0,0,0,...] is prepended to an infinite lower triangular matrix of all 1's and the rest zeros:

1, 1, 0, 0, 0, 0, ...

1, 1, 1, 0, 0, 0, ...

0, 1, 1, 1, 0, 0, ...

0, 1, 1, 1, 1, 0, ...

0, 1, 1, 1, 1, 1, ...

... (End)

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

a(n) = A059019(n+1) - A059019(n), n>0. - Philippe Deléham, Oct 02 2014

a(n) = Sum_{m=0..n} 1/(m+1)*Sum_{k=0..n-m} k*C(2*m-k+1,m-k+1)*C(n-m-1,n-m-k). - Vladimir Kruchinin, Jan 16 2018

Extensions

More terms from Emeric Deutsch, Dec 14 2007