Timeline for Probability that k randomly drawn permutations can be arranged to compose to the identity
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 6, 2021 at 4:47 | vote | accept | Nate River | ||
| Jul 5, 2021 at 20:19 | answer | added | Kasper Andersen | timeline score: 3 | |
| Jul 5, 2021 at 12:05 | comment | added | Brendan McKay | @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, 2021 at 11:50 | comment | added | Kasper Andersen | @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, 2021 at 10:10 | comment | added | Kasper Andersen | 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, 2021 at 5:53 | comment | added | Brendan McKay | 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, 2021 at 5:01 | history | asked | Nate River | CC BY-SA 4.0 |