|
%I #9 Aug 12 2023 01:09:45
%S 3,21,135,702,3402,15282,65610,270540,1082565,4221639,16120377,
%T 60450138,223205220,813100356,2927177028,10428053400,36804946455,
%U 128817263385,447470664795,1543773631158,5292938720718,18044108743734,61193066237550
%N Number of 4-ary Lyndon words of length n with exactly four 1s.
%H G. C. Greubel, <a href="/A124812/b124812.txt">Table of n, a(n) for n = 5..1005</a>
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (12,-48,36,234,-540,0,972,-729).
%F O.g.f.: 3*x^5*(1 - 5*x + 9*x^2 - 6*x^3)/((1 - 3*x^2)^2*(1 - 3*x)^4).
%F G.f.: (1/4)*( (x/(1-3*x))^4 - x^4/(1-3*x^2)^2 ).
%F a(n) = (1/4)*Sum_{d|4,d|n} mu(d)*C(n/d - 1, (n-4)/d)*3^((n-4)/d).
%F a(n) = (1/4)*C(n-1, 3)*3^(n-4) if n is odd, a(n) = (1/4)*( C(n-1, 3)*3^(n-4) - (n/2-1)*3^((n-4)/2) ) if n is even.
%F a(n) = (3/4)*( 3^(n-5)*binomial(n-1, 3) - ((n-2)/2)*A254006(n-6) ). - _G. C. Greubel_, Aug 09 2023
%e a(6) = 21 because 1111ab, 1111ba, 111a1b, 111b1a, 11a11b for ab = 23, 24, 34 (accounting for 15 words) and 1111aa, 111a1a for a=2,3,4 (accounting for 6 words) are all Lyndon of length 6
%t 3*(1-5*x+9*x^2-6*x^3)/((1-3*x)^4*(1-3*x^2)^2) + O[x]^23 // CoefficientList[#, x]& (* _Jean-François Alcover_, Sep 19 2017 *)
%t LinearRecurrence[{12,-48,36,234,-540,0,972,-729}, {3,21,135,702,3402, 15282,65610,270540}, 41] (* _G. C. Greubel_, Aug 09 2023 *)
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 3*(1-5*x+9*x^2-6*x^3)/((1-3*x)^4*(1-3*x^2)^2) )); // _G. C. Greubel_, Aug 09 2023
%o (SageMath)
%o def A124812(n): return (3/4)*(3^(n-5)*binomial(n-1,3) - ((n-2)//2)*3^((n-6)//2)*((n-5)%2))
%o [A124812(n) for n in range(5,41)] # _G. C. Greubel_, Aug 09 2023
%Y Cf. A006918, A124722, A124810, A124811, A124813, A124814, A254006.
%K nonn
%O 5,1
%A _Mike Zabrocki_, Nov 08 2006
|
