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,1

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).

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.

Example

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

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 *)

Prog

(Magma) R<x>:=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
(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.<x> = PowerSeriesRing(ZZ, prec)
    return P( f(x) ).list()
a=A124813_list(46); a[6:] # G. C. Greubel, Aug 17 2023

Crossrefs

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

Sequence in context: A241271 A222015 A127215 * A127220 A127222 A248225

Adjacent sequences: A124810 A124811 A124812 * A124814 A124815 A124816

Keyword

nonn

Author

Mike Zabrocki, Nov 08 2006

Status

approved