Permutation roots
13 hours ago
- 如果一个排列 σ 存在另一个排列 τ 使得 τ² = σ，即连续两次应用 τ 的效果等价于一次应用 σ 的效果，那么 τ 称为 σ 的平方根。
- 排列可以表示为元组，复合运算通过一个先应用第二个排列的函数来实现。
- 如果排列 σ 本身是某个排列的平方，则它总是存在平方根，但可能存在多个不同的平方根。
- 一个定理指出，排列 σ 存在平方根当且仅当在其循环分解中，每个偶数长度的循环出现偶数次。
- 这一概念可以推广到排列的立方根以及更高的 k 次根。
- 随机 n 元排列存在 k 次根的概率可以通过一个包含 Mittag-Leffler 函数的无限乘积中 x^n 的系数来计算。
- 例如，10 元排列存在平方根的概率是 29/96。