A290745 Maximum number of distinct Lyndon factors that can appear in words of length n over an alphabet of size 10.

10, 11, 13, 16, 20, 25, 31, 38, 46, 55, 64, 74, 85, 97, 110, 124, 139, 155, 172, 190, 208, 227, 247, 268, 290, 313, 337, 362, 388, 415, 442, 470, 499, 529, 560, 592, 625, 659, 694, 730, 766, 803, 841, 880, 920, 961, 1003, 1046, 1090, 1135

Offset: 1

Author

N. J. A. Sloane, Aug 11 2017

Keywords

• nonn

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

Crossrefs

Cf. A290743, A290744.

Programs

Magma

[Binomial(n+1,2)-(10-(n-10*Floor(n/10)))*Binomial(Floor(n/10)+1,2)-(n-10*Floor(n/10))*Binomial(Floor(n/10)+2,2)+ 10: n in [1..50]]; // Vincenzo Librandi, Oct 04 2017

Mathematica

Table[(Binomial[n+1, 2] - (10 - (n-10 Floor[n/10])) Binomial[Floor[n/10]+1, 2]- (n-10 Floor[n/10]) Binomial[Floor[n/10]+2, 2]+10), {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)(10); \\ 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=10, m=floor(n/s), p=n-m*s. - Andrew Howroyd, Aug 14 2017

G.f.: x*(10 - 9*x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 - 10*x^10 + 10*x^11) / ((1 - x)^3*(1 + x)*(1 - x + x^2 - x^3 + x^4)*(1 + x + x^2 + x^3 + x^4)) (conjectured). - Colin Barker, Oct 03 2017

Extensions

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