A124812 Number of 4-ary Lyndon words of length n with exactly four 1s.

3, 21, 135, 702, 3402, 15282, 65610, 270540, 1082565, 4221639, 16120377, 60450138, 223205220, 813100356, 2927177028, 10428053400, 36804946455, 128817263385, 447470664795, 1543773631158, 5292938720718, 18044108743734, 61193066237550

Offset

5,1

Links

G. C. Greubel, Table of n, a(n) for n = 5..1005

Index entries for linear recurrences with constant coefficients, signature (12,-48,36,234,-540,0,972,-729).

Formula

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

G.f.: (1/4)*( (x/(1-3*x))^4 - x^4/(1-3*x^2)^2 ).

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

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.

a(n) = (3/4)*( 3^(n-5)*binomial(n-1, 3) - ((n-2)/2)*A254006(n-6) ). - G. C. Greubel, Aug 09 2023

Example

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

Mathematica

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 *)
LinearRecurrence[{12, -48, 36, 234, -540, 0, 972, -729}, {3, 21, 135, 702, 3402, 15282, 65610, 270540}, 41] (* G. C. Greubel, Aug 09 2023 *)

Prog

(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
(SageMath)
def A124812(n): return (3/4)*(3^(n-5)*binomial(n-1, 3) - ((n-2)//2)*3^((n-6)//2)*((n-5)%2))
[A124812(n) for n in range(5, 41)] # G. C. Greubel, Aug 09 2023

Crossrefs

Cf. A006918, A124722, A124810, A124811, A124813, A124814, A254006.

Sequence in context: A274586 A333030 A125701 * A141041 A079753 A346935

Adjacent sequences: A124809 A124810 A124811 * A124813 A124814 A124815

Keyword

nonn

Author

Mike Zabrocki, Nov 08 2006

Status

approved