A124810 Number of 4-ary Lyndon words of length n with exactly two 1s.

3, 12, 54, 198, 729, 2538, 8748, 29484, 98415, 324648, 1062882, 3454002, 11160261, 35871174, 114791256, 365893848, 1162261467, 3680484804, 11622614670, 36611206686, 115063885233, 360882096930, 1129718145924, 3530368940292

Offset

3,1

Comments

If the offsets are modified, A124810 to A124813 are the 2nd to 5th Witt transform of A000244 [Moree]. - R. J. Mathar, Nov 08 2008

Links

Table of n, a(n) for n=3..26.

Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. [From R. J. Mathar, Nov 08 2008]

Index entries for linear recurrences with constant coefficients, signature (6, -6, -18, 27).

Formula

O.g.f.: 3 x^3 (1-2 x)/((1-3x)^2 (1-3x^2)) = 1/2*((x/(1-3*x))^2 - x^2/(1-3*x^2)) a(n) = 1/2*sum_{d|2,d|n} mu(d) C(n/d-1,(n-2)/d )*3^((n-2)/d) =1/2*(n-1)*3^(n-2) if n is odd =1/2*(n-1)*3^(n-2) - 1/2*3^((n-2)/2) if n is even.

Example

a(4) = 12 because 1122, 1123, 1124, 1132, 1133, 1134, 1142, 1143, 1144, 1213, 1214, 1314 are all 4-ary Lyndon words with length 4 and have exactly two 1s.

Maple

a:= n-> (Matrix([[12, 3, 0, 0]]). Matrix(4, (i, j)-> if (i=j-1) then 1 elif j=1 then [6, -6, -18, 27][i] else 0 fi)^(n-4))[1, 1]: seq(a(n), n=3..26); # Alois P. Heinz, Aug 04 2008

Mathematica

a[n_] := (1/2)*(n-1)*3^(n-2) - If[OddQ[n], 0, (1/2)*3^((n-2)/2)];
Array[a, 24, 3] (* Jean-François Alcover, Sep 19 2017 *)

Crossrefs

Cf. A124811, A124812, A124813, A124814, A004526, A124720.

Sequence in context: A306525 A293131 A120983 * A370821 A329056 A191577

Adjacent sequences: A124807 A124808 A124809 * A124811 A124812 A124813

Keyword

nonn

Author

Mike Zabrocki, Nov 08 2006

Status

approved