A058766 a(0) = 1, a(1) = 2; for n>=2 a(n) is the number of degree-n reducible polynomials over GF(2).

1, 2, 3, 6, 13, 26, 55, 110, 226, 456, 925, 1862, 3761, 7562, 15223, 30586, 61456, 123362, 247612, 496694, 996199, 1997294, 4003747, 8023886, 16078346, 32212256, 64528069, 129246720, 258849061, 518358122, 1037951557, 2078209982, 4160751616

Offset

0,2

Comments

Dimensions of homogeneous subspaces of shuffle algebra defined in the "Comments" line.

Let x and y be two letters, m and m' any two words, e is the empty word of the free monoid generated by (x,y). Let uu denote the shuffle or Hurwitz product: xm uu ym' =x.(m uu ym') + y.(xm uu m'); of course, e is neutral.

References

M. Lothaire, Combinatorics on words, Cambridge mathematical library, 1983, p. 126 (definition of shuffle algebra).

Links

Table of n, a(n) for n=0..32.

Formula

For n>=2, a(n) = 2^n - A001037(n).

Example

Degree 3: x uu x = 2 x^2, y uu y = 2 y^2, x uu y = xy + yx.

Mathematica

a[n_] := 2^n - DivisorSum[n, MoebiusMu[n/#] * 2^# &] / n; a[0] = 1; a[1] = 2; Array[a, 33, 0] (* Amiram Eldar, Aug 13 2023 *)

Crossrefs

Cf. A000079, A001037.

Sequence in context: A007910 A293315 A052702 * A127601 A030038 A030040

Adjacent sequences: A058763 A058764 A058765 * A058767 A058768 A058769

Keyword

nonn

Author

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 03 2001

Extensions

Better description from Sharon Sela (sharonsela(AT)hotmail.com), Feb 19 2002

More terms from Max Alekseyev, Aug 24 2012

Status

approved