A124720 Number of ternary Lyndon words of length n with exactly two 1's.

2, 5, 16, 38, 96, 220, 512, 1144, 2560, 5616, 12288, 26592, 57344, 122816, 262144, 556928, 1179648, 2490112, 5242880, 11009536, 23068672, 48233472, 100663296, 209713152, 436207616, 905965568, 1879048192, 3892305920, 8053063680, 16642981888, 34359738368

Offset

3,1

Comments

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

a(n+2) is the number of distinct unordered pairs of binay words having a total length of n letters: a(2+2) = 5 because we have the unordered pairs: (e,00),(e,01), (e,10), (e,11), (0,1) where e represents the empty word. Each pair has a total of 2 letters and the two elements of each pair are distinct words. - Geoffrey Critzer, Feb 28 2013

Links

Colin Barker, Table of n, a(n) for n = 3..1000

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 (4,-2,-8,8).

Formula

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

From Colin Barker, Oct 28 2016: (Start)

a(n) = 2^(n-3)*(n-1)-2^(n/2-2) for n even.

a(n) = 2^(n-3)*n-2^(n-3) for n odd.

a(n) = 4*a(n-1)-2*a(n-2)-8*a(n-3)+8*a(n-4) for n>6.

(End)

Example

a(4) = 5 because 1122, 1123, 1132, 1213, 1133 are all Lyndon words on 3 letters with 2 ones.

Mathematica

nn=30; Drop[CoefficientList[Series[(1/(1-2x)^2-1/(1-2x^2))/2, {x, 0, nn}], x], 1] (* Geoffrey Critzer, Feb 28 2013 *)

Prog

(PARI) Vec(x^3*(2-3*x)/((1-2*x)^2*(1-2*x^2)) + O(x^40)) \\ Colin Barker, Oct 28 2016

Crossrefs

Cf. A051168, A027376, A124721, A124722, A124723.

Sequence in context: A082085 A179992 A054971 * A188947 A076958 A163825

Adjacent sequences: A124717 A124718 A124719 * A124721 A124722 A124723

Keyword

nonn,easy

Author

Mike Zabrocki, Nov 05 2006

Status

approved