A166289 Number of Dyck paths with no UUU's and no DDD's, of semilength n and having no UDUD's (U=(1,1), D=(1,-1)).

1, 1, 1, 2, 2, 4, 6, 9, 17, 26, 46, 81, 135, 246, 428, 757, 1373, 2431, 4411, 7990, 14434, 26423, 48137, 88144, 162086, 297662, 549342, 1014677, 1876551, 3480596, 6458974, 12008923, 22361683, 41675773, 77797373, 145368548, 271917704

Offset

0,4

Comments

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

Links

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

Andrei Asinowski, Cyril Banderier, Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).

Formula

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

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

Example

a(5)=4 because we have UDUUDDUUDD, UUDDUDUUDD, UUDDUUDDUD, and UUDUUDDUDD.

Maple

F := RootOf(z^3*G^2-(1-z)*(1+z)^2*G+(1+z)^2, G): Fser := series(F, z = 0, 40): seq(coeff(Fser, z, n), n = 0 .. 36);

Crossrefs

Cf. A166288.

Sequence in context: A018061 A304778 A173495 * A071058 A076178 A347693

Adjacent sequences: A166286 A166287 A166288 * A166290 A166291 A166292

Keyword

nonn

Author

Emeric Deutsch, Oct 12 2009

Status

approved