A269456 -id:A269456 - cp's OEIS frontend

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

Geoffrey Critzer, Mar 25 2019

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.

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

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

Column k=1 gives A001037.
Row sums give A090129(n+1).
Cf. A269456.

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

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

G.f.: Product_{k>=1} (1 + y*x)^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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula