A105641 Number of hill-free Dyck paths of semilength n, having no UUDD's, where U=(1,1) and D=(1,-1) (a hill in a Dyck path is a peak at level 1).

0, 1, 2, 5, 14, 39, 111, 322, 947, 2818, 8470, 25677, 78420, 241061, 745265, 2315794, 7228702, 22656505, 71273364, 224965675, 712249471, 2261326010, 7197988973, 22966210236, 73437955105, 235307698544, 755395560220, 2429293941019

Offset

2,3

Comments

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

Links

Table of n, a(n) for n=2..29.

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Formula

G.f.: [(1+z)^2-sqrt((1+z^2)^2-4z)]/[2z(2+z+z^2)]-1.

D-finite with recurrence 2*(n+1)*a(n) +(-7*n+5)*a(n-1) +(n-5)*a(n-2) +2*(-n-1)*a(n-3) +2*(2*n-7)*a(n-4) +(n-5)*a(n-5) +(n-5)*a(n-6)=0. - R. J. Mathar, Jul 24 2022

Example

a(4)=2 because we have UUDUDUDD and UUUDUDDD.

Maple

G:=((1+z)^2-sqrt((1+z^2)^2-4*z))/2/z/(2+z+z^2)-1: Gser:=series(G, z=0, 36): seq(coeff(Gser, z^n), n=2..32);

Crossrefs

Cf. A118995.

Sequence in context: A026135 A201778 A367655 * A027035 A102406 A307754

Adjacent sequences: A105638 A105639 A105640 * A105642 A105643 A105644

Keyword

nonn

Author

Emeric Deutsch, May 08 2006

Status

approved