A058766 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

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.