A128725 - OEIS

%I #15 Jul 22 2022 13:11:49

%S 1,1,3,9,30,107,399,1537,6069,24434,99924,413943,1733394,7325471,

%T 31203159,133825441,577418430,2504681465,10916208453,47778816718,

%U 209923718880,925537620996,4093530000888,18157477014599,80753894026905

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

%C 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.

%H E. Deutsch, E. Munarini, S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

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

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

%F 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

%F 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

%e 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.

%p 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);

%o (Maxima)

%o 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 */

%o (PARI) C(n,k) = binomial(n,k)

%o 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

%Y Cf. A128724.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Mar 31 2007