A356582 T(n,k) is the number of degree n polynomials in GF_2[x] that have exactly k linear factors in their prime factorization when the factors are counted with multiplicity, n >= 0, 0 <= k <= n. Triangular array read by rows.

1, 0, 2, 1, 0, 3, 2, 2, 0, 4, 4, 4, 3, 0, 5, 8, 8, 6, 4, 0, 6, 16, 16, 12, 8, 5, 0, 7, 32, 32, 24, 16, 10, 6, 0, 8, 64, 64, 48, 32, 20, 12, 7, 0, 9, 128, 128, 96, 64, 40, 24, 14, 8, 0, 10, 256, 256, 192, 128, 80, 48, 28, 16, 9, 0, 11

Offset

0,3

Links

Table of n, a(n) for n=0..65.

A. Knopfmacher and J. Knopfmacher, Counting irreducible factors of polynomials over a finite field, Discrete Math, 112 (1993), pp. 103-118.

Formula

G.f.: (1/(1-y*x)^2)*Product_{i>=2} 1/(1-x^i)^A001037(i).

Explicit formula given in Knopfmacher link.

Example

   1;
   0,  2;
   1,  0,  3;
   2,  2,  0,  4;
   4,  4,  3,  0,  5;
   8,  8,  6,  4,  0, 6;
  16, 16, 12,  8,  5, 0, 7;
  32, 32, 24, 16, 10, 6, 0, 8;

Mathematica

nn = 10; i[q_, r_] := 1/r Sum[MoebiusMu[r/d] q^d, {d, Divisors[r]}];
M[q_, n_, k_, r_] := If[0 <= k <= Floor[n/r - i[q, r]], Binomial[i[q, r] + k - 1, k]*q^(n - k*r) (1 - 1/q^r)^i[q, r], Binomial[i[q, r] + k - 1, k]* q^(n - k*r) Sum[(-1)^m Binomial[i[q, r], m] q^(-r m), {m, 0, Floor[n/r] - k}]]; Table[Table[M[2, n, k, 1], {k, 0, n}], {n, 0, nn}] // Grid

Crossrefs

Cf. A001037.

Sequence in context: A263405 A106384 A333119 * A320839 A094314 A353632

Adjacent sequences: A356579 A356580 A356581 * A356583 A356584 A356585

Keyword

nonn,tabl

Author

Geoffrey Critzer, Aug 13 2022

Status

approved