A274110 Number of equivalence classes of ballot paths of length n for the string uu.

1, 2, 3, 5, 8, 14, 24, 42, 73, 128, 224, 393, 689, 1209, 2121, 3722, 6531, 11461, 20112, 35294, 61936, 108690, 190737, 334720, 587392, 1030801, 1808929, 3174449, 5570769, 9776018, 17155715, 30106181, 52832664, 92714862, 162703240, 285524282, 501060185, 879299328, 1543062752, 2707886361

Offset

1,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.

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

Formula

G.f.: x*(1-x^2-x^4) / ( (x-1)*(1+x)*(x^3-x^2+2*x-1) ). - R. J. Mathar, Jun 20 2016

a(n) = 2*a(n-1) - a(n-3) + a(n-4) - a(n-5). - Wesley Ivan Hurt, Mar 15 2023

Mathematica

CoefficientList[Series[(1 - x^2 - x^4) / ((x - 1) (1 + x) (x^3 - x^2 + 2 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 18 2016 *)

Prog

(PARI) apply( {A274110(n)=(matcompanion(x^5-2*x^4+x^2-x+1)^n)[5, 3]+1}, [1..44]) \\ M. F. Hasler, Jun 22 2021

Crossrefs

Sequence in context: A340215 A114831 A343161 * A347018 A260403 A127603

Adjacent sequences: A274107 A274108 A274109 * A274111 A274112 A274113

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 17 2016

Status

approved