

A006167


Number of factorization patterns of polynomials of degree n over F_2.
(Formerly M2349)


5



1, 3, 4, 8, 11, 20, 27, 45, 61, 95, 128, 193, 257, 374, 497, 703, 927, 1287, 1683, 2297, 2987, 4013, 5186, 6887, 8843, 11614, 14836, 19294, 24514, 31622, 39968, 51167, 64377, 81839, 102509, 129528, 161539, 202959, 252124, 315110, 389949, 485062
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Let F_q(n) represent the number of factorization patterns of n with the property that there exists a monic polynomial V of degree n over the finite field F_q such that V factors over F_q into one of the F_q(n) factorization patterns. Sequence is for the q=2 case,


REFERENCES

R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 6582.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA



EXAMPLE

For n=3 there are 5 factorization patterns of cubic polynomials: 3, 2 + 1, 1^3, 1^2 + 1, 1 + 1 + 1. For example 1^2 + 1 corresponds to a cubic polynomial which factors as a linear of multiplicity 2 and a second distinct linear factor. For q=2 the pattern 1 + 1 + 1 is not allowed since over F_2 there are only two distinct monic irreducibles of degree 1. Thus a(3) = 4.


MATHEMATICA

A001037[n_] := Sum[ MoebiusMu[n/d]*2^d, {d, Divisors[n]}]/n; b[n_] := Sum[ nd = A001037[d]; If[nd >= n/d, 1, 0], {d, Divisors[n]}]; EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1  x^Range[m])^seq), {x, 0, m}], x]]; A006167 = Rest[ EulerTransform[ Table[ b[n], {n, 1, 42}]]] (* JeanFrançois Alcover, Mar 15 2012, after Franklin T. AdamsWatters *)


CROSSREFS



KEYWORD

nonn,nice


AUTHOR



EXTENSIONS

Additional comments from Gary Mullen, Jun 03 2003


STATUS

approved



