OFFSET
1,1
COMMENTS
Column 1 is A001037.
Row sums are 2^n.
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]
LINKS
Alois P. Heinz, Rows n = 1..200, flattened
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
Triangular array T(n,k) begins:
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.
MAPLE
with(numtheory):
g:= proc(n) option remember; `if`(n=0, 1,
add(mobius(n/d)*2^d, d=divisors(n))/n)
end:
b:= proc(n, i) option remember; expand(`if`(n=0, x^n, `if`(i<1, 0,
add(binomial(g(i)+j-1, j)*b(n-i*j, i-1)*x^j, j=0..n/i))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14); # Alois P. Heinz, May 28 2019
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
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Feb 27 2016
STATUS
approved