login
Number of permutation polynomials (mod n).
1

%I #28 Jul 31 2022 20:17:28

%S 1,2,6,8,120,12,5040,128,1296,240,39916800,48,6227020800,10080,720,

%T 8192,355687428096000,2592,121645100408832000,960,30240,79833600,

%U 25852016738884976640000,768,384000000,12454041600,25509168,40320,8841761993739701954543616000000,1440

%N Number of permutation polynomials (mod n).

%C a(n) is the number of unique bijective functions from Z/nZ to itself induced by polynomials over Z/nZ.

%H Kenneth G. Hawes, <a href="/A329812/b329812.txt">Table of n, a(n) for n = 1..456</a>

%H Kenneth G. Hawes, <a href="/A329812/a329812_1.txt">SageMath program for generating the sequence</a>

%H Kenneth G. Hawes, <a href="/A329812/a329812_2.txt">Additional terms including those with more than 1000 digits, n = 1..5000</a>

%H G. Keller and F. R. Olson, <a href="https://doi.org/10.1215/S0012-7094-68-03589-8">Counting polynomial function (mod p^n)</a>, Duke Mathematical Journal, 35 (1968), 835-838.

%F a(n) = Product_{i=1..r} a(p_i^k_i) for n having the unique prime factorization n = Product_{i=1..r} p_i^k_i.

%F a(p^k) = p! if k=1, a(p^k) = p!*(p-1)^p*p^p if k=2, and a(p^k) = p!*(p-1)^p*p^(p+f(p,k)) if k>2, where f(p,k) = Sum_{i=3..k} A002034(p^i).

%e For n=3, since it is a prime number, a(3) = 3! = 6.

%e For n=4=2^2, a(4) = 2!*(2-1)^2*2^2 = 8.

%Y Formula involves the Kempner function A002034.

%K nonn,mult

%O 1,2

%A _Kenneth G. Hawes_, Nov 21 2019