login
Number of 4-ary Lyndon words of length n with exactly three 1s.
5

%I #21 Aug 12 2023 01:09:34

%S 3,18,89,405,1701,6801,26244,98415,360846,1299078,4605822,16120350,

%T 55801305,191318760,650483703,2195382771,7360989291,24536630727,

%U 81358302690,268482398877,882156452724,2887057484028,9414317882700,30596533116588,99132767304831

%N Number of 4-ary Lyndon words of length n with exactly three 1s.

%H G. C. Greubel, <a href="/A124811/b124811.txt">Table of n, a(n) for n = 4..1004</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (9,-27,30,-27,81,-81).

%F O.g.f.: x^4*(3-9*x+8*x^2)/((1-3*x)^3*(1-3*x^3)).

%F O.g.f.: (1/3)*((x/(1-3*x))^3 - x^3/(1-3*x^3)).

%F a(n) = (1/3)*Sum_{d|3, d|n} mu(d) C(n/d-1,(n-3)/d)*3^((n-3)/d).

%F a(n) = 3^(n/3-2)*(binomial(n-1, 2)*3^(2*n/3-2) - 1 + (n^2 mod 3)).

%F a(n) = 3^(n-4)*binomial(n-1, 2) - b(n-6), where b(n) = A079978(n)*3^floor(n/3). - _G. C. Greubel_, Aug 08 2023

%e a(5) = 18 because 111ab and 11a1b are Lyndon of length 4 for ab=2,3,4.

%t (3-9*x+8*x^2)/((1-3*x)^3*(1-3*x^3)) + O[x]^23//CoefficientList[#, x]& (* _Jean-François Alcover_, Sep 19 2017 *)

%t LinearRecurrence[{9,-27,30,-27,81,-81}, {3,18,89,405,1701,6801}, 41] (* _G. C. Greubel_, Aug 08 2023 *)

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( x^4*(3-9*x+8*x^2)/((1-3*x)^3*(1-3*x^3)) )); // _G. C. Greubel_, Aug 08 2023

%o (SageMath)

%o def b(n): return (1/2)*(1 + (-1)^(n + (n+1)//3))*3^(n//3)

%o def A124811(n): return 3^(n-4)*binomial(n-1,2) - b(n-6)

%o [A124811(n) for n in range(4,41)] # _G. C. Greubel_, Aug 08 2023

%Y Cf. A079978, A124810, A124812, A124813, A124814, A001840, A124721.

%K nonn,easy

%O 4,1

%A _Mike Zabrocki_, Nov 08 2006