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

Author

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

Keywords

• nonn

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.

Examples

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

References

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

Crossrefs

Cf. A000079, A001037.

Programs

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

Formula

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

Extensions

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

More terms from Max Alekseyev, Aug 24 2012