

A269456


Triangular array T(n,k) read by rows: T(n,k) is the number of degree n monic polynomials in GF(2)[x] with exactly k factors in its unique factorization into irreducible polynomials.


0



2, 1, 3, 2, 2, 4, 3, 5, 3, 5, 6, 8, 8, 4, 6, 9, 18, 14, 11, 5, 7, 18, 30, 32, 20, 14, 6, 8, 30, 63, 57, 47, 26, 17, 7, 9, 56, 114, 124, 86, 62, 32, 20, 8, 10, 99, 226, 234, 191, 116, 77, 38, 23, 9, 11, 186, 422, 480, 370, 260, 146, 92, 44, 26, 10, 12, 335, 826, 932, 775, 512, 330, 176, 107, 50, 29, 11, 13
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Column 1 is A001037.
Row sums are 2^n.
T(n,k) is the number of lengthn binary words having k factors in their standard (Chen, Fox, Lyndon)factorization. [Joerg Arndt, Nov 05 2017]


LINKS

Table of n, a(n) for n=1..78.
Daniel Panario, Random Polynomials over Finite Fields: Statistics and Algorithms, 2013.


FORMULA

G.f.: Product_{k>0} 1/(1  y*x^k)^A001037(k).


EXAMPLE

2,
1, 3,
2, 2, 4,
3, 5, 3, 5,
6, 8, 8, 4, 6,
9, 18, 14, 11, 5, 7,
18, 30, 32, 20, 14, 6, 8,
30, 63, 57, 47, 26, 17, 7, 9,
56, 114, 124, 86, 62, 32, 20, 8, 10,
T(3,1) = 2 because there are 2 monic irreducible polynomials of degree 3 in F_2[x]: 1 + x^2 + x^3, 1 + x + x^3.
T(3,2) = 2 because there are 2 such polynomials that can be factored into exactly 2 irreducible factors: (1 + x) (1 + x + x^2), x (1 + x + x^2).
T(3,3) = 4 because there are 4 such polynomials that can be factored into exactly 3 irreducible factors: x^3, x^2 (1 + x), x (1 + x)^2, (1 + x)^3.


MATHEMATICA

nn = 12; b =Table[1/n Sum[MoebiusMu[n/d] 2^d, {d, Divisors[n]}], {n, 1, nn}]; Map[Select[#, # > 0 &] &, Drop[CoefficientList[Series[Product[Sum[y^i x^(k*i), {i, 0, nn}]^b[[k]], {k, 1, nn}], {x, 0, nn}], {x, y}], 1]] // Grid


CROSSREFS

Sequence in context: A141157 A137948 A210553 * A208906 A120933 A064134
Adjacent sequences: A269453 A269454 A269455 * A269457 A269458 A269459


KEYWORD

nonn,tabl


AUTHOR

Geoffrey Critzer, Feb 27 2016


STATUS

approved



