**What are the odds two uniformly chosen elements of S\_n span the whole group (or just the alternating group)?** Mathematica experements suggest those odds approach 1 - this might have been proven a long time ago. How likely is it to get the alternating group or something much smaller?


Also, **how can you *efficiently* find the size of the subgroup $\langle a,b\rangle$ in S\_n ?** My crude tests consists of randomly multiplying the two permutations and seeing how many different elements you get. Maybe there's a more efficient way to generate all the elements spanned by two permutation. 


---


You *can* generate the whole permutation group using a swap (12) and a shift (12...n). I wonder if all two element generating sets are conjugate to this.



What are the odds two permutations in S_n do NOT generate the whole group?
The probability of generation of $A\_n$ or $S\_n$ by two random permutations is $1 - 1/n - O(1/n^2)$. The $1/n$ term comes from both permutations having the same fixed point. This is a classical result of L. Babai: The probability of generating the symmetric group, Journal of Combinatorial Theory, Series A, 1989. Warning: it uses the classification of finite simple groups. 


For asymptotics for general simple groups, see [this paper](http://www.springerlink.com/content/r32065tp23lu7847/) by Liebeck and Shalev, and a recent [short survey](http://www.emis.ams.org/journals/DMJDMV/xvol-icm/02/Shalev.MAN.ps.gz) by Shalev. 


