|
|
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), 65-82.
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}]]] (* Jean-François Alcover, Mar 15 2012, after Franklin T. Adams-Watters *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Additional comments from Gary Mullen, Jun 03 2003
|
|
STATUS
|
approved
|
|
|
|