login
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.
3
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, 220, 156, 36, 1, 186, 422, 320, 90, 6, 335, 817, 671, 207, 18, 630, 1564, 1364, 484, 54, 1161, 3023, 2787, 1070, 148, 3, 2182, 5818, 5624, 2362, 386, 12, 4080, 11240, 11357, 5095, 947, 49
OFFSET
1,1
COMMENTS
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.
LINKS
FORMULA
G.f.: Product_{k>=1} (1 + y*x)^A001037(k).
EXAMPLE
Triangular array T(n,k) begins:
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, 220, 156, 36, 1;
...
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)*b(n-i*j, i-1)*x^j, j=0..n/i))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n$2)):
seq(T(n), n=1..20); # Alois P. Heinz, May 28 2019
MATHEMATICA
nn = 16; a = Table[1/n Sum[2^d MoebiusMu[n/d], {d, Divisors[n]}], {n, 1, nn}]; Map[Select[#, # > 0 &] &, Drop[CoefficientList[
Series[Product[ (1 + u z^k)^a[[k]], {k, 1, nn}], {z, 0, nn}], {z, u}], 1]] // Grid
CROSSREFS
Column k=1 gives A001037.
Row sums give A090129(n+1).
Cf. A269456.
Sequence in context: A371632 A113297 A119985 * A234716 A357383 A181885
KEYWORD
nonn,look,tabf
AUTHOR
Geoffrey Critzer, Mar 25 2019
STATUS
approved