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

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

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

Cf. A006168, A006169, A006170, A006171.

Cf. A001037.

Sequence in context: A097497 A332681 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. Adams-Watters, Jun 19 2006

Status

approved