Is there any known lower bound for the number of polynomia functions over a finite field with fixed number of variables? Say we have a finite field $K$ of size $q$, is there an easy lower bound for the number of distinct polynomial functions in $K[x_1,x_2,\ldots,x_n]$? What about if we specifically fix the degree $d$, so that we only count those polynomial functions of degree $d$ on $n$ variables?
 A: The total number of distinct polynomial functions is $q^{q^n}$, also equal to the total number of functions $f:K^n\to K$ (proof at end). Every such polynomial is equivalent to one where all variables have degree less than $q$, because of the identity $x^q=x$. As long as we restrict our attention to polynomials with this degree bound, then two polynomials represent the same function if and only if they have the same coefficients; indeed, there are $q^{q^n}$ polynomials where every variable has degree at most $q$, and these represent all functions, so they must all be distinct functions. Therefore, you can count polynomials of degree $d$ by counting the number of representations with degree $d$.
Let $m(n,q,d)$ be the number of monomials with degree at most $d$ where all powers of all variables are at most $q$. Then the number of polynomials of degree exactly $d$ is
$$
q^{m(n,q,d)}-q^{m(n,q,d-1)}
$$
Furthermore, $m(n,q,d)$ is equal to the number of nonnegative integers solutions to the equation $a_1+\dots+a_n\le d$. Using a standard stars-and-bars/inclusion-exclusion argument, we can show
$$
m(n,q,d)=\sum_{k\ge 0}(-1)^k\binom{n}k\binom{n+d-qk}{d-qk}
$$

Proof: To prove there are $q^{q^n}$ polynomial functions, you need to show every function can be represented as a polynomial, which we do now. First, given any vector $v=(v_1,\dots,v_n)\in K^n$, we will make a polynomial $p_v(x_1,\dots,x_n)$ whose value is $1$ when $(x_1,\dots,x_n)=(v_1,\dots,v_n)$, and zero otherwise. Then, any arbitrary function can be made using a linear combination of such polynomials. To do this, for each $i\in \{1,\dots,n\}$, let
$$
g_i(x_1,\dots,x_n)=\prod_{a\in K\setminus \{v_i\}}\frac{x_i-a}{v_i-a}
$$
Note that $g_i(x_1,\dots,x_n)$ is $1$ when $x_i=v_i$, and zero otherwise. Therefore, the desired polynomial is
$$
p_v(x_1,\dots,x_n)=\prod_{i=1}^ng_i(x_1,\dots,x_n)
$$
A: The number of polynomials of at least degree $d$ is the number of homogeneous polynomials of degree $d$ with $n$ variables.
There are ${n+d\choose n}$ monomials of degree $d$, so the number of polynomials at most degree $d$ with $n$ variables is $$q^{n+d\choose n}$$
