Consider the symmetric group $S_n$ under the uniform distribution. For integer $k > 1$, suppose we draw $k$ elements $s_1, \dots, s_k$ independently at random. What is the probability that there exists at least one rearrangement of the $s_i$ that composes to the identity?

  • 4
    $\begingroup$ For any fixed order, the product is also a uniform random permutation. So the expected number of arrangements equal to the identity is $k!/n!$. However the probability cannot exceed $1/2$ no matter how large $k$ is (think parity). I think this problem has been studied; hopefully someone will know it. $\endgroup$ Jul 5 at 5:53
  • 1
    $\begingroup$ The probability is given by $1/n!$ for $k=1$ and $2$ and by $\frac{2\cdot n!-p(n)}{(n!)^2}$ (where $p(n)$ is the partition function) for $k=3$. $\endgroup$ Jul 5 at 10:10
  • $\begingroup$ @BrendanMcKay: Note that if $x_1\ldots x_k=1$ then any cyclic rearrangment has product $1$ as well. Hence I think the assympotics for $k$ fixed and $n$ large is actually $\frac{(k-1)!}{n!}$. $\endgroup$ Jul 5 at 11:50
  • $\begingroup$ @KasperAndersen That's a good observation, but it has no bearing on the expectation of the number of arrangements which is $k!/n!$. Your expression is the expectation of the number of arrangements modulo circular shift. $\endgroup$ Jul 5 at 12:05

Only a partial answer, which however is too long for a comment: Let $p_{n,k}$ denote the given probability. Then we have

(1) $p_{n,1} = p_{n,2} = \frac{1}{n!}$, $p_{n,3} = \frac{2\cdot n!-p(n)}{(n!)^2}$.

(2) $p_{1,k}=1$, $p_{2,k}=\frac{1}{2}$.

(3) $\frac{1}{n!}\leq p_{n,k}\leq \frac{(k-1)!}{n!}$.

(4) For $k$ fixed, most likely $p_{n,k}\sim \frac{(k-1)!}{n!}$ for large $n$.

(5) $p_{3,4} = \frac{77}{216}$, $p_{3,5} = \frac{139}{324}$, $p_{3,6} = \frac{101}{216}$, $p_{4,4} = \frac{35}{216}$, $p_{4,5} = \frac{3257}{10368}$ and $p_{5,4} = \frac{9533}{216000}$.

Clearly $p_{n,1}=\frac{1}{n!}$ and for $k\geq 2$ \begin{equation*} p_{n,k} = \frac{1}{(n!)^k} \sum_{x_1, \ldots, x_{k-1}\in \Sigma_n} f(x_1, \ldots, x_{k-1}) \end{equation*} where $f(x_1, \ldots, x_{k-1})$ denotes the number of elements $x_k$ in the symmetric group $\Sigma_n$ such that $x_{\sigma(1)} x_{\sigma(2)} \ldots x_{\sigma(k)}=1$ for some rearrangement $\sigma\in \Sigma_k$. This equation is equivalent to $x_k^{-1} = x_{\tau(1)} x_{\tau(2)} \ldots x_{\tau(k-1)}=1$ for some $\tau\in \Sigma_{k-1}$, i.e. $x_k$ should be the inverse of some rearrangement of the product $x_1 x_2\ldots x_{k-1}$. Since the number of rearrangements is between $1$ and $(k-1)!$ we obtain (3) and (1) for $k=1$, $2$. If $n\leq 2$, $\Sigma_n$ is abelian so there is exactly $1$ rearrangement, proving (2). Moreover for generic elements $x_1, \ldots, x_{k-1}$ we have $f(x_1, \ldots, x_{k-1}) = (k-1)!$ indicating why (4) should hold. (I havent written down the details, hence the most likely above). Finally consider $p_{n,3} = \frac{1}{(n!)^3} \sum_{x_1, x_2\in \Sigma_n} f(x_1,x_2)$. Here $f(x_1,x_2)$ equals $1$ if $x_1x_2=x_2 x_1$ and $2$ otherwise. Thus, with $X = \{ x,y\in \Sigma_n | xy=yx\}$ we have $p_{n,3} = \frac{1}{(n!)^3} \left(1\cdot |X| + 2\cdot ((n!)^2-|X|)\right)$. Note that \begin{equation*} |X| = \sum_{x\in \Sigma_n} |C_G(x)| = \sum_{x\in \Sigma_n} \frac{|\Sigma_n|}{|x^{\Sigma_n}|}, \end{equation*} where $x^{\Sigma_n}$ denotes the conjugacy class of $x$. The last sum clearly equals $n!$ times the number of conjugacy classes in $\Sigma_n$, i.e. $n! p(n)$. Plugging this in gives the desired formula for $p_{n,3}$ proving the last part of (1). Finally, point (5) was obtained by direct computer calculation.

  • $\begingroup$ Impressive analysis! Do you think there is a chance for a “closed form” answer? Say, in terms of the partition function and other known combinatorial objects. Or are asymptotics maybe the best one can hope for? $\endgroup$
    – Nate River
    Jul 5 at 21:28
  • $\begingroup$ I'm not sure if there is a closed form answer. One natural step would be to compute $p_{n,4}$ which would involve counting solutions to equations in $\Sigma_n$ like $xyz=xzy$ (which is easy) or $xyz=zxy$ (which looks hard...). $\endgroup$ Jul 6 at 10:31

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.