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.

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, 63, 57, 47, 26, 17, 7, 9, 56, 114, 124, 86, 62, 32, 20, 8, 10, 99, 226, 234, 191, 116, 77, 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

Offset

1,1

Comments

Column 1 is A001037.

Row sums are 2^n.

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]

Links

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

Daniel Panario, Random Polynomials over Finite Fields: Statistics and Algorithms, 2013.

Formula

G.f.: Product_{k>0} 1/(1 - y*x^k)^A001037(k).

Example

Triangular array T(n,k) begins:
   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,  63,  57, 47, 26, 17,  7, 9;
  56, 114, 124, 86, 62, 32, 20, 8, 10;
  ...
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.
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).
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.

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-1, j)*b(n-i*j, i-1)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, May 28 2019

Mathematica

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

Crossrefs

Cf. A001037, A306945.

Sequence in context: A357213 A137948 A210553 * A208906 A120933 A209756

Adjacent sequences: A269453 A269454 A269455 * A269457 A269458 A269459

Keyword

nonn,tabl

Author

Geoffrey Critzer, Feb 27 2016

Status

approved