A128729 Number of skew Dyck paths of semilength n with no UDL's.

1, 1, 2, 6, 20, 71, 262, 994, 3852, 15183, 60686, 245412, 1002344, 4129012, 17135432, 71575350, 300690836, 1269662127, 5385593406, 22938095326, 98059308676, 420610907183, 1809690341366, 7808145901068, 33776362530776

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, and S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Helmut Prodinger, Skew Dyck paths without up-down-left, arXiv:2203.10516 [math.CO], 2022.

Formula

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

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

D-finite with recurrence 4*n*(n+1)*a(n) -32*n*(n-1)*a(n-1) +3*(23*n^2-78*n+59)*a(n-2) -2*(n-3)*(10*n-47)*a(n-3) -44*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 22 2022

Example

a(2)=2 because we have UDUD and UUDD (UUDL does not qualify).

Maple

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

Crossrefs

Cf. A128728.

Sequence in context: A129777 A108600 A274484 * A006027 A049124 A275756

Adjacent sequences: A128726 A128727 A128728 * A128730 A128731 A128732

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved