A128725 Number of skew Dyck paths of semilength n having no LL's.

1, 1, 3, 9, 30, 107, 399, 1537, 6069, 24434, 99924, 413943, 1733394, 7325471, 31203159, 133825441, 577418430, 2504681465, 10916208453, 47778816718, 209923718880, 925537620996, 4093530000888, 18157477014599, 80753894026905

Offset

0,3

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

Table of n, a(n) for n=0..24.

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

Formula

a(n) = A128724(n,0).

G.f.: G = G(z) satisfies z^2*G^3 - 2zG^2 + (1 + z - z^2)G - 1 = 0.

a(n) = (1/n)*Sum_{j=0..n+1} C(n,j)*Sum_{i=0..n-j+1} C(i,n-j-i+1)*C(j+i-1,i), a(0)=1. - Vladimir Kruchinin, Apr 02 2019

D-finite with recurrence 25*n*(n+1)*a(n) -30*n*(5*n-4)*a(n-1) +6*(4*n-5)*(6*n-11)*a(n-2) +6*(2*n^2-49*n+117)*a(n-3) +4*(19*n^2-110*n+141)*a(n-4) +24*(n-5)*(n-6)*a(n-5) -16*(n-5)*(n-6)*a(n-6)=0. - R. J. Mathar, Jul 22 2022

Example

a(2)=3 because we have UDUD, UUDD and UUDL; a(3)=9 because among the 10 skew Dyck paths of semilength 3 only UUUDLL does not qualify.

Maple

eq:=z^2*G^3-2*z*G^2+(1+z-z^2)*G-1=0: G:=RootOf(eq, G): Gser:=series(G, z=0, 30): seq(coeff(Gser, z, n), n=0..27);

Prog

(Maxima)
a(n):=if n=0 then 1 else sum((sum(binomial(i, n-j-i+1)*binomial(j+i-1, i), i, 0, n-j+1))*binomial(n, j), j, 0, n+1)/n; /* Vladimir Kruchinin, Apr 02 2019 */
(PARI) C(n, k) = binomial(n, k)
a(n) = if (n==0, 1, 1/n*sum(j=0, n+1, C(n, j)*sum(i=0, n-j+1, C(i, n-j-i+1)*C(j+i-1, i)))); \\ Michel Marcus, Apr 01 2019

Crossrefs

Cf. A128724.

Sequence in context: A216454 A053022 A369440 * A099783 A200074 A032125

Adjacent sequences: A128722 A128723 A128724 * A128726 A128727 A128728

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved