cp's OEIS Frontend

A306945 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 squarefree factors in its unique factorization into irreducible polynomials.

%I A306945 #52 Dec 01 2019 17:07:20
%S A306945 2,1,1,2,2,3,4,1,6,8,2,9,16,7,18,30,14,2,30,60,34,4,56,114,72,14,99,
%T A306945 220,156,36,1,186,422,320,90,6,335,817,671,207,18,630,1564,1364,484,
%U A306945 54,1161,3023,2787,1070,148,3,2182,5818,5624,2362,386,12,4080,11240,11357,5095,947,49
%N A306945 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 squarefree factors in its unique factorization into irreducible polynomials.
%C A306945 T(n,k) is also the number of binary words of length n whose Lyndon factorization is strict, i.e., it contains exactly k factors of distinct Lyndon words.
%H A306945 Alois P. Heinz, <a href="/A306945/b306945.txt">Rows n = 1..500, flattened</a>
%F A306945 G.f.: Product_{k>=1} (1 + y*x)^A001037(k).
%e A306945 Triangular array T(n,k) begins:
%e A306945    2;
%e A306945    1,   1;
%e A306945    2,   2;
%e A306945    3,   4,   1;
%e A306945    6,   8,   2;
%e A306945    9,  16,   7;
%e A306945   18,  30,  14,  2;
%e A306945   30,  60,  34,  4;
%e A306945   56, 114,  72, 14;
%e A306945   99, 220, 156, 36, 1;
%e A306945   ...
%p A306945 with(numtheory):
%p A306945 g:= proc(n) option remember; `if`(n=0, 1,
%p A306945       add(mobius(n/d)*2^d, d=divisors(n))/n)
%p A306945     end:
%p A306945 b:= proc(n, i) option remember; expand(`if`(n=0, x^n, `if`(i<1, 0,
%p A306945       add(binomial(g(i), j)*b(n-i*j, i-1)*x^j, j=0..n/i))))
%p A306945     end:
%p A306945 T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n$2)):
%p A306945 seq(T(n), n=1..20);  # _Alois P. Heinz_, May 28 2019
%t A306945 nn = 16; a = Table[1/n Sum[2^d MoebiusMu[n/d], {d, Divisors[n]}], {n, 1, nn}]; Map[Select[#, # > 0 &] &, Drop[CoefficientList[
%t A306945     Series[Product[ (1 + u z^k)^a[[k]], {k, 1, nn}], {z, 0, nn}], {z, u}], 1]] // Grid
%Y A306945 Column k=1 gives A001037.
%Y A306945 Row sums give A090129(n+1).
%Y A306945 Cf. A269456.
%K A306945 nonn,look,tabf
%O A306945 1,1
%A A306945 _Geoffrey Critzer_, Mar 25 2019