A108863 Number of Dyck paths containing exactly one UUUD.

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

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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

a(n) ~ 3^n/2 * (1-5*sqrt(3)/(2*sqrt(Pi*n))). - 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).

Column k=8 of A243827.

Sequence in context: A084780 A268202 A055219 * A027172 A244198 A186244

Adjacent sequences: A108860 A108861 A108862 * A108864 A108865 A108866

Keyword

nonn

Author

David Callan, Jul 25 2005

Status

approved