A089387 Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no UD, UHD, UHHD, UHHHD, ... starting at level zero.

1, 1, 2, 8, 36, 164, 764, 3652, 17852, 88868, 449004, 2296692, 11870316, 61897140, 325239036, 1720415268, 9154052700, 48961321604, 263092909004, 1419630359572, 7689097400588, 41788586179988, 227819374037340, 1245545102522948

Offset

0,3

Links

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

Formula

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

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

Example

Example: a(2)=2 because we have HH and UUDD.

Crossrefs

Cf. A006318.

Sequence in context: A027743 A152124 A147722 * A206902 A275752 A084868

Adjacent sequences: A089384 A089385 A089386 * A089388 A089389 A089390

Keyword

nonn

Author

Emeric Deutsch, Dec 28 2003

Status

approved