Probability that k randomly drawn permutations can be arranged to compose to the identity

Question

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?

Answer 1

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.