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.
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
Offset: 1
Examples
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.
Links
- Alois P. Heinz, Rows n = 1..200, flattened
- Daniel Panario, Random Polynomials over Finite Fields: Statistics and Algorithms, 2013.
Programs
-
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
Formula
G.f.: Product_{k>0} 1/(1 - y*x^k)^A001037(k).
Comments