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,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

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

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: A231561 A113297 A119985 * A234716 A357383 A181885

Adjacent sequences: A306942 A306943 A306944 * A306946 A306947 A306948

Keyword

nonn,look,tabf

Author

Geoffrey Critzer, Mar 25 2019

Status

approved