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

Author

David Callan, Jul 25 2005

Keywords

• nonn

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

Examples

			a(4) = 5 because UUUUDDDD, UUUDUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD
each contain one UUUD.
		

Links

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

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.

Programs

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 *)

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