login
A302483
Number of FF-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths.
0
1, 1, 2, 2, 5, 9, 17, 32, 59, 107, 192, 342, 606, 1070, 1885, 3316, 5828, 10237, 17975, 31555, 55387, 97210, 170605, 299405, 525434, 922088, 1618168, 2839704, 4983351, 8745190, 15346758, 26931703, 47261865, 82938813, 145547493, 255418068, 448227487, 786584431
OFFSET
0,3
COMMENTS
Number of FF-equivalence classes of Łukasiewicz paths. A Łukasiewicz path of length n is a lattice path from (0,0) to (n,0) using up steps U_{k} = (1,k) for any positive integer k, flat steps F = (1,0) and down steps D = (1,-1). Łukasiewicz paths are alpha-equivalent whenever the positions of occurrences of pattern alpha are identical on these paths.
LINKS
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
FORMULA
G.f.: (1 - 3*x + 4*x^2 - 5*x^3 + 7*x^4 - 7*x^5 + 6*x^6 - 3*x^7 + x^8) / ((1-2*x+x^2-x^3) * (1-x)^2).
EXAMPLE
There are 14 Łukasiewicz of length 4 divided in the 5 following FF-equivalence classes: {FFFF}, {FFU_{1}D}, {U_{1}DFF}, {U_{1}FFD}, {FU_{1}DF, FU_{1}FD, FU_{2}DD, U_{1}DU_{1}D, U_{1}FDF, U_{1}U_{1}DD, U_{2}DDF, U_{2}DFD, U_{2}FDD, U_{3}DDD}.
MATHEMATICA
CoefficientList[Series[(1 - 3 x + 4 x^2 - 5 x^3 + 7 x^4 - 7 x^5 + 6 x^6 - 3 x^7 + x^8)/((1 - 2 x + x^2 - x^3) (1 - x)^2), {x, 0, 32}], x] (* Michael De Vlieger, Apr 12 2018 *)
PROG
(PARI) x='x+O('x^99); Vec((1-3*x+4*x^2-5*x^3+7*x^4-7*x^5+6*x^6-3*x^7+x^8)/((1-2*x+x^2-x^3)*(1-x)^2)) \\ Altug Alkan, Apr 12 2018
CROSSREFS
Cf. A001405, A191385, A000045, A005251, A000325, A011782, A001006, A023431, A292460, A004148 enumerates the numbers of P-equivalence classes of Łukasiewicz paths for other values of P.
Sequence in context: A054229 A212812 A214727 * A052969 A002990 A060405
KEYWORD
nonn
AUTHOR
Sergey Kirgizov, Apr 08 2018
STATUS
approved