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?



Probability that k randomly drawn permutations can be arranged to compose to the identity
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.


