login
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

%I #21 May 14 2018 18:55:11

%S 1,1,2,2,5,9,17,32,59,107,192,342,606,1070,1885,3316,5828,10237,17975,

%T 31555,55387,97210,170605,299405,525434,922088,1618168,2839704,

%U 4983351,8745190,15346758,26931703,47261865,82938813,145547493,255418068,448227487,786584431

%N Number of FF-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths.

%C 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.

%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.

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

%e 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}.

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

%o (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

%Y 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.

%K nonn

%O 0,3

%A _Sergey Kirgizov_, Apr 08 2018