This problem is from Chapter 7 of Algebraic Combinatorics by Richard p. Stanley:
Let $X$ be a finite set, and let $G$ be a subgroup of the symmetric group, $S_X$. Suppose that the number of orbits of $G$ acting on $n$-colorings of $X$ is given by the polynomial: $$f(n) = \frac{1}{a} (n^p + bn^{p-2} + \cdots + (p-1)n)$$
where $p$ is prime.
Prove that $G$ is either a cyclic group or it is not a simple group (it gives the hint that a simple group only has two normal subgroups: $G$ and the identity).
So far, I have been able to show that $G$ has order $a$, $X$ has order $p$, $G$ has no transpositions, and that $G$ acts transitively on $X$.
Some of the main theorems/notes that come from this chapter are the following:
- Burnside's Lemma
- Given a group of permutations, $G$, of $X$, the number of inequivalent $n$-colorings of $X$ is:
$$\frac{1}{\#G} \sum_{\pi \in G} n^{c(\pi)}$$ where $c(\pi)$ is the number of cycles in $\pi$.
Cycle indicators and cycle index polynomials
Polya's Thorem of 1937
The number of $n$-colored necklaces of length $\ell$ (where the set of symmetries is the cyclic group) is: $$\frac{1}{\ell} \sum_{d | \ell} \phi \left( \frac{\ell}{d} \right) n^d$$ where $\phi$ is the Euler Totient Function.
The number of permutations $\pi \in S_{\ell}$ with $c_i$ cycles of length $i$ where $\sum_i ic_i = \ell$ is given by: $$\frac{ \ell}{ 1^{c_1} c_1! 2^{c_2} c_2! 3^{c_3} c_3! \cdots}$$
Some progress that I've made so far is recognizing that that in a transitive group action, the orbits induced by a normal subgruop will all have the same size. Thus, for any normal subgroup, $H$, in $G$, the orbits induced by $H \times X \rightarrow X$ will all have the same size.
I don't understand, however, how to relate this back to the polynomial that we are given. How do we prove that $G$ must have a normal subgroup (or that it is cyclic)?