The distribution of values of polynomials over a finite field (Q917600)

For a given polynomial f(X) of \({\mathbb{F}}_ q[X]\), the polynomial ring in X over a finite field \({\mathbb{F}}_ q\) with q elements, let V(f) denote the number of distinct values assumed by f(X) in \({\mathbb{F}}_ q\). Denote by \(V_ n(t)\) the number of monic polynomials \(f\in {\mathbb{F}}_ q[X]\) of degree t with \(V(f)=n\), and by \(V^*_ n(t)\) the number of all polynomials \(f\in {\mathbb{F}}_ q[X]\) of degree \(\leq t\) with \(V(f)=n\). The authors prove that one has, for \(t\geq q\), \(1\leq n\leq q\), \[ V_ n(t)=\left( \begin{matrix} q\\ n\end{matrix} \right)n!\quad S(q,n)q^{t-q}, \] and, for \(t\geq q-1\), \(1\leq n\leq q\), \[ V^*_ n(t)=\left( \begin{matrix} q\\ n\end{matrix} \right)n!\quad S(q,n)q^{t-q+1}, \] where S(q,n) denotes a Stirling number of the second kind. The variance of V(f) for monic polynomials f of degree t about the mean is also determined explicitly.