A124722 -id:A124722 - 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)

A124721 Number of ternary Lyndon words with exactly three 1's.

Original entry on oeis.org

2, 8, 26, 80, 224, 596, 1536, 3840, 9384, 22528, 53248, 124240, 286720, 655360, 1485472, 3342336, 7471104, 16602432, 36700160, 80740352, 176859776, 385875968, 838860800, 1817531648, 3925868544, 8455716864, 18164132352, 38923141120

Offset: 4

Mike Zabrocki, Nov 05 2006

			a(5) = 8 because 11122, 11212, 11123, 11132, 11213, 11312, 11133, 11313 are all ternary Lyndon words of length 5 with three 1's

Index entries for linear recurrences with constant coefficients, signature (6,-12,10,-12,24,-16).

Cf. A051168, A027376, A124720, A124722, A124723.

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

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.

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

Original entry on oeis.org

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

Mike Zabrocki, Nov 08 2006

nonn

			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

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

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

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

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

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

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

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

A124721 Number of ternary Lyndon words with exactly three 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A124812 Number of 4-ary Lyndon words of length n with exactly four 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