

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

T. D. Noe, Table of n, a(n) for n=1..1000
A. K. Agarwal and G. L. Mullen, Partitions with "d(a) copies of a", J. Combin. Theory, A48 (1988), 120135.
R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 6582. (Annotated scanned copy)


FORMULA

Euler transform of sequence b(n) = sum_{dn, A001037(d)>=n/d} 1.  Franklin T. AdamsWatters, Jun 19 2006


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

Cf. A006168, A006169, A006170, A006171.
Cf. A001037.
Sequence in context: A299069 A097497 A279328 * A137504 A173401 A109794
Adjacent sequences: A006164 A006165 A006166 * A006168 A006169 A006170


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Gary Mullen, Jun 03 2003
More terms from Franklin T. AdamsWatters, Jun 19 2006


STATUS

approved



