A042979 -id:A042979 - cp's OEIS frontend

A051841 Number of binary Lyndon words with an even number of 1's.

1, 0, 1, 1, 3, 4, 9, 14, 28, 48, 93, 165, 315, 576, 1091, 2032, 3855, 7252, 13797, 26163, 49929, 95232, 182361, 349350, 671088, 1290240, 2485504, 4792905, 9256395, 17894588, 34636833, 67106816, 130150493, 252641280, 490853403, 954429840, 1857283155, 3616800768, 7048151355, 13743869130, 26817356775

Offset: 1

Frank Ruskey, Dec 13 1999

Also number of trace 0 irreducible polynomials over GF(2).

Also number of trace 0 Lyndon words over GF(2).

			a(5) = 3 = |{ 00011, 00101, 01111 }|.

May, Robert M. "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019

T. D. Noe, Table of n, a(n) for n = 1..300
F. Ruskey, Number of q-ary Lyndon words with given trace mod q
F. Ruskey, Number of Lyndon words over GF(q) with given trace
Index entries for sequences related to Lyndon words

Same as A001037 - A000048. Same as A042980 + A042979.
Cf. A027750, A008683.
Cf. A000010.

a051841 n = (sum $ zipWith (\u v -> gcd 2 u * a008683 u * 2 ^ v)
             ds $ reverse ds) `div` (2 * n) where ds = a027750_row n
-- Reinhard Zumkeller, Mar 17 2013

a[n_] := Sum[GCD[d, 2]*MoebiusMu[d]*2^(n/d), {d, Divisors[n]}]/(2n);
Table[a[n], {n, 1, 32}]
(* Jean-François Alcover, May 14 2012, from formula *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%2==0, L(n, k), 0 ) ) / n;
vector(33,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

a(n) = 1/(2*n)*Sum_{d|n} gcd(d,2)*mu(d)*2^(n/d).
a(n) ~ 2^(n-1) / n. - Vaclav Kotesovec, May 31 2019
From Richard L. Ollerton, May 10 2021: (Start)
a(n) = 1/(2*n)*Sum_{k=1..n} gcd(gcd(n,k),2)*mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} gcd(n/gcd(n,k),2)*mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)

A042980 Number of degree-n irreducible polynomials over GF(2) with trace = 0 and subtrace = 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 5, 6, 15, 24, 45, 85, 155, 288, 550, 1008, 1935, 3626, 6885, 13107, 24940, 47616, 91225, 174590, 335626, 645120, 1242600, 2396745, 4627915, 8947294, 17318945, 33552384, 65076240, 126320640, 245424829, 477218560, 928638035, 1808400384, 3524082400, 6871921458, 13408691175, 26178823218

Offset: 1

Frank Ruskey

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Cattell, C. R. Miers, F. Ruskey, J. Sawada and M. Serra, The Number of Irreducible Polynomials over GF(2) with Given Trace and Subtrace, J. Comb. Math. and Comb. Comp., 47 (2003) 31-64.
F. Ruskey, Number of irreducible polynomials over GF(2) with given trace and subtrace

Cf. A042979, A042981, A042982.

Cf. A074027, A074028, A074029, A074030.

L[n_, k_] := Sum[ MoebiusMu[d]*Binomial[n/d, k/d], {d, Divisors[GCD[n,k]]}]/n;
a[n_]:=Sum[ If[ Mod[n+k, 4]==2, L[n, k], 0], {k, 0, n}];
Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Jun 28 2012, from formula *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%4==2, L(n, k), 0 ) ) / n;
vector(33,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

a(n) = (1/n) * Sum_{ L(n, k) : n+k = 2 mod 4}, where L(n, k) = Sum_{ mu(d)*binomial(n/d, k/d): d|gcd(n, k)}.

A042982 Number of degree-n irreducible polynomials over GF(2) with trace = 1 and subtrace = 1.

Original entry on oeis.org

0, 1, 0, 1, 2, 2, 5, 8, 13, 27, 45, 85, 160, 288, 550, 1024, 1920, 3654, 6885, 13107, 24989, 47616, 91225, 174760, 335462, 645435, 1242600, 2396745, 4628480, 8947294, 17318945, 33554432, 65074253, 126324495, 245424829, 477218560, 928645120, 1808400384, 3524082400, 6871947672, 13408665600, 26178873147

Offset: 1

Frank Ruskey

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Cattell, C. R. Miers, F. Ruskey, J. Sawada and M. Serra, The Number of Irreducible Polynomials over GF(2) with Given Trace and Subtrace, J. Comb. Math. and Comb. Comp., 47 (2003) 31-64.
F. Ruskey, Number of irreducible polynomials over GF(2) with given trace and subtrace

Cf. A042979, A042980, A042981.

Cf. A074027, A074028, A074029, A074030.

L[n_, k_] := Sum[ MoebiusMu[d]*Binomial[n/d, k/d], {d, Divisors[GCD[n, k]]}]/n; a[n_] := Sum[ If[ Mod[n+k, 4] == 3, L[n, k], 0], {k, 0, n}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Jun 28 2012, from formula *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%4==3, L(n, k), 0 ) ) / n;
vector(33,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

a(n) = (1/n) * Sum_{ L(n, k) : n+k = 3 mod 4}, where L(n, k) = Sum_{ mu(d)*binomial(n/d, k/d) : d|gcd(n, k)}.

A074027 Number of binary Lyndon words of length n with trace 0 and subtrace 0 over Z_2.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 5, 8, 15, 24, 45, 80, 155, 288, 550, 1024, 1935, 3626, 6885, 13056, 24940, 47616, 91225, 174760, 335626, 645120, 1242600, 2396160, 4627915, 8947294, 17318945, 33554432, 65076240, 126320640, 245424829, 477211280, 928638035, 1808400384, 3524082400

Offset: 1

Frank Ruskey and Nate Kube, Aug 21 2002

Same as the number of binary Lyndon words of length n with trace 0 and subtrace 0 over GF(2).

			a(6;0,0)=2 since the two binary Lyndon words of trace 0, subtrace 0 and length 6 are { 001111, 010111 }.

Max Alekseyev, PARI/GP scripts for miscellaneous math problems
F. Ruskey, Binary Lyndon words with given trace and subtrace
F. Ruskey, Binary Lyndon words with given trace and subtrace over GF(2)

Cf. A074028, A074029, A074030.

a(2n) = A042979(2n), a(2n+1) = A042980(2n+1). This follows from Cattell et al. (see A042979), Main Theorem on p. 33 and Theorem 4 on p. 44.

Terms a(33) onward from Max Alekseyev, Apr 09 2013

A074028 Number of binary Lyndon words of length n with trace 0 and subtrace 1 over Z_2.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 4, 6, 13, 24, 48, 85, 160, 288, 541, 1008, 1920, 3626, 6912, 13107, 24989, 47616, 91136, 174590, 335462, 645120, 1242904, 2396745, 4628480, 8947294, 17317888, 33552384, 65074253, 126320640, 245428574, 477218560, 928645120, 1808400384, 3524068955

Offset: 1

Frank Ruskey and Nate Kube, Aug 21 2002

Same as the number of binary Lyndon words of length n with trace 0 and subtrace 1 over GF(2).

			a(5;0,1)=2 since the two binary Lyndon words of trace 0, subtrace 1 and length 5 are { 00011, 00101 }.

Max Alekseyev, PARI/GP scripts for miscellaneous math problems
F. Ruskey, Binary Lyndon words with given trace and subtrace
F. Ruskey, Binary Lyndon words with given trace and subtrace over GF(2)

Cf. A074027, A074029, A074030.

a(2n) = A042980(2n), a(2n+1) = A042979(2n+1). This follows from Cattell et al. (see A042979), Main Theorem on p. 33 and Theorem 4 on p. 44.

Terms a(33) onward from Max Alekseyev, Apr 09 2013

A074029 Number of binary Lyndon words of length n with trace 1 and subtrace 0 over Z_2.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 8, 15, 27, 48, 85, 155, 288, 541, 1024, 1935, 3654, 6912, 13107, 24940, 47616, 91136, 174760, 335626, 645435, 1242904, 2396745, 4627915, 8947294, 17317888, 33554432, 65076240, 126324495, 245428574, 477218560, 928638035, 1808400384, 3524068955

Offset: 1

Frank Ruskey and Nate Kube, Aug 21 2002

Same as the number of binary Lyndon words of length n with trace 1 and subtrace 0 over GF(2).

			a(3;1,0)=1 since the one binary Lyndon word of trace 1, subtrace 0 and length 3 is { 001 }.

Max Alekseyev, PARI/GP scripts for miscellaneous math problems
F. Ruskey, Binary Lyndon words with given trace and subtrace
F. Ruskey, Binary Lyndon words with given trace and subtrace over GF(2)

Cf. A074027, A074028, A074030.

a(2n) = A042982(2n), a(2n+1) = A049281(2n+1). This follows from Cattell et al. (see A042979), Main Theorem on p. 33 and Theorem 4 on p. 44.

Terms a(33) onward from Max Alekseyev, Apr 09 2013

A074030 Number of binary Lyndon words of length n with trace 1 and subtrace 1 over Z_2.

Original entry on oeis.org

0, 0, 0, 1, 2, 3, 5, 8, 13, 24, 45, 85, 160, 297, 550, 1024, 1920, 3626, 6885, 13107, 24989, 47709, 91225, 174760, 335462, 645120, 1242600, 2396745, 4628480, 8948385, 17318945, 33554432, 65074253, 126320640, 245424829, 477218560, 928645120, 1808414181, 3524082400

Offset: 1

Frank Ruskey and Nate Kube, Aug 21 2002

Same as the number of binary Lyndon words of length n with trace 1 and subtrace 1 over GF(2).

Max Alekseyev, PARI/GP scripts for miscellaneous math problems
F. Ruskey, Binary Lyndon words with given trace and subtrace
F. Ruskey, Binary Lyndon words with given trace and subtrace over GF(2)

Cf. A074027, A074028, A074029.

a(2n) = A042981(2n), a(2n+1) = A042982(2n+1). This follows from Cattell et al. (see A042979), Main Theorem on p. 33 and Theorem 4 on p. 44.

Corrected by Franklin T. Adams-Watters, Oct 25 2006

Terms a(33) onward from Max Alekseyev, Apr 09 2013

A074032 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 1.

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

Offset: 1

Frank Ruskey and Nate Kube, Aug 26 2002

Let a = RootOf( x^2+x+1 ) and b = 1+a. Same as number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace a. Same as number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace b.

Is this a duplicate of A074450? - R. J. Mathar, Dec 16 2020

E. N. Kuz'min, Irreducible polynomials over a finite field and an analogue of Gauss sums over a field of characteristic 2, Siberian Mathematical Journal, 32, 982-989 (1991).
Jon Maiga, Computer-generated formulas for A074032, Sequence Machine.
Frank Ruskey, Number of irreducible polynomials over GF(4) with given trace and subtrace

Cf. A074031, A074033, A074034, A074035, A042979.

Cf. A074450.

a(n) = A042979(2*n)/2 [discovered by Sequence Machine]. - Andrey Zabolotskiy, Oct 09 2021

More terms from Ruskey's website added by Joerg Arndt, Jan 16 2011

Terms a(17) and beyond from Andrey Zabolotskiy, Dec 15 2020

A042981 Number of degree-n irreducible polynomials over GF(2) with trace = 1 and subtrace = 0.

Original entry on oeis.org

1, 0, 1, 1, 1, 3, 4, 8, 15, 24, 48, 85, 155, 297, 541, 1024, 1935, 3626, 6912, 13107, 24940, 47709, 91136, 174760, 335626, 645120, 1242904, 2396745, 4627915, 8948385, 17317888, 33554432, 65076240, 126320640, 245428574, 477218560, 928638035, 1808414181, 3524068955, 6871947672, 13408691175, 26178823218

Offset: 1

Frank Ruskey

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Cattell, C. R. Miers, F. Ruskey, J. Sawada and M. Serra, The Number of Irreducible Polynomials over GF(2) with Given Trace and Subtrace, J. Comb. Math. and Comb. Comp., 47 (2003) 31-64.
F. Ruskey, Number of irreducible polynomials over GF(2) with given trace and subtrace

Cf. A042979, A042980, A042982.

Cf. A074027, A074028, A074029, A074030.

L[n_, k_] := Sum[ MoebiusMu[d]*Binomial[n/d, k/d], {d, Divisors[GCD[n, k]]}]/n;
a[n_] := Sum[ If[ Mod[n+k, 4] == 1, L[n, k], 0], {k, 0, n}];
Table[a[n], {n, 1, 32}]
(* Jean-François Alcover, Jun 28 2012, from formula *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%4==1, L(n, k), 0 ) ) / n;
vector(33,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

a(n) = (1/n) * Sum_{ L(n, k) : n+k = 1 mod 4}, where L(n, k) = Sum_{ mu(d)*{binomial(n/d, k/d)} : d|gcd(n, k)}.

A053727 Triangle T(n,k) = Sum_{d|gcd(n,k)} mu(d)*C(n/d,k/d) (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 2, 0, 3, 3, 0, 4, 4, 4, 0, 5, 10, 10, 5, 0, 6, 12, 18, 12, 6, 0, 7, 21, 35, 35, 21, 7, 0, 8, 24, 56, 64, 56, 24, 8, 0, 9, 36, 81, 126, 126, 81, 36, 9, 0, 10, 40, 120, 200, 250, 200, 120, 40, 10, 0, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 0, 12, 60

Offset: 1

N. J. A. Sloane, Mar 24 2000

Triangle of number of primitive words over {0,1} of length n that contain k 1's, for n,k >= 1. - Benoit Cloitre, Jun 08 2004

			Triangle begins
  1;
  2,  0;
  3,  3,  0;
  4,  4,  4,  0;
  5, 10, 10,  5,  0;
  6, 12, 18, 12,  6,  0;
  ...

J.-P. Allouche and J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 29.

Index entries for triangles and arrays related to Pascal's triangle

Cf. A042979, A042980. T(2n, n), T(2n+1, n) match A007727, A001700, respectively. Row sums match A027375.

Same triangle as A050186 except this one does not include column 0.

T[n_, k_] := DivisorSum[GCD[k, n], MoebiusMu[#] Binomial[n/#, k/#] &]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

T(n,k)=sumdiv(gcd(k,n),d,moebius(d)*binomial(n/d,k/d)) \\ Benoit Cloitre, Jun 08 2004

cp's OEIS Frontend

A051841 Number of binary Lyndon words with an even number of 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A042980 Number of degree-n irreducible polynomials over GF(2) with trace = 0 and subtrace = 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A042982 Number of degree-n irreducible polynomials over GF(2) with trace = 1 and subtrace = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A074027 Number of binary Lyndon words of length n with trace 0 and subtrace 0 over Z_2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A074028 Number of binary Lyndon words of length n with trace 0 and subtrace 1 over Z_2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A074029 Number of binary Lyndon words of length n with trace 1 and subtrace 0 over Z_2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A074030 Number of binary Lyndon words of length n with trace 1 and subtrace 1 over Z_2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A074032 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 1.

Views

Author

Keywords

Comments

Links