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
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), 120-135.
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. (Annotated scanned copy)
FORMULA
Euler transform of sequence b(n) = sum_{d|n, A001037(d)>=n/d} 1. - Franklin T. Adams-Watters, 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}]]] (* 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
More terms from Franklin T. Adams-Watters, Jun 19 2006
STATUS
approved