The number of polynomials of a given degree over a finite field with value sets of a given cardinality (Q1870027)

For a polynomial \(f\in\mathbb F_q[x]\), let \(V_f\) denote the image of \(f\) (regarded as function from \(\mathbb F_q\) to itself). The author considers the problem of determining the number \(N_q(d,k)\) of polynomials over \(\mathbb F_q\) with degree \(d\leq q-1\) and \(|V_f|=k\). By an elementary argument, he relates \(N_q(q-1,k)\) to the number of solutions \((x_1,\ldots,x_k)\) of a linear equation over \(\mathbb F_q\), with the additional restriction \(x_i\not=x_j\) for \(i\not=j\). This yields simple formulas for \(N_q(q-1,2)\) and \(N_q(d,q-1)\). The paper concludes with asymptotic estimates for the probability that a polynomial \(f\in\mathbb F_p[x]\) (\(p\) prime) with \(|V_f|=k\) has maximal degree \(p-1\).