A054660 -id:A054660 - cp's OEIS frontend

A027377 Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras.

1, 4, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220, 19172790, 71582716, 268431360, 1010580540, 3817733920, 14467258260, 54975528948, 209430785460, 799644629550, 3059510616420

Offset: 0

N. J. A. Sloane

Apart from initial terms, exponents in expansion of A065419 as a product zeta(n)^(-a(n)).

Number of aperiodic necklaces with n beads of 4 colors. - Herbert Kociemba, Nov 25 2016

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..1666 (terms 0..200 from T. D. Noe)
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
A. Pakapongpun and T. Ward, Functorial Orbit counting, JIS 12 (2009) 09.2.4, example 3.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Cf. A001037, A027376, A054719, A054660, A054661.

Column k=4 of A074650.

A027377 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*4^(n/d); od; RETURN(s/n); fi; end;

a[n_] := Sum[MoebiusMu[d]*4^(n/d), {d, Divisors[n]}] / n; a[0] = 1; Table[a[n], {n, 0, 23}](* Jean-François Alcover, Nov 29 2011 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,4],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n)=if(n,sumdiv(n,d,moebius(d)<<(2*n/d))/n,1) \\ Charles R Greathouse IV, Nov 29 2011

a(n) = Sum_{d|n} mu(d)*4^(n/d)/n.
G.f.: k=4, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016
a(n) = A054661(n) + 3 * A054660(n). - Andrey Zabolotskiy, Dec 17 2020
a(n) = 2 * (A054664(n) + A054660(n)). - Andrey Zabolotskiy, Dec 19 2020
a(n) = A054719(n)/n, n>0. - R. J. Mathar, Dec 16 2024

A054661 Number of monic irreducible polynomials over GF(4) with zero trace.

Original entry on oeis.org

1, 0, 5, 12, 51, 160, 585, 2016, 7280, 26112, 95325, 349180, 1290555, 4792320, 17895679, 67104768, 252645135, 954422560, 3616814565, 13743842916, 52357696365, 199911014400, 764877654105, 2932030307680, 11258999068416

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of Lyndon words of length n with trace 0 over GF(4).

F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of Lyndon words over GF(q) with given trace

Cf. A000048, A051841, A046211, A046209, A054660, A074031, A074032, A074446, A074447.

From Andrey Zabolotskiy, Dec 17 2020: (Start)
a(n) = A074031(n) + 3 * A074032(n).
a(n) = A074446(n) + 3 * A074447(n). (End)

More terms from James Sellers, Apr 19 2000

A074450 Let x = RootOf(z^2 + z + 1) and y = 1+x. Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace x.

Original entry on oeis.org

0, 0, 1, 4, 12, 40, 144, 512, 1813, 6528, 23808, 87380, 322560, 1198080, 4473647, 16777216, 63160320, 238605640, 904200192, 3435973836, 13089411609, 49977753600, 191219367936, 733007751680, 2814749599332, 10825959997440, 41699995927744, 160842843834660, 621186153185280

Offset: 1

Frank Ruskey and Nate Kube, Aug 23 2002

nonn

Also the number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace y. Also the number of 4-ary Lyndon words of length n over GF(4) with trace x and subtrace 1. Also the number of 4-ary Lyndon words of length n over GF(4) with trace x and subtrace x. Also the number of 4-ary Lyndon words of length n over GF(4) with trace y and subtrace 1. Also the number of 4-ary Lyndon words of length n over GF(4) with trace y and subtrace y.

Is this a duplicate of A074032? - R. J. Mathar, Dec 15 2020

Frank Ruskey, 4-ary Lyndon words with given trace and subtrace over GF(4)

Cf. A074446, A074447, A074448, A074449.

Cf. A054660, A073995, A073996, A073997, A073998, A073999.

Terms a(16) and beyond from Andrey Zabolotskiy, Jul 21 2021

A074448 Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace 0.

Original entry on oeis.org

1, 1, 1, 4, 15, 45, 144, 512, 1841, 6579, 23808, 87380, 322875, 1198665, 4473647, 16777216, 63164175, 238612920, 904200192, 3435973836, 13089461538, 49977848925, 191219367936, 733007751680, 2814750270420, 10825961287995, 41699995927744, 160842843834660, 621186162441675

Offset: 1

Frank Ruskey and Nate Kube, Aug 23 2002

nonn

Let x = RootOf(z^2 + z + 1) and y = 1 + x. Also the number of 4-ary Lyndon words of length n over GF(4) with trace x and subtrace 0. Also the number of 4-ary Lyndon words of length n over GF(4) with trace y and subtrace 0.

F. Ruskey, 4-ary Lyndon words with given trace and subtrace over GF(4)

Cf. A074446, A074447, A074449, A074450.

Cf. A054660, A073995, A073996, A073997, A073998, A073999.

Terms a(16) and beyond from Andrey Zabolotskiy, Jul 21 2021

A074449 Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace 1.

Original entry on oeis.org

0, 1, 2, 4, 12, 45, 153, 512, 1813, 6579, 23901, 87380, 322560, 1198665, 4474738, 16777216, 63160320, 238612920, 904213989, 3435973836, 13089411609, 49977848925, 191219550297, 733007751680, 2814749599332, 10825961287995, 41699998413248, 160842843834660, 621186153185280

Offset: 1

Frank Ruskey and Nate Kube, Aug 23 2002

nonn

Let x = RootOf( z^2+z+1 ) and y = 1+x. Also the number of 4-ary Lyndon words of length n over GF(4) with trace x and subtrace y. Also the number of 4-ary Lyndon words of length n over GF(4) with trace y and subtrace x.

			Let x = RootOf( z^2+z+1 ) and y = 1+x. a(2; y,x)=1 since the one 4-ary Lyndon word of trace y, subtrace x and length 2 is { 1x }.

F. Ruskey, 4-ary Lyndon words with given trace and subtrace over GF(4)

Cf. A074446, A074447, A074448, A074450.

Cf. A054660, A073995, A073996, A073997, A073998, A073999.

Terms a(16) and beyond from Andrey Zabolotskiy, Jul 21 2021

A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 3, 2, 1, 0, 3, 6, 5, 2, 1, 0, 5, 16, 16, 8, 3, 1, 0, 9, 39, 51, 30, 12, 3, 1, 0, 16, 104, 170, 125, 54, 16, 4, 1, 0, 28, 270, 585, 516, 259, 84, 21, 4, 1, 0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1, 0, 93, 1960, 7280, 9750, 6665, 2792, 819, 180, 33, 5, 1

Offset: 1

Paul Barry, Jul 25 2005

An invertible number triangle related to Lyndon words of trace 1.

			Rows begin
  1;
  0,  1;
  0,  1,   1;
  0,  1,   1,    1;
  0,  2,   3,    2,    1;
  0,  3,   6,    5,    2,    1;
  0,  5,  16,   16,    8,    3,   1;
  0,  9,  39,   51,   30,   12,   3,   1;
  0, 16, 104,  170,  125,   54,  16,   4,  1;
  0, 28, 270,  585,  516,  259,  84,  21,  4, 1;
  0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
Frank Ruskey, Number of Lyndon words over GF(q) with given trace

Columns include A000048, A046211, A054660, A054662, A054666, A373277, A300674, A300675.

T[n_, k_]:=Sum[Boole[GCD[d, k] == 1]  MoebiusMu[d] k^((n - k + 1)/d), {d, Divisors[n - k + 1]}] /(k(n - k + 1)); Flatten[Table[T[n, k], {n, 12}, {k, n}]] (* Indranil Ghosh, Mar 27 2017 *)

for(n=1, 11, for(k=1, n, print1( sum(d=1,n-k+1, if(Mod(n-k+1, d)==0 && gcd(d, k)==1, moebius(d)*k^((n-k+1)/d), 0)/(k*(n-k+1)) ),", ");); print();) \\ Andrew Howroyd, Mar 26 2017

T(n, k) = (Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).

Name clarified by Andrew Howroyd, Mar 26 2017

A300628 Triangular array T(n,k) giving coefficients in expansion of Product_{j=1..n} (1+x^j)^2 mod x^(n+1)-1.

Original entry on oeis.org

1, 2, 2, 6, 5, 5, 16, 16, 16, 16, 52, 51, 51, 51, 51, 172, 170, 170, 172, 170, 170, 586, 585, 585, 585, 585, 585, 585, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 7286, 7280, 7280, 7285, 7280, 7280, 7285, 7280, 7280, 26216, 26214, 26214, 26214, 26214, 26216, 26214, 26214, 26214, 26214

Offset: 0

Seiichi Manyama, Mar 10 2018

			Triangle begins:               A053633
  k  0    1    2    3    4   |  k  0    1    2    3    4    5    6    7    8    9
n                            |n
0    1;                      |1    1,   1;
1    2,   2;                 |3    2,   2,   2,   2;
2    6,   5,   5;            |5    6,   5,   5,   6,   5,   5;
3   16,  16,  16,  16;       |7   16,  16,  16,  16,  16,  16,  16,  16;
4   52,  51,  51,  51,  51;  |9   52,  51,  51,  51,  51,  52,  51,  51,  51,  51;
    ...                      |    ...

Seiichi Manyama, Rows n = 0..139, flattened

Cf. A053633, A054660, A298983.

T(n,k) = polcoeff(prod(j=1, n, (1+x^j)^2) % (x^(n+1) - 1), k);
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Mar 10 2018

A300674 Number of monic irreducible polynomials of degree n over GF(8) that have a given nonzero trace.

Original entry on oeis.org

1, 4, 21, 128, 819, 5460, 37449, 262144, 1864128, 13421772, 97612893, 715827840, 5286113595, 39268272420, 293203100463, 2199023255552, 16557351571215, 125099989647360, 948126237341157, 7205759403792768, 54901024028884989, 419244183493398900, 3208129404123400281, 24595658764945981440

Offset: 1

Seiichi Manyama, Mar 11 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000
F. Ruskey, C.R. Miers, and J. Sawada, The number of irreducible polynomials and Lyndon words with given trace, SIAM J. Discrete Math. 14 (2001), 240-245.

Column 8 of A110540.

Cf. A000048, A008683, A054660, A300675.

a[n_] := DivisorSum[n, MoebiusMu[#] * 8^(n/#) &, OddQ[#] &] / (8*n); Array[a, 24] (* Amiram Eldar, Oct 04 2023 *)

a(n) = sumdiv(n, d, if (d%2, moebius(d)*8^(n/d)))/(8*n); \\ Michel Marcus, Mar 11 2018

a(n) = (1/(8*n)) * Sum_{odd d divides n} mu(d)*8^(n/d), where mu is the Möbius function A008683.

A300675 Number of monic irreducible polynomials of degree n over GF(16) that have a given nonzero trace.

Original entry on oeis.org

1, 8, 85, 1024, 13107, 174760, 2396745, 33554432, 477218560, 6871947672, 99955602525, 1466015503360, 21651921285435, 321685687669320, 4803839602524143, 72057594037927936, 1085102592571150095, 16397105843297320960, 248545604361560274405, 3777893186295716170752, 57567896172125197996605

Offset: 1

Seiichi Manyama, Mar 11 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..500
F. Ruskey, C.R. Miers, and J. Sawada, The number of irreducible polynomials and Lyndon words with given trace, SIAM J. Discrete Math. 14 (2001), 240-245.

Column 16 of A110540.

Cf. A000048, A008683, A054660, A300674.

a[n_] := DivisorSum[n, MoebiusMu[#] * 16^(n/#) &, OddQ[#] &] / (16*n); Array[a, 21] (* Amiram Eldar, Oct 04 2023 *)

a(n) = sumdiv(n, d, if (d%2, moebius(d)*16^(n/d)))/(16*n); \\ Michel Marcus, Mar 11 2018

a(n) = (1/(16*n)) * Sum_{odd d divides n} mu(d)*16^(n/d), where mu is the Möbius function A008683.

A054666 Number of 6-ary Lyndon words with trace 1 mod 6.

Original entry on oeis.org

1, 3, 12, 54, 259, 1296, 6665, 34992, 186624, 1007769, 5496925, 30233088, 167444795, 932906715, 5224277604, 29386561536, 165947641615, 940369969152, 5345260877285, 30467987000514, 174102782860140, 997134120017175

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of 6-ary Lyndon words with trace 5 mod 6.

F. Ruskey, Number of q-ary Lyndon words with given trace mod q

Cf. A000048, A051841, A046211, A046209, A054660, etc.

More terms from James Sellers, Apr 19 2000

cp's OEIS Frontend

A027377 Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A054661 Number of monic irreducible polynomials over GF(4) with zero trace.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A074450 Let x = RootOf(z^2 + z + 1) and y = 1+x. Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace x.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A074448 Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A074449 Number of 4-ary Lyndon words of length n over GF(4) with trace 1 and subtrace 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A300628 Triangular array T(n,k) giving coefficients in expansion of Product_{j=1..n} (1+x^j)^2 mod x^(n+1)-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A300674 Number of monic irreducible polynomials of degree n over GF(8) that have a given nonzero trace.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula