Enumerating Permutation Polynomials I: Permutations with Non-Maximal Degree

Let be a conjugation class of permutations of a finite field _q. We consider the function N (q) defined as the number of permutations in for which the associated permutation polynomial has degree <q−2. In 1969, Wells proved a formula for N_3](q) where k] denotes the conjugation class of k-cycles. We will prove formulas for N_k](q) where k=4,5,6 and for the classes of permutations of type 2 2],3 2],4 2],3 3] and 2 2 2]. Finally in the case q=2ⁿ, we will prove a formula for the classes of permutations which are product of 2-cycles.