# How to prove a permutation group of degree n can be generated by (at most) n-1 elements?

Given a subgroup G of $S_n$. I want to prove that G can be generated by (at most) n-1 elements.

All my ideas so far seem irrelevant. A hint would be greatly appreciated.

My attempts so far: n-1 reminds me of the number of transpositions required to generate $S_n$, so I'm trying to generalize that, but with no success.

-

Jerrum's filter provides such a generating set. (it's a homework, so perhaps a link is not a completely bad answer)

-
That's a good answer. Can't believe it was given as homework because it's not related to anything we learned. It's beautiful in my opinion. – user9354 Apr 9 '11 at 14:41
seems like a tough homework :) (maybe there is some shortcut, but I have no idea) – user8268 Apr 9 '11 at 14:45
I linked to the new version of the site. I'd be interested in hearing an easy theoretical proof (suitable for homework). I've only see the algorithm. – Jack Schmidt Apr 9 '11 at 15:09
Asked the TA. Got an apology followed by an email to all students saying this Q in canceled. So unfortunately I can't provide an easy proof. Thank you very much for the help (I enjoyed the solution). – user9354 Apr 9 '11 at 16:57

You might be interested to know that Peter M. Neumann proved that, with the exception of the symmetric group of degree 3 (which requires 2 generators), every subgroup of $S_n$ can be generated by at most $n/2$ elements. This result is sharp, because (for $n$ even), the group generated by the $n/2$ transpositions $(1,2), (3,4), \ldots, (n-1,n)$ cannot be generated by fewer elements.

I don't think Neumann ever published his proof, but there is a sketch of it in Section 4 of the paper Chains of subgroups in symmetric groups" by P. Cameron, R. Solomon and A. Turull, J. Algebra 127, 340-352, 1989.

-