3
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 5, 2010 at 8:31
  • $\begingroup$ 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) $\endgroup$ Aug 5, 2010 at 11:42
  • 1
    $\begingroup$ I also remember that this "open problem" was one of the questions of the university entrance examination of a friend of mine. $\endgroup$
    – Alekk
    Aug 5, 2010 at 12:06
  • $\begingroup$ So I thought as well. I wonder what the actual statement was, or whether I had dreamt it. $\endgroup$ Aug 5, 2010 at 16:29

1 Answer 1

11
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Or very roughly $\left(\frac{2}{e}\right)^n$. $\endgroup$
    – Peter Shor
    Aug 5, 2010 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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