login
Square array T(n,k) = number of separable polynomials of degree <= k in Z/n[x], n>=1, k>=1, read by antidiagonals.
0

%I #13 Sep 28 2018 04:42:26

%S 1,1,3,1,5,8,1,9,20,12,1,17,56,40,24,1,33,164,144,104,24,1,65,488,544,

%T 504,100,48,1,129,1460,2112,2504,504,300,48,1,257,4376,8320,12504,

%U 2788,2064,320,72,1,513,13124,33024,62504,16104,14412,2304,540,72

%N Square array T(n,k) = number of separable polynomials of degree <= k in Z/n[x], n>=1, k>=1, read by antidiagonals.

%H Leonard Carlitz, <a href="http://www.jstor.org/stable/2371075">The arithmetic of polynomials in a Galois field</a>, Amer. J. Math., 54(1):39-50, January 1932.

%H Jason K. C. Polak, <a href="https://arxiv.org/abs/1703.07064">Counting Separable Polynomials in Z/n[x]</a>, arXiv:1703.07064 [math.RA], 2016.

%e 1, 1, 1, 1, 1, ...

%e 3, 5, 9, 17, 33, ...

%e 8, 20, 56, 164, 488, ...

%e 12, 40, 144, 544, 2112, ...

%e 24, 104, 504, 2504, 12504, ...

%e 24, 100, 504, 2788, 16104, ...

%t T[n_, k_] := With[{f = FactorInteger[n][[All, 1]]}, EulerPhi[n] n^k Times @@ (1 + 1/f^k)]; T[1, _] = 1;

%t Table[T[n-k+1, k], {n, 1, 10}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Sep 28 2018, from PARI *)

%o (PARI) T(n, k) = my(f=factor(n)); eulerphi(n)*n^k*prod(i=1, #f~, 1+1/f[i,1]^k);

%Y Cf. A007434 (1st column).

%K nonn,tabl

%O 1,3

%A _Michel Marcus_, Mar 25 2017