How many completely reducible polynomials of degree $n$ are there in $\mathbb{F}_p$?

Question

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:

1. "Counting Irreducible Polynomials"
2. 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$.

Answer 1

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.

Answer 2

Let's start with the fact that we're working in $\mathbb{F}_p$. There are $p$ different elements, each of which we can call $a$ to create a linear factor $x-a$.

Next, we want to create a polynomial using only these linear factors. We want to create a size $n$ polynomial, and we will use exactly $n$ of our linear factors with repetition allowed.

This is precisely the "stars-and-bars" problem from combinatorics. We have $p$ different locations, which are separated using $p-1$ bars. Then we place $n$ stars into whichever locations we like, and we can place more than one in each location. For example, if we have $p=5$ locations and an $n=3$ degree polynomial, one possible solution is:

$$ | \star \star || \star |$$

You can see more on this at Wikipedia's "Stars and bars (combinatorics)" page

The result is

$$\binom{n + p - 1}{n} \text { or } \binom{n + p - 1}{p-1}$$