cp's OEIS Frontend

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.

%I A269456 #33 May 28 2019 11:59:31
%S A269456 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 A269456 63,57,47,26,17,7,9,56,114,124,86,62,32,20,8,10,99,226,234,191,116,77,
%U A269456 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 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.
%C A269456 Column 1 is A001037.
%C A269456 Row sums are 2^n.
%C A269456 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 A269456 Alois P. Heinz, <a href="/A269456/b269456.txt">Rows n = 1..200, flattened</a>
%H A269456 Daniel Panario, <a href="http://www.stat.purdue.edu/~mdw/ChapterIntroductions/PolynomialsDanielPanario.pdf">Random Polynomials over Finite Fields: Statistics and Algorithms</a>, 2013.
%F A269456 G.f.: Product_{k>0} 1/(1 - y*x^k)^A001037(k).
%e A269456 Triangular array T(n,k) begins:
%e A269456    2;
%e A269456    1,   3;
%e A269456    2,   2,   4;
%e A269456    3,   5,   3,  5;
%e A269456    6,   8,   8,  4,  6;
%e A269456    9,  18,  14, 11,  5,  7;
%e A269456   18,  30,  32, 20, 14,  6,  8;
%e A269456   30,  63,  57, 47, 26, 17,  7, 9;
%e A269456   56, 114, 124, 86, 62, 32, 20, 8, 10;
%e A269456   ...
%e A269456 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 A269456 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 A269456 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 A269456 with(numtheory):
%p A269456 g:= proc(n) option remember; `if`(n=0, 1,
%p A269456       add(mobius(n/d)*2^d, d=divisors(n))/n)
%p A269456     end:
%p A269456 b:= proc(n, i) option remember; expand(`if`(n=0, x^n, `if`(i<1, 0,
%p A269456       add(binomial(g(i)+j-1, j)*b(n-i*j, i-1)*x^j, j=0..n/i))))
%p A269456     end:
%p A269456 T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
%p A269456 seq(T(n), n=1..14);  # _Alois P. Heinz_, May 28 2019
%t A269456 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 A269456 Cf. A001037, A306945.
%K A269456 nonn,tabl
%O A269456 1,1
%A A269456 _Geoffrey Critzer_, Feb 27 2016