login
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.
3

%I #33 May 28 2019 11:59:31

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

%T 63,57,47,26,17,7,9,56,114,124,86,62,32,20,8,10,99,226,234,191,116,77,

%U 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

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

%C Column 1 is A001037.

%C Row sums are 2^n.

%C T(n,k) is the number of length-n binary words having k factors in their standard (Chen, Fox, Lyndon)-factorization. [_Joerg Arndt_, Nov 05 2017]

%H Alois P. Heinz, <a href="/A269456/b269456.txt">Rows n = 1..200, flattened</a>

%H Daniel Panario, <a href="http://www.stat.purdue.edu/~mdw/ChapterIntroductions/PolynomialsDanielPanario.pdf">Random Polynomials over Finite Fields: Statistics and Algorithms</a>, 2013.

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

%e Triangular array T(n,k) begins:

%e 2;

%e 1, 3;

%e 2, 2, 4;

%e 3, 5, 3, 5;

%e 6, 8, 8, 4, 6;

%e 9, 18, 14, 11, 5, 7;

%e 18, 30, 32, 20, 14, 6, 8;

%e 30, 63, 57, 47, 26, 17, 7, 9;

%e 56, 114, 124, 86, 62, 32, 20, 8, 10;

%e ...

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

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

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

%p with(numtheory):

%p g:= proc(n) option remember; `if`(n=0, 1,

%p add(mobius(n/d)*2^d, d=divisors(n))/n)

%p end:

%p b:= proc(n, i) option remember; expand(`if`(n=0, x^n, `if`(i<1, 0,

%p add(binomial(g(i)+j-1, j)*b(n-i*j, i-1)*x^j, j=0..n/i))))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):

%p seq(T(n), n=1..14); # _Alois P. Heinz_, May 28 2019

%t 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

%Y Cf. A001037, A306945.

%K nonn,tabl

%O 1,1

%A _Geoffrey Critzer_, Feb 27 2016