What do we know about the count of completely reducible polynomials modulo $p$? In other words, polynomials that factor into all linear factors and nothing of higher degree.
From this site and regarding irreducible polynomials, we have:
- "Counting Irreducible Polynomials"
- IBS's answer to "Number of monic irreducible polynomials of prime degree p over finite fields"
What we can say, if anything, about (completely or totally) reducible polynomials? More specifically, in the case where we have degree $n$ polynomials in $\mathbb{F}_p$.
Best Answer
Completely reducible monic polynomials of degree $n$ over $\mathbb{F}_p$ are in bijective correspondence with the multiset of their roots (multiplicity counts number of linear factors for each root). Factoring in terms of the elements of $\mathbb{F}_p = \{0, 1, \dots, p-1\}$, this bijection looks like \begin{align} (x - 0)^{m_0} \cdot (x - 1)^{m_1} \cdots (x - (p-1))^{m_{p-1}} \quad&\longleftrightarrow\quad \{ 0^{m_0}, 1^{m_1}, \dots, (p-1)^{m_{p-1}} \} \\ \quad&\longleftrightarrow\quad (m_0, m_1, \dots, m_{p-1}) \end{align} where each $m_i \in \mathbb{Z}_{\geq 0}$ and the total degree is $m_0 + m_1 + \cdots + m_{p-1} = n$.
Enumerating the latter (multiset coefficient) is a well-known combinatorics exercise $$ \left(\!\!\left( \begin{matrix} p \\ n \end{matrix} \right)\!\!\right) = \binom{p+n-1}{n} $$
If you want to allow any nonzero leading coefficient, then you need to multiply the answer by $(p-1)$, since any nonzero leading coefficient is possible and determines a distinct polynomial.