Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
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 '10 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 '10 at 11:42
1  
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 '10 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 '10 at 16:29

1 Answer 1

up vote 10 down vote accepted

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

share|improve this answer
1  
Or very roughly $\left(\frac{2}{e}\right)^n$. –  Peter Shor Aug 5 '10 at 21:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.