How many degree $k$, monic polynomials factor completely in $\mathbb{Z}/p\mathbb{Z}$?

Solution 1:

There is a bijection: $$\{\text{monic polynomials }f \text{ of degree $k$ which split completely}\}\to\{\text{multisets of size $k$, consisting of elements of }\mathbb Z/p\},$$ sending $f$ to the set of solutions to $f(x)=0$, which all lie in $\mathbb Z/p$ due to our assumption that $f$ splits into linear factors. In the other direction, take a multiset $S$ to the polynomial $\prod_{\alpha\in S}(x-\alpha)$. [Here, a multiset is a set with multiplicity.]

The number of such multisets is ${k+p-1\choose p-1}$—imagine having $k$ objects in a line, and putting $p-1$ dividers into them to make $p$ possibly empty groups. We can instead think about $k+p$ objects, and putting $p-1$ dividers, where we require the groups to be nonempty. There are $k+p-1$ places to put the dividers, so the total number is ${k+p-1\choose p-1}$.

Alternatively, consider the coefficient of $x^k$ in the generating function $(1+x+x^2+\dots)^p=\frac1{(1-x)^p}$. The formula for this is proved here.