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