|
|
A108863
|
|
Number of Dyck paths containing exactly one UUUD.
|
|
2
|
|
|
0, 0, 0, 1, 5, 21, 78, 274, 927, 3061, 9933, 31824, 100972, 317942, 995088, 3099105, 9612735, 29715525, 91595391, 281643480, 864189486, 2646805668, 8093543439, 24713953515, 75370741506, 229604257846, 698754428388, 2124616182139
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
a(n) = number of Dyck n-paths containing exactly one UUUD.
Conjecture: this is the Motzkin transform of the sequence of three zeros followed by A001651. - R. J. Mathar, Dec 11 2008
|
|
LINKS
|
|
|
FORMULA
|
G.f. (x-1+(1-2*x)M)/(x(1-3*x)(1+x*M)) = Sum_{n>=0}a(n)x^n where M = (1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2) is the gf for Motzkin numbers (A001006); satisfies z^3 = (1 + z)(1 - 3z)( (1 - 3z + z^2)G + z^2(1 - 3z)G^2 ).
Recurrence: (n-3)*(n+2)*a(n) = (n+1)*(5*n-14)*a(n-1) - 3*(n-2)*(n-1)*a(n-2) - 9*(n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Mar 22 2014
|
|
EXAMPLE
|
a(4) = 5 because UUUUDDDD, UUUDUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD
each contain one UUUD.
|
|
MATHEMATICA
|
CoefficientList[Series[(x-1+(1-2*x)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))/(x*(1-3*x)*(1+x*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 22 2014 *)
|
|
CROSSREFS
|
Cf. same as A055219 except for offset and is column k=1 of A091958. Dyck paths containing no UUUD are counted by the Motzkin numbers (A001006).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|