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

%I M2349 #26 Nov 03 2017 22:18:25

%S 1,3,4,8,11,20,27,45,61,95,128,193,257,374,497,703,927,1287,1683,2297,

%T 2987,4013,5186,6887,8843,11614,14836,19294,24514,31622,39968,51167,

%U 64377,81839,102509,129528,161539,202959,252124,315110,389949,485062

%N Number of factorization patterns of polynomials of degree n over F_2.

%C 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,

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A006167/b006167.txt">Table of n, a(n) for n=1..1000</a>

%H A. K. Agarwal and G. L. Mullen, <a href="http://dx.doi.org/10.1016/0097-3165(88)90079-9">Partitions with "d(a) copies of a"</a>, J. Combin. Theory, A48 (1988), 120-135.

%H R. A. Hultquist, G. L. Mullen and H. Niederreiter, <a href="/A006167/a006167.pdf">Association schemes and derived PBIB designs of prime power order</a>, Ars. Combin., 25 (1988), 65-82. (Annotated scanned copy)

%F Euler transform of sequence b(n) = sum_{d|n, A001037(d)>=n/d} 1. - _Franklin T. Adams-Watters_, Jun 19 2006

%e 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.

%t 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_ *)

%Y Cf. A006168, A006169, A006170, A006171.

%Y Cf. A001037.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E Additional comments from Gary Mullen, Jun 03 2003

%E More terms from _Franklin T. Adams-Watters_, Jun 19 2006