|
%I #40 Sep 16 2022 03:55:39
%S 2,3,4,6,8,11,14,18,22,27,32,38,44,51,58,66,74,83,92,102,112,123,134,
%T 146,158,171,184,198,212,227,242,258,274,291,308,326,344,363,382,402,
%U 422,443,464,486,508,531,554,578,602,627,652,678,704,731,758
%N Maximum number of distinct Lyndon factors that can appear in words of length n over an alphabet of size 2.
%C See theorem 1 of reference for formula.
%H Vincenzo Librandi, <a href="/A290743/b290743.txt">Table of n, a(n) for n = 1..1000</a>
%H Amy Glen, Jamie Simpson, and W. F. Smyth, <a href="https://doi.org/10.37236/6915">Counting Lyndon Factors</a>, Electronic Journal of Combinatorics 24(3) (2017), #P3.28.
%H Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, <a href="https://arxiv.org/abs/2106.01190">Counting Lyndon Subsequences</a>, arXiv:2106.01190 [math.CO], 2021. See MDF(n, s).
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,1).
%F 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
%F From _Colin Barker_, Oct 03 2017: (Start)
%F G.f.: x*(2 - x - 2*x^2 + 2*x^3) / ((1 - x)^3*(1 + x)).
%F a(n) = (2*n^2 + 16) / 8 for n even.
%F a(n) = (2*n^2 + 14) / 8 for n odd.
%F a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 4. (End)
%F E.g.f.: ((8 + x + x^2)*cosh(x) + (7 + x + x^2)*sinh(x) - 8)/4. - _Stefano Spezia_, Jul 06 2021
%F 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
%t 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 *)
%o (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
%o (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
%Y Cf. A290744, A290745, A290746, A014206 (bisection), A059100 (bisection).
%K nonn,easy
%O 1,1
%A _N. J. A. Sloane_, Aug 11 2017
%E a(11)-a(55) from _Andrew Howroyd_, Aug 14 2017
|
