A124721 -id:A124721 - cp's OEIS frontend

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

Mike Zabrocki, Nov 05 2006

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

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

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

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

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

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

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)

A124722 Number of ternary Lyndon words with exactly four 1's.

Original entry on oeis.org

2, 9, 40, 137, 448, 1336, 3840, 10540, 28160, 73168, 186368, 465808, 1146880, 2785024, 6684672, 15875520, 37355520, 87161600, 201850880, 464254208, 1061158912, 2411718656, 5452595200, 12268325888, 27481079808, 61303918592

Offset: 5

Mike Zabrocki, Nov 05 2006

			a(6) = 9 because 111122, 111212, 111123, 111213, 112113, 111132, 111312, 111133, 111313 are all ternary Lyndon words with four 1's

Index entries for linear recurrences with constant coefficients, signature (8,-20,0,76,-96,-32,128,-64).

Cf. A051168, A027376, A124720, A124721, A124723.

LinearRecurrence[{8,-20,0,76,-96,-32,128,-64},{2,9,40,137,448,1336,3840,10540},40] (* Harvey P. Dale, Nov 04 2020 *)

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

A124723 Number of ternary Lyndon words with exactly five 1's.

Original entry on oeis.org

2, 12, 56, 224, 806, 2688, 8448, 25344, 73216, 205004, 559104, 1490944, 3899392, 10027008, 25401752, 63504384, 156893184, 383516672, 928514048, 2228433712, 5305794560, 12540968960, 29444014080, 68702699520, 159390262880

Offset: 6

Mike Zabrocki, Nov 05 2006

nonn

			a(7) = 12 because 11111ab, 1111a1b, 111a11b where ab = 22, 23, 32 or 33 are all ternary Lyndon words of length 7 with five 1's.

Cf. A051168, A027376, A124720, A124721, A124722.

a:= n-> (Matrix([[806, 224, 56, 12, 2, 0$5]]). Matrix(10, (i,j)-> `if`(i=j-1, 1, `if`(j=1, [10, -40, 80, -80, 34, -20, 80, -160, 160, -64] [i], 0)))^(n-10))[1,1]: seq(a(n), n=6..30);  # Alois P. Heinz, Aug 04 2008

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

A124811 Number of 4-ary Lyndon words of length n with exactly three 1s.

Original entry on oeis.org

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

Mike Zabrocki, Nov 08 2006

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

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

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

R:=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

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

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

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

A123223 Triangle read by rows: T(n,k) = number of ternary Lyndon words of length n with exactly k 1's.

Original entry on oeis.org

1, 2, 1, 1, 2, 0, 2, 4, 2, 0, 3, 8, 5, 2, 0, 6, 16, 16, 8, 2, 0, 9, 32, 38, 26, 9, 2, 0, 18, 64, 96, 80, 40, 12, 2, 0, 30, 128, 220, 224, 137, 56, 13, 2, 0, 56, 256, 512, 596, 448, 224, 74, 16, 2, 0, 99, 512, 1144, 1536, 1336, 806, 332, 96, 17, 2, 0, 186, 1024, 2560, 3840, 3840

Offset: 0

Mike Zabrocki, Nov 05 2006

Sum of rows equal to number of ternary Lyndon words A027376 first column (k=0) is equal to the number of binary Lyndon words A001037 third through sixth column (k=2,3,4,5) equal to A124720, A124721, A124722, A124723 T(n+1,n-1) entry equal to A042948.

			Triangle begins:
   1;
   2,  1;
   1,  2,  0;
   2,  4,  2,  0;
   3,  8,  5,  2,  0;
   6, 16, 16,  8,  2,  0;
   9, 32, 38, 26,  9,  2, 0;
  18, 64, 96, 80, 40, 12, 2, 0;
T(n,1) = 2^(n-1) because all words beginning with a 1 and consisting of the rest 2's or 3's are ternary Lyndon words with exactly one 1.

Alois P. Heinz, Rows n = 0..140, flattened.

Cf. A027376, A001037, A124720, A124721, A124722, A124723, A051168, A042948.

G.f. for columns (except for k=0) given by 1/k*Sum_{d|k} mu(d) x^k/(1-2*x^d)^(k/d) T(0,0) = 1 and T(n,0) = 1/n*Sum_{d|n} mu(d)*2^(n/d) T(n,n) = 0 if n>1, T(n,n-1) = 2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A124722 Number of ternary Lyndon words with exactly four 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A124723 Number of ternary Lyndon words with exactly five 1's.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A124811 Number of 4-ary Lyndon words of length n with exactly three 1s.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A123223 Triangle read by rows: T(n,k) = number of ternary Lyndon words of length n with exactly k 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula