A124813 Number of 4-ary Lyndon words of length n with exactly five 1s.

3, 27, 189, 1134, 6123, 30618, 144342, 649539, 2814669, 11821608, 48361131, 193444524, 758897748, 2927177028, 11123272701, 41712272649, 154580775111, 566796175407, 2058365058057, 7410114208989, 26464693603590, 93829368230910

Offset: 6

Author

Mike Zabrocki, Nov 08 2006

Keywords

• nonn
• easy

Examples

			a(7) = 27 because 11111ab, 1111a1b, 111a11b for a,b=2,3,4 are all Lyndon of length 7.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 6..1000
• Index entries for linear recurrences with constant coefficients, signature (15,-90,270,-405,246,-45,270,-810,1215,-729).

Crossrefs

Cf. A011795, A124723, A124810, A124811, A124812, A124814.

Programs

Magma

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 3*x^6*(1-6*x+18*x^2-27*x^3+16*x^4)/((1-3*x)^5*(1-3*x^5)) )); // G. C. Greubel, Aug 17 2023

Mathematica

3*(1 -6*x +18*x^2 -27*x^3 +16*x^4)/((1-3*x)^5*(1-3*x^5)) + O[x]^22 // CoefficientList[#, x]& (* Jean-François Alcover, Sep 19 2017 *)

SageMath

def f(x): return 3*x^6*(1-6*x+18*x^2-27*x^3+16*x^4)/((1-3*x)^5*(1-3*x^5))
def A124813_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( f(x) ).list()
a=A124813_list(46); a[6:] # G. C. Greubel, Aug 17 2023

Formula

O.g.f.: 3*x^6*(1 - 6*x + 18*x^2 - 27*x^3 + 16*x^4)/((1 - 3*x)^5*(1 - 3*x^5)).

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

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

a(n) = (1/5)*C(n-1, 4)*3^(n-5) if n=1,2,3,4 mod 5.

a(n) = (1/5)*C(n-1, 4)*3^(n-5) - (1/5)*3^((n-5)/5) if n=0 mod 5.