A027376 -id:A027376 - cp's OEIS frontend

A001693 Number of degree-n irreducible polynomials over GF(7); dimensions of free Lie algebras.

1, 7, 21, 112, 588, 3360, 19544, 117648, 720300, 4483696, 28245840, 179756976, 1153430600, 7453000800, 48444446376, 316504099520, 2077057800300, 13684147881600, 90467419857752, 599941851861744

Offset: 0

N. J. A. Sloane

Number of aperiodic necklaces with n beads of 7 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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..1186 (terms 0..200 from T. D. Noe)
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. J. Simmons, The number of irreducible polynomials of degree n over GF(p), Amer. Math. Monthly, 77 (1970), 743-745.
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

Column 7 of A074650.

Cf. A027376, A000031, A001037, A032164.

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

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

a(n) = if(n, sumdiv(n, d, moebius(d)*7^(n/d))/n, 1) \\ Altug Alkan, Dec 01 2015

a(n) = (1/n)*Sum_{d|n} mu(d)*7^(n/d), for n>0.

G.f.: k=7, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

Description corrected by Vladeta Jovovic, Feb 09 2001

A005377 Number of low discrepancy sequences in base 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139

Offset: 1

N. J. A. Sloane, Simon Plouffe

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51-70.

Cf. A005356 (base 2), A005357 (base 3), A005358 (base 5), A274039 (Plouffe's g.f.)

Cf. A001037 (N(2,n)), A027376 (N(3,n)), A027377 (N(4,n)), A062692 (M(2,n)), A114945 (M(3,n)), A114946 (M(4,n)).

N := proc(b,n)
    option remember;
    local d;
    add(b^d*numtheory[mobius](n/d),d=numtheory[divisors](n)) ;
    %/n ;
end proc:
M := proc(b,n)
    local h;
    if n = 0 then
        0;
    else
        add(N(b,h),h=1..n) ;
    end if;
end proc:
nMax := proc(b,s)
    local n;
    for n from 0 do
        if M(b,n) > s then
            return n-1 ;
        end if;
    end do:
end proc:
A005377 := proc(s)
    local n,b;
    b := 4 ;
    n := nMax(b,s) ;
    n*(s-M(b,n))+add( (h-1)*N(b,h),h=1..n) ;
end proc:
seq(A005377(n),n=1..40) ; # R. J. Mathar, Jun 09 2016

Np[b_, n_] := Np[b, n] = Sum[b^d*MoebiusMu[n/d], {d, Divisors[n]}]/n;
M[b_, n_] := If[n == 0, 0, Sum[Np[b, h], {h, 1, n}]];
nMax[b_, s_] := Module[{n}, For[n = 0, True, n++, If[M[b, n] > s, Return[n - 1]]]];
a[s_] := Module[{n, b}, b = 4; n = nMax[b, s]; n*(s - M[b, n]) + Sum[(h - 1)*Np[b, h], {h, 1, n}]];
Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Sep 12 2023, after R. J. Mathar *)

Let N(b,n) = (1/n) * Sum_{d|n} mobius(n/d) * b^d. Let M(b,n) = Sum_{k=1..n} N(b,k) with M(b,0) = 0. Let r = r(b,n) be the largest value r such that M(b,r) <= n. Then a(n) = r * (n - M(4, r)) + Sum_{h=1..r} (h-1) * N(4, h) [From Niederreiter paper]. - Sean A. Irvine, Jun 07 2016

G.f.: z^4 * (z^2+1) * (z^4-z^2+1) / (z-1)^2; [Conjectured by Simon Plouffe in his 1992 dissertation, but is incorrect.]

Terms, offset, and formula corrected by Sean A. Irvine, Jun 07 2016

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

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.

A133267 Number of Lyndon words on {1, 2, 3} with an even number of 1's.

Original entry on oeis.org

2, 1, 4, 8, 24, 56, 156, 400, 1092, 2928, 8052, 22080, 61320, 170664, 478288, 1344800, 3798240, 10760568, 30585828, 87166656, 249055976, 713197848, 2046590844, 5883926400, 16945772184, 48881973840, 141214767876, 408513980160, 1183282368360, 3431518388960

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 03 2008

nonn

A Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d)=sum L(n-d, n_1,..., n_(k-1)); n_1+...+n_(k-1)=d where L(n_0, n_1,...,n_(k-1))=(1/n)sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0=even. Alternatively, a(n)=(sum mu(d)*3^(n/d)/n; d|n) - (sum mu(d)*(3^(n/d)-1)/(2n); d|n, d odd).

			For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only the first two and the last two have an even number of 1's. Thus a(3) = 4.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

Alois P. Heinz, Table of n, a(n) for n = 1..650
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Mike Zabrocki, Course website

Cf. A006575, A027376.

with(numtheory): a:= n-> add(mobius(d) *3^(n/d), d=divisors(n))/n -add(mobius(d) *(3^(n/d)-1), d=select(x-> irem(x, 2)=1, divisors(n)))/ (2*n): seq(a(n), n=1..30);  # Alois P. Heinz, Jul 29 2011

a[n_] := DivisorSum[n, MoebiusMu[#]*(3^(n/#) - (1/2)*Boole[OddQ[#]]*(3^(n/#)-1))&]/n; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)

a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n))); \\ Michel Marcus, May 17 2018

a(1)=2; for n>1, if n=2^k for some k, then a(n) = ((3^(n/2)-1)^2)/(2*n). Otherwise, if n is even then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-2*3^(n/(2*d)))/(2*n). If n is odd then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-1)/(2*n).

A215328 Smooth Lyndon words with 3 colors.

Original entry on oeis.org

1, 3, 2, 5, 10, 24, 49, 112, 240, 534, 1175, 2626, 5848, 13153, 29594, 66955, 151814, 345494, 788049, 1802675, 4132469, 9495242, 21859912, 50423465, 116511119, 269666586, 625101288, 1451128164, 3373250909, 7851415835

Offset: 0

Joerg Arndt, Aug 08 2012

nonn

We call a Lyndon word (x[1],x[2],...,x[n]) smooth if abs(x[k]-x[k-1]) <= 1 for 2<=k<=n.

All binary Lyndon words (2 colors, A001037) are necessarily smooth.

			(See A215327).

Cf. A027376 (Lyndon words, 3 colors), A215327 (smooth necklaces, 3 colors).

More terms from Joerg Arndt, Jun 17 2019

A056288 Number of primitive (period n) n-bead necklaces with exactly three different colored beads.

Original entry on oeis.org

0, 0, 2, 9, 30, 89, 258, 720, 2016, 5583, 15546, 43215, 120750, 338001, 950030, 2677770, 7573350, 21478632, 61088874, 174179133, 497812378, 1425832077, 4092087522, 11765778330, 33887517840, 97756266615, 282414622728, 816999371955, 2366509198350, 6862929885407

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A027376.

Column k=3 of A254040.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
a:= n-> add(b(n, 3-j)*binomial(3, j)*(-1)^j, j=0..3):
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 25 2015

b[n_, k_] := b[n, k] = If[n==0, 1, DivisorSum[n, MoebiusMu[n/#]*k^#&]/n];
a[n_] := Sum[b[n, 3 - j]*Binomial[3, j]*(-1)^j, {j, 0, 3}];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jun 06 2018, after Alois P. Heinz *)

Sum mu(d)*A056283(n/d) where d|n.

A118264 Coefficient of q^n in (1-q)^3/(1-3q); dimensions of the enveloping algebra of the derived free Lie algebra on 3 letters.

Original entry on oeis.org

1, 0, 3, 8, 24, 72, 216, 648, 1944, 5832, 17496, 52488, 157464, 472392, 1417176, 4251528, 12754584, 38263752, 114791256, 344373768, 1033121304, 3099363912, 9298091736, 27894275208, 83682825624, 251048476872, 753145430616

Offset: 0

Mike Zabrocki, Apr 20 2006

a(n) is the number of generalized compositions of n when there are i^2-1 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010

			The enveloping algebra of the derived free Lie algebra is characterized as the intersection of the kernels of all partial derivative operators in the space of non-commutative polynomials, a(0) = 1 since all constants are killed by derivatives, a(1) = 0 since no polys of degree 1 are killed, a(2) = 3 since all Lie brackets [x1,x2], [x1,x3], [x2, x3] are killed by all derivative operators.

C. Reutenauer, Free Lie algebras. London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1993. xviii+269 pp.

Michael De Vlieger, Table of n, a(n) for n = 0..2097
Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082, 2005. See also Canad. J. Math. 60 (2008), no. 2, 266-296.
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See pp. 17, 20.
Index entries for linear recurrences with constant coefficients, signature (3).

Cf. A080923, A027376, A118265, A118266.

f:=n->coeftayl((1-q)^3/(1-3*q),q=0,n):seq(f(i),i=0..15);

CoefficientList[Series[(1-q)^3/(1-3q),{q,0,30}],q] (* or *) Join[{1,0,3}, NestList[3#&,8,30]] (* Harvey P. Dale, Jun 28 2011 *)
Join[{1, 0, 3}, LinearRecurrence[{3}, {8}, 24]] (* Jean-François Alcover, Sep 23 2017 *)

G.f.: (1-x)^3/(1-3x).
a(n) = 3^{n-1}-3^{n-3} for n>=3.
a(n) = A080923(n-1), n>1.
If p[i]=i^2-1 and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, May 02 2010
For a(n)>=8, a(n+1)=3*a(n). - Harvey P. Dale, Jun 28 2011

Formula corrected Mike Zabrocki, Jul 22 2010

A136704 Number of Lyndon words on {1,2,3} with an odd number of 1's and an odd number of 2's.

Original entry on oeis.org

0, 1, 2, 5, 12, 30, 78, 205, 546, 1476, 4026, 11070, 30660, 85410, 239144, 672605, 1899120, 5380830, 15292914, 43584804, 124527988, 356602950, 1023295422, 2941974270, 8472886092, 24441017580, 70607383938

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008

nonn

This sequence is also the number of Lyndon words on {1,2,3} with an even number of 1's and an odd number of 2's except that a(1) = 1 in this case.

Also, a Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d) = Sum L(n-d, n_1,..., n_(k-1)); n_1 + ... +n_(k-1) = d where L(n_0, n_1,...,n_(k-1)) = (1/n) Sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0, n_1 = odd.

			For n = 3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only 123 and 132 have an odd number of both 1's and 2's. Thus a(3) = 2.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

Amiram Eldar, Table of n, a(n) for n = 1..1000
E. N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999), 671-684.
Mike Zabrocki, MATH5020 York University Course Website.

Cf. A006575, A027376, A133267, A136703.

Bisections: A253076, A253077.

a[1] = 0;
a[n_] := If[OddQ[n], Sum[MoebiusMu[d] * 3^(n/d), {d, Divisors[n]}], Sum[Boole[OddQ[d]] MoebiusMu[d] * (3^(n/d)-1), {d, Divisors[n]}]]/(4n);
Array[a, 27] (* Jean-François Alcover, Aug 26 2019 *)

a(n) = if (n==1, 0, if (n % 2, sumdiv(n, d, moebius(d)*3^(n/d))/(4*n), sumdiv(n, d, if (d%2, moebius(d)*(3^(n/d)-1)))/(4*n))); \\ Michel Marcus, Aug 26 2019

a(1) = 0; for n>1, if n = odd then a(n) = Sum_{d|n} (mu(d)*3^(n/d))/(4n). If n = even, then a(n) = Sum_{d|n, d odd} (mu(d)*(3^(n/d)-1))/(4n).

cp's OEIS Frontend

A001693 Number of degree-n irreducible polynomials over GF(7); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005377 Number of low discrepancy sequences in base 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

A133267 Number of Lyndon words on {1, 2, 3} with an even number of 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A215328 Smooth Lyndon words with 3 colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A056288 Number of primitive (period n) n-bead necklaces with exactly three different colored beads.

Views

Author

Keywords