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

Author

N. J. A. Sloane, Jun 17 2016

Keywords

• nonn
• easy

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).

Programs

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 *)

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

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