Probability of generating the symmetric group The statement is simple:
What is the probability that a set of n-1 transpositions generates the symmetric group, $S_n$?
The motivation is that I remembered reading that this was an open problem somewhere on the internet, and then I solved it. I'm curious to see other people's solutions, because I think it's a nice problem, and don't quite believe that it is hard enough to be open.
 A: A solution (assuming that all transpositions are distinct and are choosen uniformly among all
${n\choose 2}$ possible transpositions) can be given as follows:
A set of $n-1$ transpositions $(a_1,b_1),\dots,(a_{n-1},b_{n-1})$ on the set $\lbrace 1,\dots,n\rbrace$ generates the whole symmetric group
of $\{1,\dots,n\}$ if and only if the graph with vertices $\lbrace 1,\dots,n\rbrace$ and edges $\lbrace a_i,b_i\rbrace$ is a tree. 
The probability to generate $S_n$ is thus the same as the probability to get a tree with $n$ vertices $V$ when choosing randomly
$n-1$ edges with endpoints in $V$.
By Cayley's theorem, there are $n^{n-2}$ different trees with vertices $\lbrace 1,\dots,n\rbrace$.
Since there are ${{n\choose 2}\choose n-1}$ different graphs with $n-1$ edges and vertices $\{1,\dots,n\}$, the 
probability is given by 
$n^{n-2}/{{{n\choose 2}\choose n-1}}$.
If repetitions are allowed, one gets $n^{n-2}/{{n\choose  2}+n-2\choose n-1}$ (assuming uniform probability for all distinct multisets).
