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

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

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

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)(10); \\ Andrew Howroyd, Aug 14 2017
(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

Crossrefs

Cf. A290743, A290744.

Sequence in context: A153194 A175224 A106439 * A121263 A121295 A121296

Adjacent sequences: A290742 A290743 A290744 * A290746 A290747 A290748

Keyword

nonn

Author

N. J. A. Sloane, Aug 11 2017

Extensions

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

Status

approved