login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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: 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. Adams-Watters, Jun 19 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 18:14 EST 2020. Contains 332005 sequences. (Running on oeis4.)