获取排列数

Question

我正在寻找一种算法，该算法可为我提供元素1....n的置换计数。如果我定义周期长度。

例如n := 4

<Set of cycle lengths>-> permutation count

[1,1,1,1-> 1读取长度为1的4个周期导致1个排列：1,2,3,4

[1,1,2-> 5读取2个长度为1的周期和1个长度为2的周期导致5个排列：1,2,4,3，1,4,3,2，1,3,2,4，2,1,3,4，3,2,1,4，

[2,2-> 3读取长度为2的2个周期导致3个排列：2,1,4,3，3,4,1,2，4,3,2,1

1,3-> 9读取长度为1的1个周期和长度为3的1个周期会导致9个置换1,3,2,4，1,3,4,2，1,4,2,3，2,3,1,4，2,4,3,1，3,1,2,4， 3,2,4,1，4,1,3,2，4,2,1,3，

4-> 6读取1个长度为4的周期会导致6个排列：2,3,4,1，2,4,1,3，3,1,4,2，3,4,2,1，4,1,2,3，4,3,1,2

我如何计算由周期长度组成的给定集合的排列计数？遍历所有排列不是一个选择。

Answer 1

这可以分解为：

1. 将元素划分到与每个不同周期大小的元素所需数量匹配的存储桶中的方式数量；
2. 对于每个不同的循环大小，乘以将元素均匀划分为所需循环数的唯一方式的数目；
3. 对于每个循环，乘以不同的循环顺序数

1：对于铲斗尺寸s ₁ ... s _k，得出n！/（s ₁！* ... * s _k！ ）

2：对于包含必须划分为c个循环的m个元素的存储桶，有m！/（（m / c）！^c * c！）方式

3：对于包含m个元素的循环，有（m-1）个！如果m> 1，则为不同的循环顺序，否则为1。