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

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?

• 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. Jul 5 at 5:53
• 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$. Jul 5 at 10:10
• @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!}$. Jul 5 at 11:50
• @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. 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.

• 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? Jul 5 at 21:28
• 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...). Jul 6 at 10:31