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,1

Comments

See theorem 1 of reference for formula.

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

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

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

Prog

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

Crossrefs

Cf. A290744, A290745, A290746, A014206 (bisection), A059100 (bisection).

Sequence in context: A211536 A071764 A238381 * A059291 A177339 A075535

Adjacent sequences: A290740 A290741 A290742 * A290744 A290745 A290746

Keyword

nonn,easy

Author

N. J. A. Sloane, Aug 11 2017

Extensions

a(11)-a(55) from Andrew Howroyd, Aug 14 2017

Status

approved