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.

Improve this question
$\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$
    – Victor Protsak
    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$
    – Pietro Majer
    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$
    – Ryan Thorngren
    Aug 5, 2010 at 16:29

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Or very roughly $\left(\frac{2}{e}\right)^n$. $\endgroup$
    – Peter Shor
    Aug 5, 2010 at 21:53
  • $\begingroup$ In the case, we take a random subset $A$ of $S_n$ with probability $p$, what is the probability which $x\in A$ condition on a number of transpositions $(a_1,b_1),\cdots, (a_m,b_m)$ with $m$ is fixed? Thanks. $\endgroup$
    – user52523
    May 14, 2023 at 16:13
  • 1
    $\begingroup$ @user52523 I do not understand your question. Could you reformulate it unambigously? $\endgroup$
    – Roland Bacher
    May 15, 2023 at 12:57
  • 1
    $\begingroup$ @user52523 Sorry, your question is still not clear : Are $(ai,b_i)$ transpositions or simply elements of $\lbrace 1,\ldots,n\rbrace$? How do you choose $\sigma$ (uniformly?) etc? I can not read your mind and therefore your question has to be absolutely clear. $\endgroup$
    – Roland Bacher
    May 17, 2023 at 7:24
  • 1
    $\begingroup$ Sorry, I give up. $\endgroup$
    – Roland Bacher
    May 17, 2023 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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