第一个方法是Frobenius formula。这个formula专门考虑如下问题，给定n个conjugacy class \gamma_1,...\gamma_m。考虑满足如下条件的全部的n-tuple (x_1,...,x_m)x_i 都属于S_n
xi的type是\gamma_i。
x_1...x_m=1。
满足这些条件的全部的这样的n-tuple的个数可以用Frobenius formula进行计算。这个方法是一般性的方法，常用于各种各样关于permutation group衍生出来的组合问题的计算中。/wiki/Frobenius_formula
第二个方法也是可以推广的一个方法。你问的问题可以类似考虑一个“等价”问题，给定n个不同的点，他们一共可以生成多少个不同的tree。答案留给题主自己算，我只给一下简单的思路。实际上，每两个点之间如果存在一条线，那么就意味着，有一个2-cycle。给定一个tree，一共有n-1个2-cycle，一共可以生成？个不同的n-cycle(自己算)。那么
number of trees * number of cycles generated by each tree=?? * number of n-cycles。
？？：是你的问题的答案。
这个问题可以拓展到n-cycle，甚至任意type的cycle上。图论中叫做hypergraph theory。
