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$– Brendan McKayJul 5, 2021 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$– Kasper AndersenJul 5, 2021 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{(k1)!}{n!}$. $\endgroup$– Kasper AndersenJul 5, 2021 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$– Brendan McKayJul 5, 2021 at 12:05
1 Answer
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{(k1)!}{n!}$.
(4) For $k$ fixed, most likely $p_{n,k}\sim \frac{(k1)!}{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_{k1}\in \Sigma_n} f(x_1, \ldots, x_{k1}) \end{equation*} where $f(x_1, \ldots, x_{k1})$ 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(k1)}=1$ for some $\tau\in \Sigma_{k1}$, i.e. $x_k$ should be the inverse of some rearrangement of the product $x_1 x_2\ldots x_{k1}$. Since the number of rearrangements is between $1$ and $(k1)!$ 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_{k1}$ we have $f(x_1, \ldots, x_{k1}) = (k1)!$ 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!)^2X)\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$ Jul 5, 2021 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, 2021 at 10:31