  In this paper we study the average $\NL_{2\alpha}$-norm over $T$-polynomials,
where $\alpha$ is a positive integer. More precisely, we present an explicit
formula for the average $\NL_{2\alpha}$-norm over all the polynomials of degree
exactly $n$ with coefficients in $T$, where $T$ is a finite set of complex
numbers, $\alpha$ is a positive integer, and $n\geq0$. In particular, we give a
complete answer for the cases of Littlewood polynomials and polynomials of a
given height. As a consequence, we derive all the previously known results for
this kind of problems, as well as many new results.
