This is a [question](https://math.stackexchange.com/questions/29272/counting-some-vanishing-polynomials-in-mathbbz-nx) I asked on Math.SE and got only a partial answer. I hope I will have better chances here. 


Given the ring of polynomials $\mathbb{Z}\_n[X]$, consider $$\mathbb{P}\_n = \lbrace a\_0 +a\_1x+a\_2x^2+\cdots+a\_{n-1}x^{n-1}| a\_i \in \mathbb{Z}\_n \rbrace,$$ i.e. 
$\mathbb{P}\_n$ is the set of all polynomials in $\mathbb{Z}\_n[X]$ with exponents in $\mathbb{Z}\_n$.


So, $\mathbb{P}\_2 = \lbrace 0,1,x,1+x \rbrace ,$ 


$$\mathbb{P}\_3 = \lbrace 0, x^2, 2x^2, x, x+x^2, x+2x^2, 2x, 2x+x^2, 2x+2x^2, 1, 1+x^2, 1+2x^2, 1+x \rbrace \cup $$ 


$$ \lbrace 1+x+x^2, 1+x+2x^2, 1+2x, 1+2x+2x^2, 2, 2+x^2, 2+2x^2, 2+x, 2+x+x^2 \rbrace \cup $$ 


$$ \lbrace 2+x+2x^2, 2+2x, 2+2x+x^2, 2+2x+2x^2 \rbrace $$ 


The above ordering of the elements is based on the coefficient coordinates pattern: $(0,0,0), (0,0,1),(0,0,2), (0,1,0), (0,1,1), (0,1,2), \cdots, (2,2,0), (2,2,1), (2,2,2).$


Clearly, $\mathbb{P}\_n$ has $n^n$ elements. I am counting the number of polynomials in $\mathbb{P}\_n$ that vanish in $\mathbb{Z}\_n$. Let's denote the count for $\mathbb{P}\_n$ by $r\_n$ ($r$ loosely stands for 'reducible'). Then, $r\_2 = 3, r\_3 = 19, \cdots$ It is very early to guess the growth of $r\_n$ or its primality but I would like to know if there is any theorem that would help to count or reduce the number of polynomials I should check.


Some work: 


1. Since $\mathbb{Z}\_n \subset \mathbb{Z}\_n[X]$, $r\_n \leq n^n - (n-1)$. (there are $n-1$ nonzero elements)
2. There are $n^{n-1}$ polynomials with zero constant term and there are $n-1$ polynomials of degree $1$ with nonzero constant term all of which vanish for some $x$ in $\mathbb{Z}\_n$. Hence $n^{n-1} + (n-1) \leq r\_n$. This is not a good bound as it is far less than $n^n$ for large $n$.



Counting some polynomials that have a zero in $\mathbb{Z}_n[X]$
I think there's a simple answer when $n$ is prime. Count instead the polynomials that don't have a zero. Such a polynomial must map $\lbrace0,1,\dots,n-1\rbrace$ to $\lbrace1,\dots,n-1\rbrace$. There are $(n-1)^n$ such maps. But each of those maps corresponds to a unique polynomial, since Lagrange interpolation works over a field. So the number you are looking for is $n^n-(n-1)^n$. 


