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.

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

Author

Geoffrey Critzer, Mar 25 2019

Keywords

• nonn
• look
• tabf

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.

Examples

			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;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..500, flattened

Crossrefs

Column k=1 gives A001037.

Row sums give A090129(n+1).

Cf. A269456.

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)*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

Formula

G.f.: Product_{k>=1} (1 + y*x)^A001037(k).