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