A290743 Maximum number of distinct Lyndon factors that can appear in words of length n over an alphabet of size 2.
2, 3, 4, 6, 8, 11, 14, 18, 22, 27, 32, 38, 44, 51, 58, 66, 74, 83, 92, 102, 112, 123, 134, 146, 158, 171, 184, 198, 212, 227, 242, 258, 274, 291, 308, 326, 344, 363, 382, 402, 422, 443, 464, 486, 508, 531, 554, 578, 602, 627, 652, 678, 704, 731, 758
Offset: 1
Links
- Vincenzo Librandi, Table of n, a(n) for n = 1..1000
- Amy Glen, Jamie Simpson, and W. F. Smyth, Counting Lyndon Factors, Electronic Journal of Combinatorics 24(3) (2017), #P3.28.
- Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, Counting Lyndon Subsequences, arXiv:2106.01190 [math.CO], 2021. See MDF(n, s).
- Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
Programs
-
Magma
[Binomial(n+1,2)-(2-(n-2*Floor(n/2)))*Binomial(Floor(n/2)+1,2)-(n-2*Floor(n/2))*Binomial(Floor(n/2)+2,2)+2: n in [1..60]]; // Vincenzo Librandi, Oct 04 2017
-
Mathematica
Table[(Binomial[n+1,2] - (2-(n - 2 Floor[n/2])) Binomial[Floor[n/2]+1, 2] - (n-2 Floor[n/2]) Binomial[Floor[n/2]+2, 2] + 2), {n, 60}] (* Vincenzo Librandi, Oct 04 2017 *) -
PARI
a(n)=(s->my(m=n\s,p=n%s); binomial(n+1,2)-(s-p)*binomial(m+1,2)-p*binomial(m+2,2)+s)(2); \\ Andrew Howroyd, Aug 14 2017
Formula
a(n) = binomial(n+1,2) - (s-p)*binomial(m+1,2) - p*binomial(m+2,2) + s where s=2, m=floor(n/s), p=n-m*s. - Andrew Howroyd, Aug 14 2017
From Colin Barker, Oct 03 2017: (Start)
G.f.: x*(2 - x - 2*x^2 + 2*x^3) / ((1 - x)^3*(1 + x)).
a(n) = (2*n^2 + 16) / 8 for n even.
a(n) = (2*n^2 + 14) / 8 for n odd.
a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 4. (End)
E.g.f.: ((8 + x + x^2)*cosh(x) + (7 + x + x^2)*sinh(x) - 8)/4. - Stefano Spezia, Jul 06 2021
Sum_{n>=1} 1/a(n) = coth(sqrt(2)*Pi)*Pi/(2*sqrt(2)) + tanh(sqrt(7)*Pi/2)*Pi/sqrt(7) - 1/4. - Amiram Eldar, Sep 16 2022
Extensions
a(11)-a(55) from Andrew Howroyd, Aug 14 2017
Comments