A128740 Number of DD's in all skew Dyck paths of semilength n.

0, 0, 1, 6, 31, 154, 754, 3670, 17824, 86524, 420169, 2041946, 9932959, 48368000, 235769011, 1150413818, 5618786629, 27468246832, 134399280931, 658139933938, 3225323325109, 15817633139722, 77625378841756, 381190465089138

Offset

0,4

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 the path is defined to be the number of its steps.

Links

Robert Israel, Table of n, a(n) for n = 0..1432

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

Formula

a(n) = Sum_{k>=0} k*A128738(n,k).

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

Conjecture: +2*(n+1)*(n^2-5*n+5)*a(n) +(-13*n^3+60*n^2-52*n+15)*a(n-1) +2*(8*n^3-44*n^2+63*n-20)*a(n-2) -5*(n-3)*(n^2-3*n+1)*a(n-3)=0. - R. J. Mathar, Jun 17 2016

Conjecture verified using the differential equation (-12*z^2+10*z+10)*y(z)+(-25*z^4-10*z^3+37*z^2-6*z)*y'(z)+(-30*z^5+56*z^4-18*z^3-2*z^2)*y''(z)+(-5*z^6+16*z^5-13*z^4+2*z^3)*y'''(z)+6*z^2=0 satisfied by the G.f.. - Robert Israel, Dec 25 2017

Example

a(3)=6 because each of the paths UDUUDD, UUDDUD, UUDUDD, UUUDDL contains one DD, the path UUUDDD contains 2 DD's and the paths UDUDUD, UDUUDL, UUUDLD, UUDUDL and UUUDLL contain no DD's.

Maple

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

Crossrefs

Cf. A128738.

Sequence in context: A346226 A240879 A056015 * A227505 A026705 A243874

Adjacent sequences: A128737 A128738 A128739 * A128741 A128742 A128743

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved