login
A135337
Number of Dyck paths of semilength n with no DUUU's starting at level 1.
3
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,3
COMMENTS
Column 0 of A135331. - Emeric Deutsch, Dec 14 2007
LINKS
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
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
EXAMPLE
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).
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 *)
PROG
(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
(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 */
CROSSREFS
Sequence in context: A271941 A114465 A135310 * A133365 A370886 A135335
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 07 2007
EXTENSIONS
More terms from Emeric Deutsch, Dec 14 2007
STATUS
approved