Probability of generating the symmetric group

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

2
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

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

1 Answer

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9480321407318115, "perplexity_flag": "head"}