Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #11 Aug 13 2023 02:48:29
%S 1,2,3,6,13,26,55,110,226,456,925,1862,3761,7562,15223,30586,61456,
%T 123362,247612,496694,996199,1997294,4003747,8023886,16078346,
%U 32212256,64528069,129246720,258849061,518358122,1037951557,2078209982,4160751616
%N a(0) = 1, a(1) = 2; for n>=2 a(n) is the number of degree-n reducible polynomials over GF(2).
%C Dimensions of homogeneous subspaces of shuffle algebra defined in the "Comments" line.
%C 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.
%D M. Lothaire, Combinatorics on words, Cambridge mathematical library, 1983, p. 126 (definition of shuffle algebra).
%F For n>=2, a(n) = 2^n - A001037(n).
%e Degree 3: x uu x = 2 x^2, y uu y = 2 y^2, x uu y = xy + yx.
%t 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 *)
%Y Cf. A000079, A001037.
%K nonn
%O 0,2
%A Claude Lenormand (claude.lenormand(AT)free.fr), Jan 03 2001
%E Better description from Sharon Sela (sharonsela(AT)hotmail.com), Feb 19 2002
%E More terms from _Max Alekseyev_, Aug 24 2012