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

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

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

Example

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

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

Prog

(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
(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

Crossrefs

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

Sequence in context: A218924 A037295 A290331 * A006568 A181955 A147518

Adjacent sequences: A124808 A124809 A124810 * A124812 A124813 A124814

Keyword

nonn,easy

Author

Mike Zabrocki, Nov 08 2006

Status

approved