Probability of generating the symmetric group - MathOverflow 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 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 Answer by Roland Bacher for Probability of generating the symmetric group 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>