A128726 Number of LL's in all skew Dyck paths of semilength n.

0, 0, 0, 1, 7, 38, 192, 946, 4616, 22440, 108964, 529133, 2571079, 12504038, 60872038, 296641049, 1447054867, 7065841496, 34534088328, 168933369259, 827073303197, 4052396628306, 19870029768028, 97495408609784

Offset

0,5

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 steps in it.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Formula

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

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

a(n) ~ 5^(n-1/2)/(6*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014

Conjecture: +2*n*(n-3)^2*a(n) +(-13*n^3+84*n^2-167*n+100)*a(n-1) +(n-2)*(16*n^2-77*n+85)*a(n-2) -5*(n-3)*(n-2)^2*a(n-3)=0. - R. J. Mathar, Jun 17 2016

Example

a(4)=7 because we have UDUUUDLL, UUUUDLLD, UUDUUDLL, UUUDUDLL, UUUUDDLL and UUUUDLLL (last path has two LL's).

Maple

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

Mathematica

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

Crossrefs

Cf. A128724.

Sequence in context: A037696 A026895 A037605 * A346395 A055146 A014827

Adjacent sequences: A128723 A128724 A128725 * A128727 A128728 A128729

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved