## 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.

-
The motivation, "I remember reading that this was an open problem somewhere on the internet" does not strike one as very compelling. Isn't it true that $n-1$ transpositions, viewed as edges of a graph on $n$ vertices, generate $S_n$ if and only if the graph is a tree? So it's a question of tree enumeration. – Victor Protsak Aug 5 2010 at 8:31
Good point. How does it look like translating the bijection it terms of Pruefer sequences? (I fear it doesn't add much to the picture though) – Pietro Majer Aug 5 2010 at 11:42
I also remember that this "open problem" was one of the questions of the university entrance examination of a friend of mine. – Alekk Aug 5 2010 at 12:06
So I thought as well. I wonder what the actual statement was, or whether I had dreamt it. – Ryan Thorngren Aug 5 2010 at 16:29

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).

-
 Or very roughly $\left(\frac{2}{e}\right)^n$. – Peter Shor Aug 5 2010 at 21:53