A306945 -id:A306945 - cp's OEIS frontend

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

Geoffrey Critzer, Feb 27 2016

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]

			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.

Alois P. Heinz, Rows n = 1..200, flattened
Daniel Panario, Random Polynomials over Finite Fields: Statistics and Algorithms, 2013.

Cf. A001037, A306945.

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

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

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

A329721 Irregular 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 distinct factors in its unique factorization into irreducible polynomials.

Original entry on oeis.org

2, 3, 1, 4, 4, 6, 9, 1, 8, 20, 4, 14, 35, 15, 20, 70, 36, 2, 36, 122, 90, 8, 60, 226, 196, 30, 108, 410, 414, 91, 1, 188, 762, 848, 242, 8, 352, 1390, 1719, 601, 34, 632, 2616, 3406, 1416, 122, 1182, 4879, 6739, 3207, 374, 3, 2192, 9196, 13274, 7026, 1062, 18

Offset: 1

Geoffrey Critzer, Nov 30 2019

Observed row lengths are 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, ...

			    2;
    3,   1;
    4,   4;
    6,   9,   1;
    8,  20,   4;
   14,  35,  15;
   20,  70,  36,  2;
   36, 122,  90,  8;
   60, 226, 196, 30;
  108, 410, 414, 91, 1;
  ...
T(5,3) = 4 because we have: x(x+1)(x^3+x+1), x(x+1)(x^3 +x^2+1), x^2(x+1)(x^2+x+1), x(x+1)^2(x^2+x+1).

Cf. A306945, A269456.
Row sums give A000079.
Column k=1 gives A000031.

nn = 10; a = Table[1/m Sum[MoebiusMu[m/d] 2^d, {d, Divisors[m]}], {m, 1,
   nn}]; Grid[Map[Select[#, # > 0 &] &, Drop[CoefficientList[Series[Product[(u/(1 -  z^m ) - u + 1)^a[[m]], {m, 1, nn}], {z, 0,nn}], {z, u}], 1]]]

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula