most recent 30 from http://mathoverflow.net 2013-06-19T04:44:55Z http://mathoverflow.net/feeds/question/34591 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34591/probability-of-generating-the-symmetric-group Ryan Thorngren 2010-08-05T08:22:10Z 2010-08-05T10:07:12Z

<p>The statement is simple:</p> <p>What is the probability that a set of n-1 transpositions generates the symmetric group, $S_n$?</p> <p>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.</p>

http://mathoverflow.net/questions/34591/probability-of-generating-the-symmetric-group/34594#34594 Roland Bacher 2010-08-05T08:37:13Z 2010-08-05T10:07:12Z

<p>A solution (assuming that all transpositions are distinct and are choosen uniformly among all ${n\choose 2}$ possible transpositions) can be given as follows:</p> <p>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. </p> <p>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}}$.</p> <p>If repetitions are allowed, one gets $n^{n-2}/{{n\choose 2}+n-2\choose n-1}$ (assuming uniform probability for all distinct multisets).</p>