反复排列

$n$个元素共有$n!$种排列，对$n=3$而言有以下六种排列: \begin{align*} P_1: &(123)\mapsto(123), \\ P_2: &(123)\mapsto(213), \\ P_3: &(123)\mapsto(321), \\ P_4: &(123)\mapsto(132), \\ P_5: &(123)\mapsto(312), \\ P_6: &(123)\mapsto(231), \end{align*} 记$I$为恒等排列$(1\ldots n)\mapsto(1\ldots n)$。给定一个排列，令$f(P)$为使得$P^m=I$的最小正整数$m$，对$n=3$而言有 \begin{align*} f(P_1)=1: &(123), \\ f(P_2)=2: &(213)\mapsto(123), \\ f(P_3)=2: &(321)\mapsto(123), \\ f(P_4)=2: &(132)\mapsto(123), \\ f(P_5)=3: &(312)\mapsto(231)\mapsto(123), \\ f(P_6)=3: &(231)\mapsto(312)\mapsto(123), \end{align*} 令$g(n)$为长度为n的排列中各$f(P)$的平方均值，例如 $$g(3)=\frac{1}{3!}(1^2+2^2+2^2+2^2+3^2+3^2)=\frac{31}{6}\approx5.166666667e0.$$ 可以验证$g(5)=2081/120\approx1.734166667e1$以及$g(20)=12422728886023769167301/2432902008176640000\approx5.106136147e3$。

求$g(350)$，用科学计数法表示，以小写字母e来分隔尾数和指数，尾数应如上例一样保留10位有效数字。

本题难度:

解答

本题即求对称群的平均阶数。

每个排列都可以分解若干个循环排列之积，其阶数就是这些循环排列的阶数的最小公倍数。

由$a_i$个$i$阶循环排列之积组成的排列共有$n!/(a_i!\cdot i^{a_i})$个。

接下来就是在$\sum_i i\cdot a_i=n$的约束下枚举$(a_1,\ldots,a_n)$，这是比较常规的问题，有很多方法可以实现，以下代码用动态规划递推计算，最终结果是$4.993401567e22$。

注：因使用math.lcm函数，以下代码为Python 3。

import math

N=350

primeFactorMax=[1]*(N+1)
for i in range(2,N+1):
    if primeFactorMax[i]==1:
        for j in range(i,N+1,i):
            primeFactorMax[j]=i

f=[{} for i in range(N+1)]
f[0][1]=f[1][1]=x=1.0
for i in range(2,N+1):
    x/=i
    f[i][1]=x

for p in range(N,1,-1):
    if primeFactorMax[p]==p:
        for c in range(p,N+1,p):
            if primeFactorMax[c]==p:
                g=[{} for i in range(N+1)]
                x=1.0
                t=0
                while t<=N:
                    for d in range(t,N+1):
                        for k,v in f[d-t].items():
                            r=math.lcm(k, 1 if t==0 else c)
                            g[d][r]=g[d].get(r,0)+v*x
                    t+=c
                    x/=t
                f=g
                del g
        for c in range(N+1):
            h={}
            for k,v in f[c].items():
                while k%p==0:
                    k//=p
                    v*=p*p
                h[k]=h.get(k,0)+v
            f[c]=h
            del h

print(f"{sum(k*k*v for k,v in f[N].items()):.9e}")