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

Author

Mike Zabrocki, Nov 05 2006

Keywords

• nonn
• easy

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

Examples

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

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

Crossrefs

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

Programs

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

PARI

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

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)