IMC 2009 · Day 2 · P9

Note that both of our polynomials are bijective functions on $\mathbb{F}_p$: $f_1(x) = x + 1$ is the cycle $0 \to 1 \to 2 \to \dots \to (p-1) \to 0$ and $f_2(x) = x^{p-2} + x^{p-3} + \dots + x^2 + 2x + 1$ is the transposition $0 \leftrightarrow 1$ (this follows from the formula $f_2(x) = \frac{x^{p-1} - 1}{x - 1} + x$ and Fermat's little theorem). So any composition formed from them is also a bijection, and reduction modulo $x^p - x$ does not change the evaluation in $\mathbb{F}_p$. Also note that the transposition and the cycle generate the symmetric group ($f_1^k \circ f_2 \circ f_1^{p-k}$ is the transposition $k \leftrightarrow (k+1)$, and transpositions of consecutive elements clearly generate $S_p$), so we get all $p!$ permutations of the elements of $\mathbb{F}_p$.

The set $W$ only contains polynomials of degree at most $p - 1$. This means that two distinct elements of $W$ cannot represent the same permutation. So $W$ must contain those polynomials of degree at most $p - 1$ which permute the elements of $\mathbb{F}_p$. By minimality, $W$ has exactly these $p!$ elements.