A128721 Number of UUU's in all skew Dyck paths of semilength n.

0, 0, 0, 4, 28, 157, 820, 4155, 20742, 102725, 506504, 2491230, 12236520, 60063399, 294748884, 1446436680, 7099442700, 34855583275, 171187439920, 841084246980, 4134129246180, 20328683526575, 100003531112300, 492153054177155

Offset: 0

Author

Emeric Deutsch, Mar 30 2007

Keywords

• nonn

Comments

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps.

Examples

			a(3)=4 because each of the paths UUUDDD, UUUDLD, UUUDDL and UUUDLL contains one UUU, while the other six paths of semilength 3 contain no UUU's.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..300
• E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Crossrefs

Cf. A128719.

Programs

Maple

G:=(1-5*z+4*z^2-2*z^3-(1-2*z)*sqrt(1-6*z+5*z^2))/2/z/sqrt(1-6*z+5*z^2): Gser:=series(G,z=0,28): seq(coeff(Gser,z,n),n=0..25);

Mathematica

CoefficientList[Series[(2*x*(1-x-Sqrt[1-6*x+5*x^2])/(2*x)-(1-x-Sqrt[1-6*x+5*x^2])/(2*x)+1-x+x^2)/(2*x*(1-x-Sqrt[1-6*x+5*x^2])/(2*x)+x-1), {x, 0, 20}], x] (* Vaclav Kotesovec, Nov 19 2012 *)

Formula

a(n) = Sum_{k=0..n-2} k*A128719(n,k) (n >= 2).

G.f.: (2zg - g + 1 - z + z^2)/(2zg + z - 1), where g = 1 + zg^2 + z(g-1) = (1 - z - sqrt(1 - 6z + 5z^2))/(2z).

Recurrence: 2*(n+1)*(121*n-348)*a(n) = (1663*n^2 - 4620*n + 1392)*a(n-1) - (2476*n^2 - 11133*n + 11787)*a(n-2) + 5*(n-4)*(211*n-537)*a(n-3). - Vaclav Kotesovec, Nov 19 2012

a(n) ~ 9*5^(n-3/2)/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Nov 19 2012