login
A135310
Number of Dyck paths of semilength n having no UUUU's starting at level 0.
2
1, 1, 2, 5, 13, 36, 105, 319, 1002, 3235, 10685, 35970, 123045, 426667, 1496782, 5303623, 18956417, 68270576, 247518777, 902708185, 3309559838, 12190954231, 45096739797, 167462013888, 624019924009, 2332697899665
OFFSET
0,3
COMMENTS
Column 0 of A135309. - Emeric Deutsch, Dec 15 2007
LINKS
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
FORMULA
From Emeric Deutsch, Dec 15 2007: (Start)
a(n) = Sum_{j=0..floor(n/4)} (-1)^(j)*(5j+1)*binomial(2n-3j,n+j)/(n+j+1).
G.f.: C/(1+z^4*C^5), where C=(1-sqrt(1-4z))/(2z) is the g.f. of the Catalan numbers (A000108). (End)
a(n) = the upper left term in M^n, M = the following production matrix in which a column of (1,1,1,0,0,0,...) is prepended to an infinite lower triangular matrix with all 1's and the rest zeros:
1, 1, 0, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, 0, ...
0, 1, 1, 1, 1, 0, 0, ...
0, 1, 1, 1, 1, 1, 0, ...
0, 1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 11 2011
a(n) ~ 2^(2*n+5)/(81*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
EXAMPLE
a(4)=13 because among the 14 (=A000108(4)) Dyck paths of semilength 4 only UUUUDDDD does not qualify.
MAPLE
a:=proc(n) options operator, arrow: sum((-1)^j*(5*j+1)*binomial(2*n-3*j, n+j)/(n+j+1), j=0..floor((1/4)*n)) end proc: seq(a(n), n=0..25); # Emeric Deutsch, Dec 15 2007
MATHEMATICA
CoefficientList[Series[(1-Sqrt[1-4*x])/(2*x)/(1+x^4*((1-Sqrt[1-4*x])/(2*x))^5), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)
PROG
(PARI) x='x+O('x^50); Vec((1-sqrt(1-4*x))/(2*x)/(1+x^4*((1-sqrt(1-4*x))/(2*x))^5)) \\ G. C. Greubel, Mar 21 2017
CROSSREFS
Sequence in context: A125094 A271941 A114465 * A135337 A133365 A370886
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Dec 07 2007
EXTENSIONS
More terms from Emeric Deutsch, Dec 15 2007
STATUS
approved