|
|
A135336
|
|
Number of Dyck paths of semilength n with no UUDU's starting at level 0.
|
|
2
|
|
|
1, 1, 2, 4, 10, 28, 85, 271, 893, 3013, 10351, 36075, 127219, 453097, 1627378, 5887660, 21436354, 78484402, 288779728, 1067263660, 3960081904, 14746806292, 55094725918, 206450572930, 775724723086, 2922060848734
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{j=0..floor(n/3)} (-1)^j*(3*j+1)*binomial(2*n-3*j,n)/(n+1).
G.f.: C/(1+z^3*C^3) = C/[(1-z)*(1+z*C)], where C = [1-sqrt(1-4*z)]/(2*z) is the g.f. of the Catalan numbers (A000108). (End)
|
|
EXAMPLE
|
a(3)=4 because among the 5 (=A000108(3)) Dyck paths of semilength 3 only UUDUDD does not qualify.
|
|
MAPLE
|
a:=proc(n) options operator, arrow: (sum((-1)^j*(3*j+1)*binomial(2*n-3*j, n), j =0..floor((1/3)*n)))/(n+1) end proc: seq(a(n), n=0..25); # Emeric Deutsch, Dec 14 2007
|
|
MATHEMATICA
|
CoefficientList[Series[(1-Sqrt[1-4*x])/(2*x)/((1-x)*(1+x*(1-Sqrt[1-4*x])/(2*x))), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)
|
|
PROG
|
(PARI) x='x+O('x^50); Vec((1-sqrt(1-4*x))/(x*(1-x)*(3 - sqrt(1-4*x)))) \\ G. C. Greubel, Mar 21 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|