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.



Probability of generating the symmetric group
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).


