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

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:

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$$.

• By completely reducible you mean that the polynomial can be written as a product of linear factors? Jul 12, 2022 at 19:26
• @SammyBlack: Yes. Jul 12, 2022 at 19:27
• Yes, I didn't read "completely" in your question at first, and deleted my comment. I added that word to the title of your post for clarity. Jul 12, 2022 at 19:29
• Well, how many multisets of size $n$ can you make out of $p$ elements?
– lulu
Jul 12, 2022 at 19:30
• I'm not saying anything complicated...sticking to monic polynomials for the moment, such a thing is determined by the list of its roots with multiplicity. That means, a multiset of size $n$. Then, of course, you have to multiply by the number of possible lead coefficients ($p-1$).
– lulu
Jul 12, 2022 at 19:39

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.

• I'm now seeing that people have been working this out with OP in the comments. Feel free to hold off and choose one of their answers if they post. Cheers. Jul 12, 2022 at 20:05

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}$$

• Don't forget that you need to consider the possible lead coefficients. There are $p-1$ of these, so multiply your result by $p-1$.
– lulu
Jul 12, 2022 at 20:18
• @lulu: Oh yeah, I forgot to mention that I was thinking about monic polynomials. Good point! Jul 12, 2022 at 20:20