A095980 Number of UFU-free Motzkin paths of length n.

1, 1, 2, 4, 9, 20, 47, 112, 274, 679, 1708, 4341, 11143, 28831, 75135, 197013, 519447, 1376256, 3662327, 9784106, 26232033, 70558313, 190348160, 514904151, 1396328313, 3795324358, 10338000693, 28215285901, 77149545999, 211314835549, 579730469034

Offset

0,3

Comments

a(n) = number of Motzkin paths (A001006) of length n that contain no consecutive UFU.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Jean-Luc Baril and José Luis Ramírez, Partial Motzkin paths with air pockets of the first kind avoiding peaks, valleys or double rises, arXiv:2301.10449 [math.CO], 2023.

Formula

G.f.: (1 - x - x^3 - (1 - 2*x - 3*x^2 + 2*x^3 - 2*x^4 + x^6)^(1/2))/(2*x^2*(1 - x + x^2)).

Example

a(5) = 20 because, of the 21 Motzkin paths of length 5, only UFUDD contains an occurrence of UFU.

Mathematica

CoefficientList[Series[(1 - x - x^3 - (1 - 2*x - 3*x^2 + 2*x^3 - 2*x^4 + x^6)^(1/2))/(2*x^2*(1 - x + x^2)), {x, 0, 30}], x] (* Michael De Vlieger, Jan 31 2023 *)

Prog

(PARI) seq(n)={Vec((1 - x - x^3 - (1 - 2*x - 3*x^2 + 2*x^3 - 2*x^4 + x^6 + O(x^3*x^n))^(1/2))/(2*x^2*(1 - x + x^2)))} \\ Andrew Howroyd, Nov 05 2019

Crossrefs

Cf. A001006.

Sequence in context: A213905 A058385 A058386 * A036619 A036620 A036721

Adjacent sequences: A095977 A095978 A095979 * A095981 A095982 A095983

Keyword

nonn

Author

David Callan, Jul 16 2004

Extensions

Terms a(23) and beyond from Andrew Howroyd, Nov 05 2019

Status

approved