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

3, 18, 89, 405, 1701, 6801, 26244, 98415, 360846, 1299078, 4605822, 16120350, 55801305, 191318760, 650483703, 2195382771, 7360989291, 24536630727, 81358302690, 268482398877, 882156452724, 2887057484028, 9414317882700, 30596533116588, 99132767304831

Offset: 4

Author

Mike Zabrocki, Nov 08 2006

Keywords

• nonn
• easy

Examples

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

Links

• G. C. Greubel, Table of n, a(n) for n = 4..1004
• Index entries for linear recurrences with constant coefficients, signature (9,-27,30,-27,81,-81).

Crossrefs

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

Programs

Magma

R:=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

Mathematica

(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 *)
LinearRecurrence[{9,-27,30,-27,81,-81}, {3,18,89,405,1701,6801}, 41] (* G. C. Greubel, Aug 08 2023 *)

SageMath

def b(n): return (1/2)*(1 + (-1)^(n + (n+1)//3))*3^(n//3)
def A124811(n): return 3^(n-4)*binomial(n-1,2) - b(n-6)
[A124811(n) for n in range(4,41)] # G. C. Greubel, Aug 08 2023

Formula

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

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

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

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

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