A329682 Number of excursions of length n with Motzkin-steps forbidding all consecutive steps of length 2 except UH, UD, HU and DD.

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1

Offset

0

Comments

The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending on the x-axis and never crossing the x-axis, i.e., staying at nonnegative altitude.

This sequence is periodic with a pre-period of length 2 (namely 1, 1) and a period of length 3 (namely 1, 1, 0).

Decimal expansion of 11099/99900. - Elmo R. Oliveira, Jun 16 2024

Links

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

Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Formula

G.f.: (1+t+t^2-t^4)/(1-t^3).

a(n) = a(n-3) for n > 4. - Elmo R. Oliveira, Jun 16 2024

Example

a(6) = 1 because we only have one such excursion of length 6, namely UHUDDD. Similarly a(8) = 1, since only UHUHUDDD is allowed.
More generally, the only possibilities are (HU)^kD^k, U(HU)^(k-1)D^k (aside from trivial cases of length zero or one).

Crossrefs

Cf. A329680, A329683, A329684.

Essentially the same as A204418 and A011655.

Sequence in context: A131218 A174391 A343910 * A113998 A253084 A182741

Adjacent sequences: A329679 A329680 A329681 * A329683 A329684 A329685

Keyword

nonn,walk,easy

Author

Valerie Roitner, Nov 29 2019

Status

approved