A problem of permutation group

Question

An exercise in a book of permutation groups:

Let $G \leq S_n$. If $G$ has $r$ orbits, show that $G$ can be generated by a set of at most $n-r$ elements.

I really have no idea how to prove it. Please help! Thanks!

Answer 1

Use induction on $n-r$.

The base of induction is when $n-r=0$, i.e. $G$ has $n$ orbits. In this case $G$ must be trivial, so it is generated by the empty set of elements (I follow the agreement that the empty set generates the trivial subgroup in $S_n$).

As for the transition, here is a hint. Suppose that $G$ has $r$ orbits, and the claim has already been established for groups that have $r+1$ orbits or more. Now pick an element $\alpha$ in one of the non-trivial orbits of $G$. Look at its stabiliser $$ G_\alpha = \{g \in G \,|\, g(\alpha) = g\}. $$ $G_\alpha$ has strictly more than $r$ orbits, say $r+k$. Now you can use the induction hypothesis on $G_\alpha$, which says that $G_\alpha$ can be generated by at most $n-r-k$ elements. All you need to do now is show that one can find at most $k$ elements which together with $G_\alpha$ generate all of $G$. You can do this if you look closely at orbits of $G$ and smaller orbits of $G_\alpha$.