置换环

结论

每次交换任意两个数，将一个排列排序。

结论 \(1\)：其最小操作数为 \(n-k\)。

结论 \(2\)：其操作方案数为 \((n-k)!\prod\limits_{i=1}^{k}\dfrac{l_i^{l_i-2}}{(l_i-1)!}\)。

其中 \(n\) 为长度，\(k\) 为置换环个数，\(l_i\) 为第 \(i\) 个置换环长度。

证明

引理：若交换的两个数在同一个置换环内，则环的个数加 \(1\)；否则，环的个数减 \(1\)。

手玩一下不难证明。于是有：将一个长为 \(l\) 的置换环拆成 \(l\) 个自环的最小操作数是 \(l-1\) 次。

那么就可以得到结论 \(1\)。

重点是结论 \(2\)。由上可知，只要每次操作的两个数在当前的同一置换环内，就可以达到这个最小数。还是考虑单个环的情况，设 \(f_i\) 表示长为 \(i\) 的置换环操作方案数，那么枚举交换的两个数在环中的距离，得到递归式 \(f_i=\dfrac{i}{2}\sum\limits_{j=1}^{i-1}f_jf_{i-j}\binom{i-2}{j-1}\)。

不过这个式子没啥卵用，主要用于打表，我们考虑从意义上求解 \(f_i\)。

正难则反，拆环不好做我们变成合并环，从全是自环的局面开始，不断将两个点的所属集合合并，最终变成一个集合。

我们考虑一棵 \(n-1\) 条边的树，我们再任意钦定一个顺序，按这个顺序合并一定是合法的，即最终变成了一个大环，其方案数总数是 \(n^{n-2}(n-1)!\)，而最终局面是一个长为 \(n\) 的环，有 \((n-1)!\) 种。显然，这 \((n-1)!\) 种环的 \(f\) 均相同，于是答案就是 \(n^{n-2}\) 种方案了。

对于多个环的排列，将第 \(i\) 个环的操作视作 类别 \(i\)，答案即为将所有 \(l_i-1\) 个 \(i\) 全排列的方案数，易证结论 \(2\)。